Find Score of an Array After Marking All Elements

Medium
1171.

Find Score of an Array After Marking All Elements

MediumArrayHash TableSortingHeap (Priority Queue)AmazonGoogle

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.

Start with score = 0 and every element of the positive integer array nums unmarked. Repeat until every element is marked:

  1. Choose the smallest unmarked element; if several are equal, choose the one with the smallest index.
  2. Add its value to score.
  3. 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^5
  • 1 <= nums[i] <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var findScore = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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:

  1. Choose the smallest unmarked element; if several are equal, choose the one with the smallest index.
  2. Add its value to score.
  3. 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^5
  • 1 <= nums[i] <= 10^4

Hints for Find Score of an Array After Marking All Elements

  1. Hint 1

    The order in which elements are considered is fixed: by value, then by index.

  2. Hint 2

    Marking only ever removes candidates; it never changes the order of the rest.

  3. 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

  1. Create the list of indices sorted by nums[i], ties by i.
  2. Keep a boolean marked array.
  3. Walk the sorted indices; skip a marked one. Otherwise add nums[i] to the score and mark i - 1, i and i + 1.
  4. 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 score

Java

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