Watch 10 video solutions for Moving Stones Until Consecutive II, a medium level problem involving Array, Math, Two Pointers. This walkthrough by Programming Live with Larry has 1,911 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
stones = [1,2,5], you cannot move the endpoint stone at position 5, since moving it to any position (such as 0, or 3) 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] <= 109stones are unique.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 | 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. |