Find Score of an Array After Marking All Elements - Solution & Explanation
Problem Statement
You are given an array nums consisting of positive integers.
Starting with score = 0, apply the following algorithm:
- Choose the smallest integer of the array that is not marked. If there is a tie, choose the one with the smallest index.
- Add the value of the chosen integer to
score. - Mark the chosen element and its two adjacent elements if they exist.
- Repeat until all the array elements are marked.
Return the score you get after applying the above algorithm.
Example 1:
Input: nums = [2,1,3,4,5,2] Output: 7 Explanation: We mark the elements as follows: - 1 is the smallest unmarked element, so we mark it and its two adjacent elements: [2,1,3,4,5,2]. - 2 is the smallest unmarked element, so we mark it and its left adjacent element: [2,1,3,4,5,2]. - 4 is the only remaining unmarked element, so we mark it: [2,1,3,4,5,2]. Our score is 1 + 2 + 4 = 7.
Example 2:
Input: nums = [2,3,5,1,3,2] Output: 5 Explanation: We mark the elements as follows: - 1 is the smallest unmarked element, so we mark it and its two adjacent elements: [2,3,5,1,3,2]. - 2 is the smallest unmarked element, since there are two of them, we choose the left-most one, so we mark the one at index 0 and its right adjacent element: [2,3,5,1,3,2]. - 2 is the only remaining unmarked element, so we mark it: [2,3,5,1,3,2]. Our score is 1 + 2 + 2 = 5.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 106
Approach Overview
Problem Overview: You repeatedly pick the smallest unmarked element in the array, add its value to a running score, then mark that element and its immediate neighbors. The process continues until every element becomes marked. The challenge is efficiently selecting the smallest available element while ensuring already-marked indices are skipped.
Approach 1: Greedy with Sorting and Marking (O(n log n) time, O(n) space)
This approach sorts the elements by value while keeping their original indices. After sorting, iterate through the pairs (value, index) from smallest to largest. If the current index is not marked, add its value to the score and mark index, index - 1, and index + 1. A boolean array tracks which positions are already marked so they are skipped later. Sorting guarantees that the smallest available value is processed first, which satisfies the greedy requirement. This method is simple to implement and works well when you want predictable iteration over elements.
The algorithm uses ideas common in sorting and array traversal problems. Sorting costs O(n log n), while the marking operations remain constant time per element.
Approach 2: Priority Queue Based Greedy Selection (O(n log n) time, O(n) space)
Instead of sorting upfront, push every element into a min-heap as (value, index). Each step pops the smallest value from the heap. If its index is already marked, discard it and continue. Otherwise, add the value to the score and mark the element and its neighbors. The heap dynamically maintains the smallest candidate at the top, which matches the greedy rule of always choosing the minimum unmarked element.
This solution uses a heap (priority queue) to simulate the selection process. Each push and pop operation costs O(log n), leading to overall O(n log n) complexity. The approach is flexible when the selection order must be dynamically maintained rather than precomputed.
Recommended for interviews: The greedy idea is the real test here: always select the smallest unmarked value and invalidate its neighbors. The sorting approach is usually the cleanest explanation during interviews because it processes elements once after ordering them. The priority queue version demonstrates stronger familiarity with greedy selection structures and is useful when discussing alternatives that avoid full sorting.
Approach 1: Approach 1: Greedy with Sorting and Marking
Sort a copy of the array while maintaining the original indices to easily find the smallest element to mark. Use an auxiliary array to track marked elements. This approach finds the next smallest unmarked element in constant time after sorting.
This C code sorts the array with indices maintained, ensures constant time lookup for the smallest element, and tracks marked elements using a simple integer array.
Complexity
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing indices and marked status.
Approach 2: Approach 2: Priority Queue Based Greedy Selection
Use a priority queue (or min-heap) to efficiently select the smallest element that is unmarked at each step. This reduces the overall time spent searching for the next smallest element in a sorted list, ensuring optimized selection.
In this C implementation, we created a list of elements with values and indices and sorted it. Since a priority queue isn't available natively in C, we sort to simulate the behavior of selecting minimum values.
Complexity
Time Complexity: O(n log n) for sorting instead of using priority queue directly.
Space Complexity: O(n) for the element list and marking status.
Approach 3: Priority Queue (Min Heap)
We use a priority queue to maintain the unmarked elements in the array, and each item in the queue is a tuple (x, i), where x and i represent the element value and index of the array respectively. An array vis is used to record whether the element in the array is marked.
Each time we take out the smallest element (x, i) from the queue, we add x to the answer, and then mark the element at the i position, and the left and right adjacent elements at the i position, that is, the elements at the i-1 and i+1 positions. Then we determine whether the top element of the heap is marked. If it is marked, pop the top element of the heap until the top element is unmarked or the heap is empty.
Finally, return the answer.
The time complexity is O(n times log n) and the space complexity is O(n), where n is the length of the array.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Sorting
We can create an index array idx where idx[i]=i, and then we sort the index array idx according to the element values in the array nums. If the element values are the same, then sort them according to the index values.
Next, create an array vis of length n+2 where vis[i]=false, which means whether the element in the array is marked.
We traverse the index array idx, and for each index i in the array, if vis[i+1] is false, that is, the element at position i is not marked, we add nums[i] to the answer, and then mark the element at position i, and the left and right adjacent elements at position i, that is, the elements at positions i-1 and i+1. Continue to traverse the index array idx until the end.
Finally, return the answer.
The time complexity is O(n times log n) and the space complexity is O(n), where n is the length of the array.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Greedy with Sorting and Marking | Time Complexity: O(n log n) due to sorting. |
| Approach 2: Priority Queue Based Greedy Selection | Time Complexity: O(n log n) for sorting instead of using priority queue directly. |
| Priority Queue (Min Heap) | — |
| Sorting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting and Marking | O(n log n) | O(n) | Best for clean implementation when sorting elements once and scanning is sufficient. |
| Priority Queue Greedy Selection | O(n log n) | O(n) | Useful when dynamically retrieving the smallest element without sorting the entire array first. |
Video Solution
Find Score of an Array After Marking All Elements | 2 Approaches | Leetcode 2593 | codestorywithMIK • codestorywithMIK • 7,283 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find Score of an Array After Marking All Elements easy or hard?
Find Score of an Array After Marking All Elements Python/Java solution
How to solve Find Score of an Array After Marking All Elements in O(n)?
What is the best approach for Find Score of an Array After Marking All Elements?
Is Find Score of an Array After Marking All Elements asked at Google/Amazon/Meta?
What data structure is used in Find Score of an Array After Marking All Elements?
What is the time complexity of Find Score of an Array After Marking All Elements?
Ready to solve this problem?
Practice Find Score of an Array After Marking All Elements with our built-in code editor and test cases.
Practice on FleetCode