Clearing the Stacks Evenly

Easy

A warehouse holds stacks of crates: stacks[i] is the height of stack i (0 means it is empty). In one round a worker picks an integer x > 0 no greater than the height of the lowest **non-empty** stack and removes exactly x crates from every non-empty stack. Return the fewest rounds needed to empty all the stacks.

Example 1

stacks=[4, 0, 2, 4, 6] → 3

Take 2 from each: [2, 0, 0, 2, 4]. Take 2 again: [0, 0, 0, 0, 2]. Then the last 2: all empty after three rounds.

Example 2

stacks=[0, 0] → 0

All stacks are already empty.

Example 3

stacks=[3, 3, 3] → 1

Constraints

1 ≤ len(stacks) ≤ 100
0 ≤ stacks[i] ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Hash Table Sorting Simulation Heap (Priority Queue)

Similar problems

Jobs With a Cooldown Medium Narrowest Range Touching Every List Hard Spread Out the Labels Medium Cross Out Half the List Medium Busiest Meeting Room Hard

Input

stacks=[4, 0, 2, 4, 6]

Expected

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