Watch 10 video solutions for Find Score of an Array After Marking All Elements, a medium level problem involving Array, Hash Table, Sorting. This walkthrough by codestorywithMIK has 6,878 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array nums consisting of positive integers.
Starting with score = 0, apply the following algorithm:
score.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] <= 106Problem 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 | 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. |