Moving Stones Until Consecutive II: Sliding Window on Sorted Endpoints

You are given an array of integers stones representing positions of stones on the x-axis. In one move, you pick an endpoint stone (the leftmost or rightmost) and move it to any unoccupied position that is strictly between the remaining endpoints. You repeat this until all stones are on consecutive positions. Return an array [min_moves, max_moves].

This is LeetCode 1040: Moving Stones Until Consecutive II, and it is one of the trickiest medium-level problems because it combines two different techniques: a greedy argument for the maximum, and a sliding window for the minimum.

Why this problem matters

This problem sits at the intersection of sorting, sliding windows, and greedy reasoning. You cannot brute-force it because the search space is enormous. Instead, you need to think about the structure of the problem from two opposite angles: how to waste the most moves (maximum) and how to waste the fewest (minimum). Both arguments require you to reason about gaps between sorted positions, which is a pattern that shows up in many array and interval problems.

The sliding window portion is especially useful. Counting how many elements from a sorted array fall inside a window of fixed size is a building block you will see in problems about subarrays, permutations, and geometric containment.

The key insight

After sorting the stones, split the problem into two parts.

Maximum moves. Each move fills exactly one empty slot between the endpoints. The total number of empty slots is stones[n-1] - stones[0] - (n - 1). But the first move must skip over the gap created by removing an endpoint. If you move the left endpoint first, you lose the gap between stones[0] and stones[1]. If you move the right endpoint first, you lose the gap between stones[n-2] and stones[n-1]. You pick whichever option preserves more empty slots: max(stones[n-1] - stones[1], stones[n-2] - stones[0]) - (n - 2).

Minimum moves. You want to find a window of n consecutive positions that already contains the most stones. If a window [stones[i], stones[i] + n - 1] contains k stones, you need n - k moves to fill in the rest. Slide this window across the sorted array and track the best. There is one special case: if n - 1 stones are already consecutive and the one remaining stone is far away on one end, you cannot place it in a single move (there is no valid position strictly between the endpoints that completes the run). In that case, the answer is 2 instead of 1.

The solution

def num_moves_stones_ii(stones: list[int]) -> list[int]:
    stones.sort()
    n = len(stones)

    max_moves = max(stones[n - 1] - stones[1], stones[n - 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] + 1 <= n:
            j += 1
        stones_in_window = j - i + 1
        if stones_in_window == n - 1 and stones[j] - stones[i] + 1 == n - 1:
            min_moves = min(min_moves, 2)
        else:
            min_moves = min(min_moves, n - stones_in_window)

    return [min_moves, max_moves]

Let's walk through each piece.

First, sort the stones. This lets you reason about gaps between adjacent positions and slide a window from left to right.

For the maximum, consider two strategies. You can start by moving the left endpoint, which means the first move skips over the gap stones[1] - stones[0] - 1. After that, every subsequent move fills one empty slot in the remaining range [stones[1], stones[n-1]]. The total empty slots in that range are stones[n-1] - stones[1] - (n - 2). Similarly, if you start by moving the right endpoint, the empty slots are stones[n-2] - stones[0] - (n - 2). Take the larger of the two.

For the minimum, slide a window of size n (in terms of positions, not indices) across the number line. For each left boundary stones[i], find the rightmost stone stones[j] that fits inside the window [stones[i], stones[i] + n - 1]. The stones from index i to j are all inside the window, so you need n - (j - i + 1) moves to fill the rest. Track the best across all positions.

The special case triggers when you find n - 1 stones that are already consecutive (they span exactly n - 2 gaps with no holes) but the last stone is far away. In this situation, the "obvious" single move does not work because the far stone must land strictly between the remaining endpoints, and the only open slot in the consecutive run is at one end. You need two moves instead.

Visual walkthrough

Let's trace through the example stones = [6, 5, 4, 3, 10] step by step. After sorting, the stones are at positions [3, 4, 5, 6, 10].

Notice that the maximum is about choosing which endpoint to sacrifice first (the one that wastes fewer empty slots), while the minimum is about finding the tightest cluster of stones you can extend into a full consecutive sequence.

Complexity analysis

Time is O(n log n) due to sorting. The sliding window itself runs in O(n) because both pointers i and j only move forward. The maximum computation is O(1) after sorting. So the sort dominates.

Space is O(1) beyond the input (or O(n) if the sort is not in-place, depending on the language). No auxiliary data structures are needed.

The building blocks

1. Sliding window on sorted data

j = 0
for i in range(n):
    while j + 1 < n and stones[j + 1] - stones[i] + 1 <= n:
        j += 1
    window_count = j - i + 1

This pattern counts how many elements from a sorted array fall within a window of fixed size. The outer loop advances the left boundary. The inner while loop advances the right boundary as far as it can go without exceeding the window size. Because j never decreases, the total work across all iterations is O(n). You will see this exact pattern in problems like "Contains Duplicate III" (LeetCode 220), "Longest Substring Without Repeating Characters" (with a sorted twist), and any problem that asks "how many points fit inside a range of size k?"

2. Greedy endpoint analysis

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

This pattern reasons about the worst-case (or best-case) impact of removing an element from one end of a sorted array. By comparing the two possible first moves, you determine which one leaves the most room. This style of argument, considering two symmetric choices and taking the better one, appears in problems involving intervals, scheduling, and any greedy problem where you have a binary decision at each step.

Edge cases

• All stones already consecutive: both minimum and maximum are 0. The sliding window finds all n stones in one window.
• Three stones: this is a simpler version (LeetCode 1033). The sliding window still works, but you can also handle it with direct case analysis.
• Two large gaps on both sides: for example [1, 2, 3, 100, 200]. The maximum is max(200 - 2, 100 - 1) - 3 = 195. The minimum uses the window containing [1, 2, 3], needing 2 moves.
• The special case: [1, 2, 3, 4, 10]. Four consecutive stones and one outlier. The minimum is 2, not 1, because stone 10 cannot jump directly to position 5 (it must land strictly between the remaining endpoints, which are 1 and 4 after removing 10, but 5 is not between 1 and 4).
• Stones spread far apart: the algorithm handles arbitrarily large values because it works with positions, not indices. No array of size stones[n-1] is allocated.

From understanding to recall

The two-part structure of this problem, greedy for maximum and sliding window for minimum, is what makes it hard. Understanding the logic is one thing. Reproducing it quickly under pressure is another. The special case alone is the kind of detail that slips away if you have not practiced it recently.

Spaced repetition locks both halves into long-term memory. You practice the maximum formula, the sliding window loop, and the special case check independently until each one flows out without hesitation. When you encounter a problem that mixes greedy reasoning with windowing, you recognize the shape immediately and know exactly what to write.

Related posts

• Two Sum II - Two pointer pattern on sorted arrays
• Sliding Window Maximum - Another sliding window technique
• 3Sum Closest - Sorted array with two pointers

CodeBricks breaks Moving Stones Until Consecutive II into its greedy endpoint and sliding window building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a problem combining sorting, windows, and edge cases shows up in your interview, you do not hesitate. You just write it.