LeetCode 1040 - Moving Stones Until Consecutive II

The problem gives an array stones representing positions of stones on the X-axis, where each position is unique. The goal is to move the endpoint stones-the stones at the smallest and largest positions-so that eventually all stones occupy consecutive positions on the X-axis.

leetcodemediumarraymathsliding-windowsorting

LeetCode Problem 1040

Difficulty: 🟡 Medium
Topics: Array, Math, Sliding Window, Sorting

Solution

Problem Understanding

The problem gives an array stones representing positions of stones on the X-axis, where each position is unique. The goal is to move the endpoint stones-the stones at the smallest and largest positions-so that eventually all stones occupy consecutive positions on the X-axis. An endpoint stone can only be moved to a position that is not itself an endpoint after the move.

The output is an array [minMoves, maxMoves] where minMoves is the fewest number of moves required to make the stones consecutive, and maxMoves is the largest number of moves possible under the rules.

The key constraints are that there are at least 3 stones and no more than 10,000, and stone positions can be very large, up to 10^9. The array is guaranteed to contain unique positions.

Edge cases to note include stones that are already consecutive, stones with large gaps at either end, or configurations where moving one endpoint first is necessary to allow subsequent moves.

Approaches

The brute-force approach would involve simulating all possible sequences of moving endpoint stones. This involves recursively choosing an endpoint, moving it to every possible valid position, and checking if the stones are consecutive. While this guarantees correctness, it has exponential time complexity because the number of sequences grows combinatorially with the number of stones and gaps. For arrays of size 10,000, this is completely infeasible.

The key insight for the optimal approach is to recognize that:

  1. For the maximum moves, we can always move stones from one end inward, always leaving the other end as an endpoint. The maximum moves occur when we move all stones one by one toward the largest possible consecutive segment, which is max(stones) - min(stones) + 1 - len(stones).
  2. For the minimum moves, we can use a sliding window over the sorted stones. We attempt to fit as many stones as possible in a window of size equal to the number of stones. The minimum moves are essentially the number of stones outside this window. Special care is needed for the case where all stones except one are consecutive and a single move cannot create consecutive stones directly; in this case, the minimum moves become 2.

This leads to a linear or linearithmic solution with sorting and sliding window techniques.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Explore all sequences of moves, infeasible for large n
Optimal O(n log n) O(1) Sort and use sliding window to find minimum moves; max moves via formula

Algorithm Walkthrough

  1. Sort the stones in ascending order. Sorting simplifies both the sliding window calculation and finding maximum gaps.
  2. Compute the maximum moves as max(stones) - min(stones) + 1 - len(stones). This counts all empty positions between the smallest and largest stone minus the number of stones already present.
  3. Use a sliding window to compute the minimum moves:
  • Initialize two pointers, left and right, to represent a window of stones.
  • Expand right as long as the number of stones within the window fits in a length of n (the total number of stones).
  • The minimum moves for the current window is n - number of stones in window.
  • Check for the special edge case where the window covers n-1 stones and the total range is n-2 (gap of 1 at one end). This requires 2 moves instead of 1.
  1. Return the result as [minMoves, maxMoves].

Why it works: Sorting guarantees that stones are in order, so we can compute gaps efficiently. The sliding window ensures we find the largest cluster of consecutive or nearly consecutive stones, which minimizes the number of moves. The formula for maximum moves uses the property that the farthest stones can always be moved inward without violating the endpoint rule.

Python Solution

from typing import List

class Solution:
    def numMovesStonesII(self, stones: List[int]) -> List[int]:
        stones.sort()
        n = len(stones)
        maxMoves = max(stones[-1] - stones[1] - n + 2, stones[-2] - stones[0] - n + 2)
        
        minMoves = n
        left = 0
        for right in range(n):
            while stones[right] - stones[left] + 1 > n:
                left += 1
            if right - left + 1 == n - 1 and stones[right] - stones[left] + 1 == n - 1:
                minMoves = min(minMoves, 2)
            else:
                minMoves = min(minMoves, n - (right - left + 1))
        
        return [minMoves, maxMoves]

The implementation first sorts the stones to simplify distance calculations. maxMoves is derived using the outermost gaps. The sliding window computes the largest cluster of stones within a length n, giving minMoves. The special case is handled when one move is not sufficient due to a single gap.

Go Solution

import "sort"

func numMovesStonesII(stones []int) []int {
    sort.Ints(stones)
    n := len(stones)
    maxMoves := max(stones[n-1]-stones[1]-n+2, stones[n-2]-stones[0]-n+2)
    
    minMoves := n
    left := 0
    for right := 0; right < n; right++ {
        for stones[right]-stones[left]+1 > n {
            left++
        }
        if right-left+1 == n-1 && stones[right]-stones[left]+1 == n-1 {
            if minMoves > 2 {
                minMoves = 2
            }
        } else {
            if minMoves > n-(right-left+1) {
                minMoves = n - (right - left + 1)
            }
        }
    }
    
    return []int{minMoves, maxMoves}
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

In Go, sorting and slice operations are analogous to Python. We handle the special edge case explicitly and define a helper function max.

Worked Examples

Example 1: stones = [7,4,9]

Sorted: [4,7,9]

maxMoves = max(9-7-3+2, 7-4-3+2) = max(1, 2) = 2

Sliding window for minMoves: window [4,7] has 2 stones → minMoves = 1

Output: [1,2]

Example 2: stones = [6,5,4,3,10]

Sorted: [3,4,5,6,10]

maxMoves = max(10-4-5+2, 6-3-5+2) = max(3, 0) = 3

Sliding window for minMoves: window [3,4,5,6] has 4 stones → minMoves = 5-4 = 1 but special case applies → minMoves = 2

Output: [2,3]

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates, sliding window is linear O(n)
Space O(1) Constant extra space aside from sorting (in-place)

The time complexity is dominated by sorting, while the sliding window scans the array at most once.

Test Cases

# Provided examples
assert Solution().numMovesStonesII([7,4,9]) == [1,2]  # simple 3-stone case
assert Solution().numMovesStonesII([6,5,4,3,10]) == [2,3]  # larger spread

# Boundary cases
assert Solution().numMovesStonesII([1,2,3]) == [0,0]  # already consecutive
assert Solution().numMovesStonesII([1,3,6]) == [1,3]  # gap in the middle
assert Solution().numMovesStonesII([1,1000000000,2]) == [1,999999997]  # large range

# Edge cases
assert Solution().numMovesStonesII([1,2,4]) == [1,2]  # almost consecutive
assert Solution().numMovesStonesII([1,2,5,6,7]) == [1,4]  # multiple gaps
Test Why
[7,4,9] Basic 3-stone test, checks both min and max moves
[6,5,4,3,10] Spread with larger max endpoint, checks sliding window logic
[1,2,3] Already consecutive, tests zero moves
[1,3,6] Middle gap triggers calculation of min/max moves
[1,1000000000,2] Extremely large range, tests integer handling
[1,2,4] Special case for minimum moves
`[1,2,5,6,