2593. Find Score of an Array After Marking All Elements
Problem Description
In this problem, you are given an array called nums
which contains positive integers. The task is to implement an algorithm to calculate a score, beginning with a score of 0. The algorithm consists of the following steps:
- Identify the smallest unmarked integer in the array. If there's a tie for the smallest number, choose the one that comes first in the array.
- Add the value of this chosen integer to a running total score.
- Mark the chosen integer as well as its neighbors - the numbers immediately to its left and right in the array, if they exist.
- Repeat this process until all elements in the array have been marked.
The goal is to return the final score after all elements in the array have been processed according to the algorithm described.
Intuition
To efficiently solve this problem, we must strategically pick the smallest unmarked integers while keeping track of which elements are marked. Using a min heap (or a priority queue in terms of some programming languages) can help us to maintain a sorted set of unmarked elements to choose from. Each element we're considering is a pair consisting of the integer's value and its index in the array.
The intuition for using a min heap is due to its property of always giving us the smallest element when we pop from it. This helps us to follow the rule of choosing the smallest unmarked integer at each step without having to sort the array or search for the minimum value each time we make a choice.
When we choose an integer from the min heap, we add its value to the score and mark it along with its adjacent indices. Once an index is marked, we ensure it doesn't come back into consideration by popping out all marked elements from the top of the min heap before making the next choice.
The main challenges we need to address in our algorithm are:
- Efficiently finding and choosing the smallest unmarked numbers.
- Keeping track of which elements have been marked to avoid selecting them again.
- Handling the situation when there are multiple smallest numbers (resolving ties by index).
- Maintaining the min heap property by popping out marked elements before each new selection.
To achieve the above challenges, we initialize a priority queue to store pairs of numbers and their indices from the given array, and we mark elements inside a boolean visitation array. The workflow consists of choosing and popping the smallest number from the heap, marking the chosen numbers, and popping out all marked elements from the top of the heap before proceeding to the next step.
With this approach, we can assure that we're always operating on the right elements in a time-efficient manner. The process goes on until the heap is empty, which means all elements have been marked, and we then return the accumulated score.
Learn more about Sorting and Heap (Priority Queue) patterns.
Solution Approach
The implementation of the solution to this problem involves a couple of critical concepts from computer science, primarily from the field of data structures and algorithms.
Solution 1: Priority Queue (Min Heap)
Since we need to repeatedly select the smallest unmarked element from our list, a Min Heap is used, which is a binary tree where the parent is always smaller than its children. This guarantees that the smallest element will always be at the root of the tree, hence accessible in constant time O(1)
. To ensure that we are always working with the smallest unmarked items, we perform the following steps:
- Introduce a priority queue and fill it with pairs
(value, index)
for all elements in the array. - Use a
visited
array of boolean values initially set toFalse
, which will mark whether elements innums
have been considered or not. - While the priority queue is not empty:
- Extract the smallest element from the heap which is unmarked. If it is already marked, continue extracting until an unmarked one is found.
- Once found, add its value to the
score
, and mark this element as visited. - Also mark the adjacent elements (left and right neighbors) as visited.
- Then, remove all top elements in the heap that are marked as visited to keep the heap clean for the next iteration.
- After all elements have been marked and processed, the running score is returned as the final answer.
The time complexity of this solution is O(n log n)
because we perform at most n
insertions to the heap and n
deletions from the heap, both of which are O(log n)
operations. The space complexity is O(n)
due to the storage required for the heap and the visited array.
Solution 2: Sorting (Alternate Approach)
An alternate solution involves sorting. Here's the workflow:
- Create an index array
idx
whereidx[i]=i
for each element innums
. - Sort the index array
idx
so that its indices correspond to the elements innums
sorted first by value and then by their index, should values be equal. - Create an array
vis
of lengthn+2
initialized tofalse
, which will keep track of the marked elements. - Iterate through the index array
idx
, for each elementi
:- If
vis[i+1]
isfalse
, it means the elementnums[i]
is not marked, add it to the score. - Mark this element as visited along with its left and right adjacent elements by setting the corresponding
vis
entries totrue
.
- If
- Continue this process for the entire array
idx
. - Finally, return the accumulated score as the result.
In this approach, the initial sorting has a time complexity of O(n log n)
, and the iteration has a time complexity of O(n)
, resulting in a total complexity of O(n log n)
. The space complexity is O(n)
due to the additional index and visited arrays.
Both methods leverage efficient data structures to systematically reduce our problem into smaller sub-problems that can be solved in a stepwise fashion.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a simple example to demonstrate how the solution approach works. Suppose we have the following array nums
: [4, 1, 3, 2]
. We want to calculate the score based on the rules specified.
Here's how we would apply the Priority Queue (Min Heap) approach step by step:
-
Initialize our priority queue with pairs
(value, index)
and thevisited
array:- Priority Queue:
[(4, 0), (1, 1), (3, 2), (2, 3)]
(will be represented as a heap internally). - Visited:
[False, False, False, False]
- Priority Queue:
-
The priority queue works as a min heap and will sort the pairs to
[(1, 1), (2, 3), (3, 2), (4, 0)]
with the smallest pair(1, 1)
at the top. -
Pop
(1, 1)
from the heap since1
is the smallest unmarked element and its index is1
. Add its value to the score (initially0
), so score =1
. -
Mark element at index
1
and its neighbors as visited:- Visited:
[False, True, True, False]
- Visited:
-
Pop all marked elements from the top of the heap. In this case, the next element
(3, 2)
would be popped out, as it's marked visited. -
The heap now effectively has
[(2, 3), (4, 0)]
. Next, we pop(2, 3)
because it is the smallest unmarked element. Add its value to the score, so score =1 + 2 = 3
. -
Mark element at index
3
and its neighbors as visited. Since there's no element to the right of index3
, only index3
is marked:- Visited:
[False, True, True, True]
- Visited:
-
Again, we pop all marked elements from the top of the heap. Since
(4, 0)
is at the top and is the last unmarked element, we process it next. -
Add the value of the last element to the score, so score =
3 + 4 = 7
. -
Mark the last element as visited:
- Visited:
[True, True, True, True]
- Visited:
-
The priority queue is now empty, so we exit the loop and return the final score
7
.
Following the above steps, we would be able to find the result using the Priority Queue (Min Heap) approach. The final score as per our steps for the given array [4, 1, 3, 2]
is 7
.
Solution Implementation
1from heapq import heapify, heappop # We need these functions to work with a priority queue (min-heap).
2
3class Solution:
4 def findScore(self, nums: List[int]) -> int:
5 # Calculate the length of the input list.
6 length = len(nums)
7
8 # Initialize a visited list to keep track of elements that have been added to the score.
9 visited = [False] * length
10
11 # Create a priority queue with pairs (value, index) for each number in nums.
12 priority_queue = [(value, index) for index, value in enumerate(nums)]
13 heapify(priority_queue) # Transform list into a heap, in-place, in linear time.
14
15 # Initialize the answer to 0.
16 score = 0
17
18 # Process the queue until it's empty.
19 while priority_queue:
20 # Pop the smallest item from the heap, increasing the score by its value.
21 value, index = heappop(priority_queue)
22 score += value
23 visited[index] = True # Mark the current index as visited.
24
25 # Mark the neighbors of the current index as visited.
26 for neighbor in (index - 1, index + 1):
27 if 0 <= neighbor < length:
28 visited[neighbor] = True
29
30 # Remove all elements from the heap whose indices have been visited.
31 while priority_queue and visited[priority_queue[0][1]]:
32 heappop(priority_queue)
33
34 # Return the calculated score.
35 return score
36
1class Solution {
2 public long findScore(int[] nums) {
3 int length = nums.length;
4 // Create an array to keep track of visited indices
5 boolean[] visited = new boolean[length];
6 // Create a priority queue to store the pairs of number and index,
7 // sorted by the number value, and in case of a tie, by the index
8 PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(
9 (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
10
11 // Add all numbers along with their indices to the priority queue
12 for (int i = 0; i < length; ++i) {
13 priorityQueue.offer(new int[] {nums[i], i});
14 }
15
16 long totalScore = 0; // This will hold the final score
17
18 // Process the queue until it's empty
19 while (!priorityQueue.isEmpty()) {
20 var currentPair = priorityQueue.poll(); // Get the pair with the smallest number
21 totalScore += currentPair[0]; // Add the number to the score
22 visited[currentPair[1]] = true; // Mark the index as visited
23
24 // Visit the neighbors of the current index and mark them as visited
25 for (int neighborIndex : List.of(currentPair[1] - 1, currentPair[1] + 1)) {
26 if (neighborIndex >= 0 && neighborIndex < length) {
27 visited[neighborIndex] = true;
28 }
29 }
30
31 // Discard all pairs from the queue where the index has been visited
32 while (!priorityQueue.isEmpty() && visited[priorityQueue.peek()[1]]) {
33 priorityQueue.poll();
34 }
35 }
36
37 // Return the total score calculated
38 return totalScore;
39 }
40}
41
1class Solution {
2public:
3 long long findScore(vector<int>& nums) {
4 int size = nums.size();
5 // 'visited' vector keeps track of whether a number at an index has been added to the score.
6 vector<bool> visited(size, false);
7 // Pair to store the value and its index in the heap.
8 using ValueIndexPair = pair<int, int>;
9 // Min-heap to store numbers and their indices based on their value, in ascending order.
10 priority_queue<ValueIndexPair, vector<ValueIndexPair>, greater<ValueIndexPair>> min_heap;
11
12 // Populate the heap with the numbers and their indices.
13 for (int i = 0; i < size; ++i) {
14 min_heap.emplace(nums[i], i);
15 }
16
17 long long score = 0;
18 // Process the numbers until the heap is empty.
19 while (!min_heap.empty()) {
20 auto [value, index] = min_heap.top();
21 min_heap.pop();
22 // Add the value from the top of the min-heap to the score.
23 score += value;
24
25 // Mark the current index as visited.
26 visited[index] = true;
27 // Mark the adjacent numbers as visited as well, as per the problem statement.
28 if (index + 1 < size) {
29 visited[index + 1] = true;
30 }
31 if (index - 1 >= 0) {
32 visited[index - 1] = true;
33 }
34
35 // Remove the top element of the heap if it's been visited.
36 while (!min_heap.empty() && visited[min_heap.top().second]) {
37 min_heap.pop();
38 }
39 }
40 // Return the final calculated score.
41 return score;
42 }
43};
44
1interface Pair {
2 numberValue: number;
3 index: number;
4}
5
6function findScore(numbers: number[]): number {
7 // Initialize a priority queue with a custom compare function.
8 // The priority is based on the number value first, then the index.
9 const priorityQueue = new PriorityQueue({
10 compare: (a: Pair, b: Pair) =>
11 (a.numberValue === b.numberValue ? a.index - b.index : a.numberValue - b.numberValue),
12 });
13
14 // Get the length of the input array.
15 const length = numbers.length;
16
17 // Create an array to mark visited elements.
18 const visited: boolean[] = new Array(length).fill(false);
19
20 // Enqueue all elements along with their index into the priority queue.
21 for (let i = 0; i < length; ++i) {
22 priorityQueue.enqueue({ numberValue: numbers[i], index: i });
23 }
24
25 // Initialize the score to zero.
26 let score = 0;
27
28 // Dequeue elements from the priority queue until it's empty.
29 while (!priorityQueue.isEmpty()) {
30 const { numberValue, index } = priorityQueue.dequeue()!;
31
32 // Skip already visited elements.
33 if (visited[index]) {
34 continue;
35 }
36
37 // Accumulate the score with the selected number's value.
38 score += numberValue;
39
40 // Mark the current, previous, and next elements as visited.
41 visited[index] = true;
42 if (index - 1 >= 0) {
43 visited[index - 1] = true;
44 }
45 if (index + 1 < length) {
46 visited[index + 1] = true;
47 }
48
49 // Remove all front elements in the queue that have been visited.
50 while (!priorityQueue.isEmpty() && visited[priorityQueue.front()!.index]) {
51 priorityQueue.dequeue();
52 }
53 }
54
55 // Return the final score.
56 return score;
57}
58
Time and Space Complexity
The time complexity of the given code is O(n * log n)
, as the algorithm requires inserting all n
elements into a min-heap and each insertion has a complexity of O(log n)
. Additionally, each element is removed exactly once, which also requires O(log n)
time per element. Hence, combined, the overall complexity is O(n * log n)
.
The space complexity is O(n)
because we allocate an array vis
of size n
and a heap q
that also could contain up to n
elements at the beginning. Although elements are popped from the heap, it does not grow to more than n
entries.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the relationship between a tree and a graph?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we