Cross Out the Smallest First

Medium

You are given an array of positive integers values. At first nothing is crossed out and the score is zero. While some number is still not crossed out, repeat: 1. Take the smallest number that is not crossed out. On a tie, take the leftmost one. 2. Add it to the score. 3. Cross it out together with its left and right neighbours, if they exist (a neighbour that is already crossed out simply stays that way). Return the final score.

Example 1

values=[4, 2, 7, 1, 3] → 3

First take 1 (index 3) and cross it out together with 7 and 3. Of the remaining 4 and 2, the smaller is 2; taking it also crosses out 4. The score is 1 + 2 = 3.

Example 2

values=[5, 5, 5, 5] → 10

All values tie, so the leftmost wins: index 0 (crossing out 0 and 1), then index 2 (crossing out 2 and 3). The score is 10.

Example 3

values=[9] → 9

Constraints

1 ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 10⁶

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Sorting Simulation Heap (Priority Queue)

Similar problems

Shelf Total After Orders Medium Clearing the Stacks Evenly Easy Busiest Meeting Room Hard Most Common Values Medium Jobs With a Cooldown Medium

Input

values=[4, 2, 7, 1, 3]

Expected

Run checks the first 3 tests in your browser. Submit checks all 114 tests on the server, hidden ones included.