Find Score of an Array After Marking All Elements

Find Score of an Array After Marking All Elements

What is this problem about?

The Find Score of an Array After Marking All Elements interview question is a simulation problem. You start with a score of 0. In each step, you find the smallest unmarked element in the array (picking the smallest index if there's a tie). You add its value to your score and mark it, along with its immediate left and right neighbors. You repeat this until all elements are marked.

Why is this asked in interviews?

Companies like Visa and Bloomberg ask the Find Score coding problem to test your ability to use Heaps or Sorting to efficiently find minimum values in a dynamic state. It evaluations whether you can maintain a "marked" state correctly and avoid redundant searches. It's a great test of Heap (Priority Queue) interview patterns.

Algorithmic pattern used

This problem is solved using Sorting and a Visited Array.

1. Pairing: Create a list of pairs (value, index) for every element in the array.
2. Sort: Sort the pairs primarily by value and secondarily by index.
3. Iterate: Use a boolean marked array. For each pair (val, idx) in sorted order:
   • If marked[idx] is false:
     • score += val.
     • marked[idx] = true.
     • marked[idx - 1] = true (if valid).
     • marked[idx + 1] = true (if valid).
4. Result: Return the total score.

Example explanation

Array: [2, 1, 3, 4, 5, 2]

1. Sorted pairs: (1, 1), (2, 0), (2, 5), (3, 2), (4, 3), (5, 4).
2. Step 1: Smallest is 1 at index 1. score = 1. Mark indices {0, 1, 2}.
3. Step 2: Next smallest unmarked is 2 at index 5. score = 1 + 2 = 3. Mark indices {4, 5}.
4. Step 3: Next smallest unmarked is 4 at index 3. score = 3 + 4 = 7. Mark index {3}. All marked. Result: 7.

Common mistakes candidates make

• Linear Search: Searching for the minimum element in every step ($O(N^2)$), which is too slow. Sorting ($O(N \log N)$) is much better.
• Neighbor marking: Forgetting to check array boundaries before marking idx-1 or idx+1.
• Tie-breaking: Failing to sort by index when values are equal, which can lead to incorrect marking sequences.

Interview preparation tip

When a problem asks you to repeatedly find the "best" element, your first instinct should be a Heap or Sorting. If the "best" criteria is fixed (like value and index), sorting once is usually easier to implement than a dynamic heap.