Moving Stones Until Consecutive II - Solution & Explanation
Problem Statement
There are some stones in different positions on the X-axis. You are given an integer array stones, the positions of the stones.
Call a stone an endpoint stone if it has the smallest or largest position. In one move, you pick up an endpoint stone and move it to an unoccupied position so that it is no longer an endpoint stone.
- In particular, if the stones are at say,
stones = [1,2,5], you cannot move the endpoint stone at position5, since moving it to any position (such as0, or3) will still keep that stone as an endpoint stone.
The game ends when you cannot make any more moves (i.e., the stones are in three consecutive positions).
Return an integer array answer of length 2 where:
answer[0]is the minimum number of moves you can play, andanswer[1]is the maximum number of moves you can play.
Example 1:
Input: stones = [7,4,9] Output: [1,2] Explanation: 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] Explanation: 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 <= 1041 <= stones[i] <= 109- All the values of
stonesare unique.
Approach Overview
Problem Overview: You are given the positions of stones on a number line. In one move, you can relocate an endpoint stone to any empty position so the stone is no longer an endpoint. The task is to compute the minimum and maximum number of moves required to make all stones occupy consecutive positions.
Approach 1: Brute Force with Optimization (Time: O(n2), Space: O(1))
Start by sorting the array so stone positions are in increasing order. For every possible consecutive segment of length n, count how many stones already fall inside that segment. The remaining stones must be moved. You simulate different windows of size n across the number line and compute the number of stones outside each window. This approach works because the final configuration must be a block of n consecutive integers. Sorting enables efficient range checks, but scanning every candidate window still leads to quadratic behavior in the worst case.
Approach 2: Sliding Window and Greedy (Time: O(n log n), Space: O(1))
Sort the stones first. The maximum moves come from greedily filling gaps between stones while keeping one endpoint fixed. Specifically, compute the total empty spaces between the first and last stones and subtract the larger boundary gap to determine the worst-case moves. For the minimum moves, use a sliding window over the sorted array to find the largest group of stones that already fits inside a window of size n. Two pointers expand and shrink the window while checking stones[right] - stones[left] + 1. The number of stones outside this window represents the moves needed. One edge case occurs when n-1 stones already fit in a window but require two moves due to endpoint constraints. This technique relies on properties of sorted positions and works naturally with two pointers and sorting over an array.
Recommended for interviews: The sliding window and greedy strategy is the expected solution. Interviewers want to see you recognize that consecutive placement forms a window of size n and that sorting enables efficient pointer movement. Mentioning the brute force idea first shows problem exploration, but implementing the optimized sliding window demonstrates strong algorithmic reasoning.
Approach 1: Sliding Window and Greedy Approach
An efficient approach to solve the problem combines a sliding window technique with some greedy insights. First, we sort the stone positions. The main observation is that the smallest window covering the stones consecutively determines the minimum moves required. For the maximum moves, the difference between the maximum and minimum stones minus the number of stones gives the maximum gap, in which we can perform the moves.
The C solution sorts the stones and uses a sliding window to check the number of stones in a consecutive subsequence. It updates the minimum moves with the extra moves needed to achieve a full sequence. It also calculates the maximum moves considering the largest gap at the ends.
Complexity
Time Complexity: O(n log n) due to the sorting step. Space Complexity: O(1) for using constant extra space apart from input and output.
Approach 2: Brute Force with Optimization
This approach tries every possible position for an endpoint stone to minimize or maximize the moves. Although not as efficient as the previous optimized slide window approach, it showcases one straightforward yet computationally intensive method. It tries to place endpoint stones in every potential position keeping them non-endpoints in mind.
In C, this version calculates gaps explicitly, and imposes constraints to limit endpoint becoming one in every choice of moves. Then performs sliding window evaluation for min moves.
Complexity
Time Complexity: O(n^2) in the worst case due to the nested loops probing. Space Complexity: O(1).
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window and Greedy Approach | Time Complexity: O(n log n) due to the sorting step. Space Complexity: O(1) for using constant extra space apart from input and output. |
| Brute Force with Optimization | Time Complexity: O(n^2) in the worst case due to the nested loops probing. Space Complexity: O(1). |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Optimization | O(n^2) | O(1) | Good for understanding the problem by testing every possible consecutive window. |
| Sliding Window and Greedy | O(n log n) | O(1) | Best practical solution after sorting. Efficiently finds the largest valid window using two pointers. |
Video Solution
1040. Moving Stones Until Consecutive II (Leetcode Medium) • Programming Live with Larry • 1,939 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Moving Stones Until Consecutive II easy or hard?
Moving Stones Until Consecutive II Python/Java solution
How to solve Moving Stones Until Consecutive II in O(n)?
What is the best approach for Moving Stones Until Consecutive II?
Is Moving Stones Until Consecutive II asked at Google/Amazon/Meta?
What data structure is used in Moving Stones Until Consecutive II?
What is the time complexity of Moving Stones Until Consecutive II?
Ready to solve this problem?
Practice Moving Stones Until Consecutive II with our built-in code editor and test cases.
Practice on FleetCode