Find Score of an Array After Marking All Elements
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. It repeatedly scans the entire array to find the smallest unmarked element, adds it to the score, and then marks it along with its neighbors.
Algorithm
- Initialize a
longvariablescoreto 0. - Create a boolean array
markedof the same size asnums, initialized tofalse. - Use a counter
markedCountto track the number of marked elements. - Loop until
markedCountequals the length ofnums. - Inside the loop, find the smallest unmarked element by iterating through the entire array.
- Add the found element's value to
score. - Mark the chosen element and its two adjacent elements (if they exist and are not already marked), updating
markedCount. - Return the final
score.
Walkthrough
The brute-force method follows the problem statement literally. We maintain a boolean array marked to keep track of which elements have been marked. In each step of the algorithm, we need to find the smallest unmarked element. To do this, we perform a linear scan through the nums array, ignoring any elements where marked[i] is true. We keep track of the minimum value seen so far and its index.
Once we find the smallest unmarked element at minIndex, we add its value nums[minIndex] to our running score. Then, we mark this element and its neighbors. We set marked[minIndex] to true. If minIndex - 1 is a valid index, we set marked[minIndex - 1] to true. Similarly, if minIndex + 1 is a valid index, we set marked[minIndex + 1] to true. We repeat this entire process until all elements in the array are marked.
class Solution { public long findScore(int[] nums) { int n = nums.length; boolean[] marked = new boolean[n]; long score = 0; int markedCount = 0; while (markedCount < n) { int minVal = Integer.MAX_VALUE; int minIndex = -1; // Find the smallest unmarked element with the smallest index for (int i = 0; i < n; i++) { if (!marked[i]) { if (nums[i] < minVal) { minVal = nums[i]; minIndex = i; } // Tie-breaking (smallest index) is handled naturally by the loop's direction } } if (minIndex == -1) { break; // All elements are marked } // Add to score score += nums[minIndex]; // Mark the element and its neighbors if (!marked[minIndex]) { marked[minIndex] = true; markedCount++; } if (minIndex > 0 && !marked[minIndex - 1]) { marked[minIndex - 1] = true; markedCount++; } if (minIndex < n - 1 && !marked[minIndex + 1]) { marked[minIndex + 1] = true; markedCount++; } } return score; }}The tie-breaking rule (smallest index) is naturally handled by the linear scan from left to right. If two elements have the same minimum value, the one with the smaller index will be found and stored first.
Complexity
Time
O(N^2). The outer `while` loop can run up to `N` times. In each iteration, we scan the entire array of `N` elements to find the minimum. This results in a quadratic time complexity.
Space
O(N). We use a boolean array `marked` of size `N` to store the state of each element.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the problem description.
Cons
Highly inefficient due to the repeated linear scan for the minimum element.
Will result in a 'Time Limit Exceeded' (TLE) error for large inputs as specified in the constraints.
A more efficient approach involves pre-processing the array to determine the order in which elements should be considered. The rule is to pick the smallest value, with ties broken by the smallest index. This is a standard sorting criterion. We can create pairs of (value, index), sort them, and then iterate through the sorted list to calculate the score.
Algorithm
- Create a list of pairs or a 2D array to store
(value, original_index)for each element innums. - Sort this list. The primary sorting key is the value (ascending), and the secondary key is the index (ascending).
- Initialize a
longvariablescoreto 0. - Create a boolean array
markedof sizeN, initialized tofalse. - Iterate through the sorted list of pairs
(val, idx). - For each pair, if the element at
idxis not already marked:- Add
valtoscore. - Mark the element at
idxand its neighbors (idx-1andidx+1) as true.
- Add
- Return the final
score.
Walkthrough
The bottleneck in the brute-force approach is repeatedly finding the minimum element. We can optimize this by figuring out the order of selection upfront. The problem states we should always pick the available element with the smallest value, and use the smallest index as a tie-breaker. This is equivalent to sorting the elements based on their value, and then their original index.
We first create a data structure, like a 2D array or a list of custom objects, to store both the value and the original index of each element from the input array nums. Then, we sort this structure. After sorting, we can iterate through the elements in their prioritized order.
For each element (value, index) in our sorted list, we check a marked array to see if the element at this original index has already been marked by a previous step. If it hasn't, we add its value to the score and mark the element itself and its adjacent neighbors in the original array layout. If it's already marked, we simply skip it and move to the next element in the sorted list.
import java.util.Arrays;import java.util.Comparator; class Solution { public long findScore(int[] nums) { int n = nums.length; int[][] indexedNums = new int[n][2]; for (int i = 0; i < n; i++) { indexedNums[i][0] = nums[i]; indexedNums[i][1] = i; } // Sort by value, then by index for tie-breaking Arrays.sort(indexedNums, (a, b) -> { if (a[0] != b[0]) { return Integer.compare(a[0], b[0]); } else { return Integer.compare(a[1], b[1]); } }); boolean[] marked = new boolean[n]; long score = 0; for (int i = 0; i < n; i++) { int val = indexedNums[i][0]; int index = indexedNums[i][1]; if (!marked[index]) { score += val; marked[index] = true; if (index > 0) { marked[index - 1] = true; } if (index < n - 1) { marked[index + 1] = true; } } } return score; }}This approach processes each element from the sorted list once, making it much faster.
Complexity
Time
O(N log N). The dominant operation is sorting the `N` elements, which takes `O(N log N)`. The subsequent iteration through the sorted elements takes `O(N)`.
Space
O(N). We need `O(N)` space for the `indexedNums` array to store values and indices, and another `O(N)` for the `marked` array.
Trade-offs
Pros
Much more efficient than the brute-force approach.
Guaranteed to pass within the time limits for the given constraints.
Cons
Requires extra space proportional to the input size to store the indexed pairs for sorting.
This approach is similar in efficiency to sorting but uses a min-heap (Priority Queue) data structure. A min-heap is ideal for repeatedly finding and removing the minimum element from a collection. We populate a min-heap with all elements (as (value, index) pairs) and then iteratively extract the minimum, update the score, and mark elements.
Algorithm
- Create a min-heap (Priority Queue) that orders elements first by value, then by index.
- Insert all
(nums[i], i)pairs into the min-heap. - Initialize a
longvariablescoreto 0. - Create a boolean array
markedof sizeN, initialized tofalse. - While the min-heap is not empty:
- Extract the top element
(val, idx)from the heap. - If the element at
idxis already marked, ignore it and continue. - If it's not marked:
- Add
valtoscore. - Mark the element at
idxand its neighbors (idx-1andidx+1) as true.
- Add
- Extract the top element
- Return the final
score.
Walkthrough
Instead of sorting all elements at once, we can use a min-heap (implemented as a PriorityQueue in Java) to maintain the set of available elements and efficiently retrieve the one with the highest priority (smallest value, then smallest index).
First, we populate the priority queue with pairs of (value, index) for every element in the input array. The priority queue is configured with a custom comparator to order pairs first by value, and then by index in case of a tie.
Then, we enter a loop that continues as long as the priority queue is not empty. In each iteration, we extract the element with the highest priority (the minimum). We then check our marked array to see if this element has already been marked by a previous step (as a neighbor of another chosen element). If it's already marked, we discard it and proceed to the next iteration. If not, it's a valid choice. We add its value to the score and mark it and its neighbors in the marked array.
import java.util.PriorityQueue; class Solution { public long findScore(int[] nums) { int n = nums.length; // PriorityQueue stores [value, index] // It's a min-heap ordered by value, then index. PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> { if (a[0] != b[0]) { return Integer.compare(a[0], b[0]); } else { return Integer.compare(a[1], b[1]); } }); for (int i = 0; i < n; i++) { pq.offer(new int[]{nums[i], i}); } boolean[] marked = new boolean[n]; long score = 0; while (!pq.isEmpty()) { int[] top = pq.poll(); int val = top[0]; int index = top[1]; if (!marked[index]) { score += val; marked[index] = true; if (index > 0) { marked[index - 1] = true; } if (index < n - 1) { marked[index + 1] = true; } } } return score; }}This method is conceptually similar to the sorting approach but processes elements dynamically rather than in a pre-sorted batch.
Complexity
Time
O(N log N). Inserting `N` elements into the priority queue takes `O(N log N)`. The main loop runs up to `N` times, and each `poll` operation takes `O(log N)`, leading to a total time complexity of `O(N log N)`.
Space
O(N). The priority queue can store up to `N` elements, and the `marked` array also requires `O(N)` space.
Trade-offs
Pros
Efficient and a natural fit for problems requiring repeated extraction of minimum/maximum elements.
Asymptotically equivalent in performance to the sorting approach.
Cons
Can have slightly higher constant factor overhead compared to sorting in some language implementations.
Requires extra space for the heap and the marked array.
Solutions
Solution
class Solution {public long findScore(int[] nums) { int n = nums.length; boolean[] vis = new boolean[n]; PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]); for (int i = 0; i < n; ++i) { q.offer(new int[]{nums[i], i}); } long ans = 0; while (!q.isEmpty()) { var p = q.poll(); ans += p[0]; vis[p[1]] = true; for (int j : List.of(p[1] - 1, p[1] + 1)) { if (j >= 0 && j < n) { vis[j] = true; } } while (!q.isEmpty() && vis[q.peek()[1]]) { q.poll(); } } return ans; }}class Solution {public: long long findScore(vector<int> &nums) { int n = nums.size(); vector<bool> vis(n); using pii = pair<int, int>; priority_queue<pii, vector<pii>, greater<pii>> q; for (int i = 0; i < n; ++i) { q.emplace(nums[i], i); } long long ans = 0; while (!q.empty()) { auto [x, i] = q.top(); q.pop(); ans += x; vis[i] = true; if (i + 1 < n) { vis[i + 1] = true; } if (i - 1 >= 0) { vis[i - 1] = true; } while (!q.empty() && vis[q.top().second]) { q.pop(); } } return ans; }};class Solution: def findScore(self, nums: List[int]) -> int: n = len(nums) vis = [False] * n q = [(x, i) for i, x in enumerate(nums)] heapify(q) ans = 0 while q: x, i = heappop(q) ans += x vis[i] = True for j in (i - 1, i + 1): if 0 <= j < n: vis[j] = True while q and vis[q[0][1]]: heappop(q) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.