Find Score of an Array After Marking All Elements
Problem
Start with score = 0. Repeatedly choose the smallest unmarked value in nums (on a tie, the smallest index), add it to score, then mark that element and its two adjacent elements if they exist. Continue until every element is marked, and return the final score.
nums = [2, 1, 3, 4, 5, 2]7def findScore(nums):
n = len(nums)
marked = [False] * n
# (value, index) pairs sorted: smallest value first, then smallest index
order = sorted(range(n), key=lambda i: (nums[i], i))
score = 0
for i in order:
if marked[i]: # skip already-marked picks
continue
score += nums[i] # take the smallest unmarked value
marked[i] = True
if i - 1 >= 0:
marked[i - 1] = True # mark left neighbor
if i + 1 < n:
marked[i + 1] = True # mark right neighbor
return scorefunction findScore(nums) {
const n = nums.length;
const marked = new Array(n).fill(false);
// indices sorted by (value, then index)
const order = [...nums.keys()].sort(
(a, b) => nums[a] - nums[b] || a - b);
let score = 0;
for (const i of order) {
if (marked[i]) continue; // skip marked picks
score += nums[i]; // take smallest unmarked value
marked[i] = true;
if (i - 1 >= 0) marked[i - 1] = true; // left neighbor
if (i + 1 < n) marked[i + 1] = true; // right neighbor
}
return score;
}long findScore(int[] nums) {
int n = nums.length;
boolean[] marked = new boolean[n];
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) order[i] = i;
// sort by value, then by index on ties
Arrays.sort(order, (a, b) ->
nums[a] != nums[b] ? nums[a] - nums[b] : a - b);
long score = 0;
for (int i : order) {
if (marked[i]) continue; // skip marked picks
score += nums[i]; // take smallest unmarked value
marked[i] = true;
if (i - 1 >= 0) marked[i - 1] = true; // left neighbor
if (i + 1 < n) marked[i + 1] = true; // right neighbor
}
return score;
}long long findScore(vector<int>& nums) {
int n = nums.size();
vector<bool> marked(n, false);
vector<int> order(n);
iota(order.begin(), order.end(), 0);
// sort by value, then by index on ties
sort(order.begin(), order.end(), [&](int a, int b) {
return nums[a] != nums[b] ? nums[a] < nums[b] : a < b;
});
long long score = 0;
for (int i : order) {
if (marked[i]) continue; // skip marked picks
score += nums[i]; // take smallest unmarked value
marked[i] = true;
if (i - 1 >= 0) marked[i - 1] = true; // left neighbor
if (i + 1 < n) marked[i + 1] = true; // right neighbor
}
return score;
}Explanation
The rule "always take the smallest unmarked value, breaking ties by index" is exactly what a min-heap / priority queue gives you. Push every (value, index) pair; the heap pops them in increasing value, and for equal values the smaller index comes out first.
But notice we never need to change an element's priority — we only ever skip it once it has been marked. So instead of a live heap we can simply sort the indices once by (value, index) and walk through them in that frozen order. Both views process elements in the identical sequence; sorting is just a heap that does all its pops up front.
As we walk the sorted order, we keep a boolean marked[] array. When we reach an index i that is still unmarked, it is guaranteed to be the smallest unmarked value remaining, so we add nums[i] to the score and mark i together with its neighbors i − 1 and i + 1 (when they are inside the array).
If an index comes up already marked — because an earlier, smaller pick touched it as a neighbor — we just skip it. That single check is what keeps the simulation faithful: every value is considered in sorted order, but only the ones that survive contribute to the score.
Example: nums = [2,1,3,4,5,2]. Sorted order of indices is 1, 0, 5, 2, 3, 4. We take 1 (mark 0,1,2), then index 0 and 2 are already marked, take the 2 at index 5 (mark 4,5), then take 4 at index 3. Score = 1 + 2 + 4 = 7.