Moving Stones Until Consecutive II
01 · Problem
Stones sit on an infinite number line at the distinct integer positions given in stones.
A stone is an endpoint stone if it is at the smallest or the largest position. In one move you pick up an endpoint stone and place it on an unoccupied integer position such that it is no longer an endpoint stone (that is, strictly between the new smallest and largest remaining positions). The game ends when the stones occupy consecutive positions, after which no move is possible.
Return an array [minimumMoves, maximumMoves]: the fewest and the most moves you can make before the game ends.
02 · Examples
stones = [1,5,6,12]
[2,5]
Minimum: move 1 to 7, then 12 to 8, for [5,6,7,8]. Maximum: move 1 to 7, then 5 to 8, 6 to 9, 7 to 10 and 8 to 11, ending at [9,10,11,12] after 5 moves.
stones = [6,5,4,3,10]
[2,3]
Minimum: move 3 to 8, then 10 to 7, for [4,5,6,7,8]. Maximum: move 3 to 7, then 4 to 8, then 5 to 9, for [6,7,8,9,10].
stones = [100,101,104,102,103]
[0,0]
The stones already occupy 100-104 consecutively, so no move can be made.
03 · Constraints
- 013 <= stones.length <= 104
- 021 <= stones[i] <= 109
- 03All values in stones are distinct
04 · Optimal complexity
- Time
- O(n log n)
- Space
- O(1)
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.