2593. Find Score of an Array After Marking All Elements

MediumArraySortingSimulationHeap (Priority Queue)

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 to False, which will mark whether elements in nums have been considered or not.
While the priority queue is not empty:
1. Extract the smallest element from the heap which is unmarked. If it is already marked, continue extracting until an unmarked one is found.
2. Once found, add its value to the score, and mark this element as visited.
3. Also mark the adjacent elements (left and right neighbors) as visited.
4. 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 where idx[i]=i for each element in nums.
Sort the index array idx so that its indices correspond to the elements in nums sorted first by value and then by their index, should values be equal.
Create an array vis of length n+2 initialized to false, which will keep track of the marked elements.
Iterate through the index array idx, for each element i:
1. If vis[i+1] is false, it means the element nums[i] is not marked, add it to the score.
2. Mark this element as visited along with its left and right adjacent elements by setting the corresponding vis entries to true.
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 Evaluator

Example 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 the visited array:
- Priority Queue: [(4, 0), (1, 1), (3, 2), (2, 3)] (will be represented as a heap internally).
- Visited: [False, False, False, False]
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 since 1 is the smallest unmarked element and its index is 1. Add its value to the score (initially 0), so score = 1.
Mark element at index 1 and its neighbors as visited:
- Visited: [False, True, True, False]
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 index 3, only index 3 is marked:
- Visited: [False, True, True, True]
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]
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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

dp[i] = dp[i - 1] + dp[i - 2]

dp[i] = dp[i - 1] + 1

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

dp[i] = dp[i - 1]

I don’t know