#1040

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Moving Stones Until Consecutive II

Determine the minimum and maximum moves to make stones consecutive using sliding window and endpoint adjustments efficiently.

array math sliding window sorting

Problem Statement

You are given an array stones representing unique positions of stones on the X-axis. Each move allows you to pick an endpoint stone—one at the smallest or largest position—and move it to an unoccupied position such that it is no longer an endpoint. The goal is to minimize and maximize the number of moves needed to arrange the stones into consecutive positions.

A move is legal only if it transforms an endpoint stone into a non-endpoint stone. The game ends when all stones occupy consecutive positions, and no further moves are possible. Your task is to return an array [minimumMoves, maximumMoves] indicating the least and most moves required to complete the game.

Examples

Example 1

Input: stones = [7,4,9]

Output: [1,2]

We can move 4 -> 8 for one move to finish the game. Or, we can move 9 -> 5, 4 -> 6 for two moves to finish the game.

Example 2

Input: stones = [6,5,4,3,10]

Output: [2,3]

We can move 3 -> 8 then 10 -> 7 to finish the game. Or, we can move 3 -> 7, 4 -> 8, 5 -> 9 to finish the game. Notice we cannot move 10 -> 2 to finish the game, because that would be an illegal move.

Constraints

3 <= stones.length <= 104
1 <= stones[i] <= 109
All the values of stones are unique.

Solution Approach

Sort Stones and Identify Endpoints

Begin by sorting the stones to simplify identification of consecutive sequences. Track the smallest and largest stones as potential endpoints to determine how moves affect the range and gaps.

Sliding Window to Compute Minimum Moves

Use a sliding window over the sorted stones to count how many stones are already inside a window of size equal to the total stones. The minimum moves equal the number of stones outside the best-positioned window, with special handling for near-edge gaps that require two moves instead of one.

Calculate Maximum Moves from Endpoint Gaps

For maximum moves, consider the total gap minus the largest single endpoint gap. Move stones from the far ends one by one, losing either the leftmost or rightmost interval, until all stones become consecutive. This ensures the worst-case scenario is covered.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting takes O(N log N) time. Sliding window for minimum moves runs in O(N). Maximum moves calculation is O(1) after sorting. Space complexity is O(1) if sorting in-place or O(N) otherwise.

What Interviewers Usually Probe

Checks if candidate identifies endpoint stones correctly for both min and max calculations.
Observes whether sliding window correctly counts stones already in place for minimal moves.
Watches for handling edge cases where two moves are needed due to single gaps at ends.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle the special case where exactly one stone is outside a nearly full window.
Miscounting maximum moves by not subtracting the largest endpoint gap properly.
Assuming consecutive stones start from the first or last position without sorting first.

Follow-up variants

Changing the movement rule to allow moving any stone, not just endpoints, affects both min and max computations.
Limiting stone positions to a small range introduces simpler window counting and may reduce complexity.
Extending to 2D positions requires adapting sliding window logic and gap calculations to multiple axes.

FAQ

What is the main strategy for Moving Stones Until Consecutive II?

Sort the stones and use a sliding window to compute minimal moves while calculating gaps at endpoints for maximum moves.

How do I handle edge cases in the sliding window approach?

Specially check if only one stone is outside the ideal window; this often requires two moves instead of one.

Can stones be moved anywhere or only endpoints?

Moves are restricted to endpoint stones. Moving non-endpoints is not allowed and breaks the rules.

What is the time complexity of this solution?

Sorting takes O(N log N), sliding window minimum is O(N), and maximum moves calculation is O(1) after sorting.

Why is the problem categorized under sliding window with running state updates?

Because minimal moves rely on counting stones within moving windows and updating state dynamically as the window shifts.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def numMovesStonesII(self, stones: List[int]) -> List[int]:
        stones.sort()
        mi = n = len(stones)
        mx = max(stones[-1] - stones[1] + 1, stones[-2] - stones[0] + 1) - (n - 1)
        i = 0
        for j, x in enumerate(stones):
            while x - stones[i] + 1 > n:
                i += 1
            if j - i + 1 == n - 1 and x - stones[i] == n - 2:
                mi = min(mi, 2)
            else:
                mi = min(mi, n - (j - i + 1))
        return [mi, mx]

Continue Practicing

#1610 maximum number of visible points #1030 matrix cells in distance order #976 largest perimeter triangle