MediumHeapAI interview only
Find Score Of An Array
Asked atamazongooglemicrosoft
01 · Problem
You are given an array nums of positive integers. Start with score = 0 and every element unmarked, then repeat the following until every element is marked:
- Pick the smallest unmarked element. If several unmarked elements share that value, pick the one with the smallest index.
- Add its value to
score. - Mark that element and its immediate left and right neighbours (if they exist). Marking an already marked element has no effect.
Return the final score.
02 · Examples
Example 01
Input
nums = [2,1,3,4,5,2]
Output
7
Pick 1 (index 1), marking indices 0-2. Next smallest unmarked is 2 at index 5, marking indices 4-5. Then 4 at index 3 remains. Score = 1 + 2 + 4 = 7.
Example 02
Input
nums = [2,3,5,1,3,2]
Output
5
Pick 1 (index 3), marking indices 2-4. Two 2s remain unmarked; the lower index 0 is taken first, marking indices 0-1. Then 2 at index 5. Score = 1 + 2 + 2 = 5.
Example 03
Input
nums = [1]
Output
1
The only element is picked once, giving a score of 1.
03 · Constraints
- 011 <= nums.length <= 105
- 021 <= nums[i] <= 106
- 03Ties in value are broken by choosing the smaller index
- 04The answer may exceed the 32-bit range, so use a 64-bit integer
04 · Optimal complexity
- Time
- O(n log n)
- Space
- O(n)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.