LeetCode 1040: Moving Stones Until Consecutive II

Problem Restatement

We have n stones at distinct positions on an infinite line.

In one move, we pick the leftmost or rightmost stone and move it to any unoccupied position between the leftmost and rightmost stones.

We need to return [min_moves, max_moves].

The official constraints state that 3 <= stones.length <= 10^4 and 1 <= stones[i] <= 10^9.

Input and Output

Function shape:

def numMovesStonesII(stones: list[int]) -> list[int]:
    ...

Examples

Example 1:

stones = [7, 4, 9]

Move stone 9 to 5: [4,5,7]. Then move 7 to 6: [4,5,6]. Min = 2.

Max: Move 4 to 8: [7,8,9]. 1 move. Wait, that’s for 3 stones. Max for 3 stones is the total gaps minus 1 consideration.

Answer:

[1, 2]

Key Insight

Maximum moves: Each move takes one endpoint stone and moves it one step closer from the other side. The maximum is:

max(stones[-1] - stones[1] - (n - 2), stones[-2] - stones[0] - (n - 2))

(The first expression moves the leftmost stone as far right as possible, the second moves the rightmost stone as far left as possible.)

Minimum moves: Use a sliding window of size n on the sorted positions. For each window [stones[i], stones[i] + n - 1], count how many stones are already inside. The moves needed are n - (stones inside), with a special case when n - 1 stones are inside but they are all consecutive starting from one end (then we need 2 moves, not 1).

Algorithm

1. Sort stones.
2. Max = max(stones[-1] - stones[1] - n + 2, stones[-2] - stones[0] - n + 2).
3. For min, use sliding window to find window of width n-1 with maximum stones inside.

Correctness

For the maximum, one endpoint stone moves inward each step. The total moves until all are consecutive equals the total gap available for the endpoint with more room.

For the minimum, the optimal strategy places all stones into a window of length n - 1. Stones already in the window don’t need to move.

Edge Cases

• Handle windows that never become valid.
• Update counts when both expanding and shrinking the window so stale characters do not remain in the state.
• For fixed-size windows, record the answer only after the window has exactly the required length.

Complexity

Common Pitfalls

• Do not count a window before it satisfies the required size or validity condition.
• When removing the left character, delete zero-count entries if the algorithm uses the number of keys.

Implementation

class Solution:
    def numMovesStonesII(self, stones: list[int]) -> list[int]:
        stones.sort()
        n = len(stones)

        max_moves = max(
            stones[-1] - stones[1] - n + 2,
            stones[-2] - stones[0] - n + 2
        )

        min_moves = n
        j = 0
        for i in range(n):
            while j + 1 < n and stones[j + 1] - stones[i] < n:
                j += 1
            already = j - i + 1
            if already == n - 1 and stones[j] - stones[i] == n - 2:
                min_moves = min(min_moves, 2)
            else:
                min_moves = min(min_moves, n - already)

        return [min_moves, max_moves]

Testing

def run_tests():
    s = Solution()

    assert s.numMovesStonesII([7, 4, 9]) == [1, 2]
    assert s.numMovesStonesII([6, 5, 4, 3, 10]) == [2, 3]

    print("all tests passed")

run_tests()