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.
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; }}Video 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.