Find Score of an Array After Marking All Elements — Solution
Find Score of an Array After Marking All Elements solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find Score of an Array After Marking All Elements is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Sorting, Heap
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Start with score = 0 and every element of the positive integer array nums unmarked. Repeat until every element is marked:
- Choose the smallest unmarked element; if several are equal, choose the one with the smallest index.
- Add its value to
score. - Mark it and its two adjacent elements (those that exist).
Return the final score.
Note: the original problem allows values up to 10^6 and returns a 64-bit score; here nums[i] <= 10^4, so the answer always fits in a 32-bit integer.
Example 1
Input: nums = [3,1,4,1,5,2]
Output: 4
Explanation: Take the 1 at index 1 (marks indices 0–2), then the 1 at index 3 (marks 2–4), then the 2 at index 5. Score 1 + 1 + 2 = 4.
Example 2
Input: nums = [7]
Output: 7
Example 3
Input: nums = [2,2,2,2]
Output: 4
Explanation: Index 0 is chosen first (ties go to the smaller index), marking 0 and 1; then index 2.
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^4
Hints for Find Score of an Array After Marking All Elements
Hint 1
The order in which elements are considered is fixed: by value, then by index.
Hint 2
Marking only ever removes candidates; it never changes the order of the rest.
Hint 3
Sort the indices by
(value, index)and walk them, skipping any index that is already marked.
How to solve Find Score of an Array After Marking All Elements
The process always picks the first unmarked index in (value, index) order. Sorting the indices by that key once and skipping marked ones reproduces the process exactly.
Approach
- Create the list of indices sorted by
nums[i], ties byi. - Keep a boolean
markedarray. - Walk the sorted indices; skip a marked one. Otherwise add
nums[i]to the score and marki - 1,iandi + 1. - Return the score.
Why it works
At each step the process selects the unmarked index that is smallest in (value, index) order. Walking the sorted list and skipping marked entries reaches exactly that index next, because every earlier entry in the list is already marked. Marks only accumulate, so a skipped index never becomes eligible again.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Ties must go to the smaller index — sort with the index as the second key (or use a stable sort).
- Marking a neighbour does not add it to the score.
- With the original limits the score needs 64 bits.
Reference solution
Python
from typing import List
def findScore(nums: List[int]) -> int:
n = len(nums)
order = sorted(range(n), key=lambda i: (nums[i], i))
marked = [False] * n
score = 0
for i in order:
if marked[i]:
continue
score += nums[i]
marked[i] = True
if i > 0:
marked[i - 1] = True
if i + 1 < n:
marked[i + 1] = True
return scoreJava
public static int findScore(int[] nums) {
int n = nums.length;
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) order[i] = i;
Arrays.sort(order, (a, b) -> nums[a] != nums[b] ? Integer.compare(nums[a], nums[b]) : Integer.compare(a, b));
boolean[] marked = new boolean[n];
long score = 0;
for (int at : order) {
if (marked[at]) continue;
score += nums[at];
marked[at] = true;
if (at > 0) marked[at - 1] = true;
if (at + 1 < n) marked[at + 1] = true;
}
return (int) score;
}C++
int findScore(vector<int>& nums) {
int n = nums.size();
vector<int> order(n);
for (int i = 0; i < n; i++) order[i] = i;
sort(order.begin(), order.end(), [&](int a, int b) {
return nums[a] != nums[b] ? nums[a] < nums[b] : a < b;
});
vector<bool> marked(n, false);
long long score = 0;
for (int at : order) {
if (marked[at]) continue;
score += nums[at];
marked[at] = true;
if (at > 0) marked[at - 1] = true;
if (at + 1 < n) marked[at + 1] = true;
}
return (int)score;
}JavaScript
var findScore = function(nums) {
var n = nums.length;
var order = [];
for (var i = 0; i < n; i++) order.push(i);
order.sort(function(a, b) { return nums[a] !== nums[b] ? nums[a] - nums[b] : a - b; });
var marked = new Array(n).fill(false);
var score = 0;
for (var k = 0; k < n; k++) {
var at = order[k];
if (marked[at]) continue;
score += nums[at];
marked[at] = true;
if (at > 0) marked[at - 1] = true;
if (at + 1 < n) marked[at + 1] = true;
}
return score;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets