How to Solve Moving Stones Until Consecutive II

To solve Moving Stones Until Consecutive II, first sort the stones and apply a sliding window to find the minimum moves required to cluster them consecutively. The maximum moves come from moving endpoint stones strategically, considering gaps at the edges. This approach combines array sorting, gap calculations, and running state updates to ensure efficient computation of both minimum and maximum moves.

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

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.

How GhostInterview Helps

• GhostInterview guides you through identifying endpoint stones and their impact on minimal and maximal moves.
• It simulates sliding window checks for different windows to compute minimum moves efficiently.
• The tool visualizes gap loss scenarios to ensure maximum moves are correctly calculated.

Topic Pages

• Array
• Math
• Sliding Window
• Sorting

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.