Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Moving Stones Until Consecutive II solution and explanation

MediumArrayMathSortingTwo Pointers6 min read59.4% acceptanceUpdated 9 Apr 2026
Asked atMeta
Practise Moving Stones Until Consecutive II
52:44
1040. Moving Stones Until Consecutive II (Leetcode Medium)Programming Live with Larry · 52:44 · 1K viewsWatch on YouTube
9 more videos on this problem
  1. 1040. Moving Stones Until Consecutive II (Leetcode Medium)Programming Live with Larry · 52:44 · 1K views
  2. leetCode 1040 - Moving Stones Until Consecutive II | JSer - algorithm & JavaScriptJSer · 45:20 · 1K views
  3. Moving Stones Until Consecutive II || LeetCodeSiddharth Nagaych · 29:30 · 970 views
  4. 猩猩的乐园 Leetcode1040 Moving Stones Until Consecutive II猩猩的乐园 · 14:24 · 463 views
  5. Moving Stones Until Consecutive II, Medium, LeetCode 1040 (Part 1)H William Polenz · 41:54 · 303 views
  6. Moving Stones Until Consecutive II, Medium, LeetCode 1040 (Part 3)H William Polenz · 1:25:28 · 113 views
  7. LeetCode 1040: Moving Stones Until Consecutive IIAlitaCode · 28:12 · 90 views
  8. Moving Stones Until Consecutive II, Medium, LeetCode 1040 (Part 2)H William Polenz · 2:47:36 · 74 views
  9. LeetCode 1040: Moving Stones Until Consecutive IIAlitaCode · 26:14 · 33 views
  10. No Sound Leetcode 1040: Moving Stones Until Consecutive IIExtremeProgrammer · 3:16 · 23 views

The problem

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 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, and
  • answer[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 <= 104
  • 1 <= stones[i] <= 109
  • All the values of stones are 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.

from typing import List

def numMovesStonesII(stones: List[int]) -> List[int]:
    stones.sort()
    numStones = len(stones)
    max_moves = stones[-1] - stones[0] + 1 - numStones
    max_moves -= min(stones[-1] - stones[-2] - 1, stones[1] - stones[0] - 1)

    min_moves = numStones
    i = 0
    for j in range(numStones):
        while stones[j] - stones[i] + 1 > numStones:
            i += 1
        already_placed = j - i + 1
        if already_placed == numStones - 1 and stones[j] - stones[i] + 1 == numStones - 1:
            min_moves = min(min_moves, 2)
        else:
            min_moves = min(min_moves, numStones - already_placed)

    return [min_moves, max_moves]
import java.util.Arrays;

class Solution {
    public int[] numMovesStonesII(int[] stones) {
        Arrays.sort(stones);
        int numStones = stones.length;
        int max_moves = stones[numStones - 1] - stones[0] + 1 - numStones;
        max_moves -= Math.min(stones[numStones - 1] - stones[numStones - 2] - 1, stones[1] - stones[0] - 1);

        int min_moves = numStones;
        int i = 0;
        for (int j = 0; j < numStones; ++j) {
            while (stones[j] - stones[i] + 1 > numStones) i++;
            int already_placed = j - i + 1;
            if (already_placed == numStones - 1 && stones[j] - stones[i] + 1 == numStones - 1) {
                min_moves = Math.min(min_moves, 2);
            } else {
                min_moves = Math.min(min_moves, numStones - already_placed);
            }
        }

        return new int[]{min_moves, max_moves};
    }
}
#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> numMovesStonesII(std::vector<int>& stones) {
    std::sort(stones.begin(), stones.end());
    int numStones = stones.size();
    int max_moves = stones[numStones - 1] - stones[0] + 1 - numStones;
    max_moves -= std::min(stones[numStones - 1] - stones[numStones - 2] - 1,
                         stones[1] - stones[0] - 1);

    int min_moves = numStones;
    int i = 0;
    for (int j = 0; j < numStones; ++j) {
        while (stones[j] - stones[i] + 1 > numStones) i++;
        // Number of stones in the current window
        int already_placed = j - i + 1;
        if (already_placed == numStones - 1 &&  stones[j] - stones[i] + 1 == numStones - 1) {
            min_moves = std::min(min_moves, 2);
        } else {
            min_moves = std::min(min_moves, numStones - already_placed);
        }
    }

    return {min_moves, max_moves};
}
function numMovesStonesII(stones) {
    stones.sort((a, b) => a - b);
    const numStones = stones.length;
    let max_moves = stones[numStones - 1] - stones[0] + 1 - numStones;
    max_moves -= Math.min(stones[numStones - 1] - stones[numStones - 2] - 1, stones[1] - stones[0] - 1);

    let min_moves = numStones;
    let i = 0;
    for (let j = 0; j < numStones; j++) {
        while (stones[j] - stones[i] + 1 > numStones) i++;
        const already_placed = j - i + 1;
        if (already_placed === numStones - 1 && stones[j] - stones[i] + 1 === numStones - 1) {
            min_moves = Math.min(min_moves, 2);
        } else {
            min_moves = Math.min(min_moves, numStones - already_placed);
        }
    }

    return [min_moves, max_moves];
}
#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int* numMovesStonesII(int* stones, int stonesSize, int* returnSize) {
    qsort(stones, stonesSize, sizeof(int), compare);
    int numStones = stonesSize;
    int* result = (int*)malloc(2 * sizeof(int));
    result[0] = result[1] = 0;

    int max_moves = stones[numStones - 1] - stones[0] + 1 - numStones;
    max_moves -= fmin(stones[numStones - 1] - stones[numStones - 2] - 1,
                      stones[1] - stones[0] - 1);

    int min_moves = numStones;
    for (int i = 0, j = 0; i < numStones; i++) {
        while (j < numStones && stones[j] - stones[i] + 1 <= numStones) j++;
        int already_placed = j - i;
        if (already_placed == numStones - 1 && stones[j - 1] - stones[i] + 1 == numStones - 1) // corner case
            min_moves = fmin(min_moves, 2);
        else
            min_moves = fmin(min_moves, numStones - already_placed);
    }

    result[0] = min_moves;
    result[1] = max_moves;
    *returnSize = 2;
    return result;
}
using System;

public class Solution {
    public int[] NumMovesStonesII(int[] stones) {
        Array.Sort(stones);
        int numStones = stones.Length;
        int max_moves = stones[numStones - 1] - stones[0] + 1 - numStones;
        max_moves -= Math.Min(stones[numStones - 1] - stones[numStones - 2] - 1, stones[1] - stones[0] - 1);

        int min_moves = numStones;
        int i = 0;
        for (int j = 0; j < numStones; j++) {
            while (stones[j] - stones[i] + 1 > numStones) i++;
            int already_placed = j - i + 1;
            if (already_placed == numStones - 1 && stones[j] - stones[i] + 1 == numStones - 1) {
                min_moves = Math.Min(min_moves, 2);
            } else {
                min_moves = Math.Min(min_moves, numStones - already_placed);
            }
        }

        return new int[] { min_moves, max_moves };
    }
}

In the Python solution, the sorted list allows for a simple implementation of the minimum and maximum moves calculation using a sliding window approach. Python's capabilities for list manipulation and built-in functions make this solution concise and effective.

Complexity

Time Complexity: O(n log n) because of sorting. Space Complexity: O(1), as it operates in-place on constant sized additional space.

Try this approach in the editor

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.

def numMovesStonesII(stones):
    stones.sort()
    n = len(stones)
    total_gap = stones[-1] - stones[0] + 1 - n
    left_gap = stones[1] - stones[0] - 1
    right_gap = stones[-1] - stones[-2] - 1
    max_moves = total_gap - min(left_gap, right_gap)

    min_moves = n
    i = 0
    for j in range(n):
        while stones[j] - stones[i] + 1 > n:
            i += 1
        already_placed = j - i + 1
        if already_placed == n - 1 and stones[j] - stones[i] + 1 == n - 1:
            min_moves = min(min_moves, 2)
        else:
            min_moves = min(min_moves, n - already_placed)

    return [min_moves, max_moves]
import java.util.Arrays;

class Solution {
    public int[] numMovesStonesII(int[] stones) {
        Arrays.sort(stones);
        int total_gaps = stones[stones.length - 1] - stones[0] + 1 - stones.length;
        int left_gap = stones[1] - stones[0] - 1;
        int right_gap = stones[stones.length - 1] - stones[stones.length - 2] - 1;
        int max_moves = total_gaps - Math.min(left_gap, right_gap);

        int min_moves = stones.length;
        int i = 0;
        for (int j = 0; j < stones.length; j++) {
            while (i < stones.length && stones[j] - stones[i] + 1 > stones.length) i++;
            int already_placed = j - i + 1;
            if (already_placed == stones.length - 1 && stones[j] - stones[i] + 1 == stones.length - 1) {
                min_moves = Math.min(min_moves, 2);
            } else {
                min_moves = Math.min(min_moves, stones.length - already_placed);
            }
        }

        return new int[] {min_moves, max_moves};
    }
}
#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> numMovesStonesII(std::vector<int>& stones) {
    int n = stones.size();
    std::sort(stones.begin(), stones.end());
    int total_gap = stones[n - 1] - stones[0] + 1 - n;
    int left_gap = stones[1] - stones[0] - 1;
    int right_gap = stones[n - 1] - stones[n - 2] - 1;
    int max_moves = total_gap - std::min(left_gap, right_gap);

    int min_moves = n;
    for (int i = 0, j = 0; i < n; ++i) {
        while (j < n && stones[j] - stones[i] + 1 <= n) j++;
        int already_placed = j - i;
        if (already_placed == n - 1 && stones[j - 1] - stones[i] + 1 == n - 1) {
            min_moves = std::min(min_moves, 2);
        } else {
            min_moves = std::min(min_moves, n - already_placed);
        }
    }

    return {min_moves, max_moves};
}
function numMovesStonesII(stones) {
    stones.sort((a, b) => a - b);
    let n = stones.length;
    let total_gap = stones[n - 1] - stones[0] + 1 - n;
    let left_gap = stones[1] - stones[0] - 1;
    let right_gap = stones[n - 1] - stones[n - 2] - 1;
    let max_moves = total_gap - Math.min(left_gap, right_gap);

    let min_moves = n;
    let i = 0;
    for (let j = 0; j < n; ++j) {
        while (i < n && stones[j] - stones[i] + 1 > n) i++;
        let already_placed = j - i + 1;
        if (already_placed === n - 1 && stones[j] - stones[i] + 1 === n - 1) {
            min_moves = Math.min(min_moves, 2);
        } else {
            min_moves = Math.min(min_moves, n - already_placed);
        }
    }

    return [min_moves, max_moves];
}
#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int* numMovesStonesII(int* stones, int stonesSize, int* returnSize) {
    qsort(stones, stonesSize, sizeof(int), compare);
    int left_gap = stones[1] - stones[0] - 1;
    int right_gap = stones[stonesSize - 1] - stones[stonesSize - 2] - 1;
    int total_gap_without_endpoints = stones[stonesSize - 1] - stones[0] + 1 - stonesSize;
    int max_moves = total_gap_without_endpoints - (left_gap < right_gap ? left_gap : right_gap);

    int min_moves = stonesSize;
    for (int start = 0, j = 0; start < stonesSize; start++) {
        while (j < stonesSize && stones[j] - stones[start] + 1 <= stonesSize) j++;
        int already_placed = j - start;
        if(already_placed == stonesSize - 1 && stones[j - 1] - stones[start] + 1 == stonesSize - 1) // corner case
            min_moves = min_moves <= 2 ? min_moves : 2;
        else
            min_moves = min_moves <= stonesSize - already_placed ? min_moves : stonesSize - already_placed;
    }

    int* result = (int*)malloc(sizeof(int) * 2);
    result[0] = min_moves;
    result[1] = max_moves;
    *returnSize = 2;
    return result;
}
public class Solution {
    public int[] NumMovesStonesII(int[] stones) {
        Array.Sort(stones);
        int total_gaps = stones[stones.Length - 1] - stones[0] + 1 - stones.Length;
        int left_gap = stones[1] - stones[0] - 1;
        int right_gap = stones[stones.Length - 1] - stones[stones.Length - 2] - 1;
        int max_moves = total_gaps - Math.Min(left_gap, right_gap);

        int min_moves = stones.Length;
        int i = 0;
        for (int j = 0; j < stones.Length; j++) {
            while (i < stones.Length && stones[j] - stones[i] + 1 > stones.Length) i++;
            int already_placed = j - i + 1;
            if (already_placed == stones.Length - 1 && stones[j] - stones[i] + 1 == stones.Length - 1) {
                min_moves = Math.Min(min_moves, 2);
            } else {
                min_moves = Math.Min(min_moves, stones.Length - already_placed);
            }
        }

        return new int[] {min_moves, max_moves};
    }
}

Python parse utilizes built-ins efficiently for analysis over gaps and window expansion, aligning brute-logic with optimization to achieve minimal computational heft.

Complexity

Time Complexity: O(n^2) worst-case from redundant checks. Space Complexity: O(1).

Try this approach in the editor

Approach 3: Default Approach

function numMovesStonesII(stones: number[]): number[] {
    stones.sort((a, b) => a - b);
    const n = stones.length;
    let mi = n;
    const mx = Math.max(stones[n - 1] - stones[1] + 1, stones[n - 2] - stones[0] + 1) - (n - 1);
    for (let i = 0, j = 0; j < n; ++j) {
        while (stones[j] - stones[i] + 1 > n) {
            ++i;
        }
        if (j - i + 1 === n - 1 && stones[j] - stones[i] === n - 2) {
            mi = Math.min(mi, 2);
        } else {
            mi = Math.min(mi, n - (j - i + 1));
        }
    }
    return [mi, mx];
}
func numMovesStonesII(stones []int) []int {
	sort.Ints(stones)
	n := len(stones)
	mi := n
	mx := max(stones[n-1]-stones[1]+1, stones[n-2]-stones[0]+1) - (n - 1)
	i := 0
	for j, x := range stones {
		for x-stones[i]+1 > n {
			i++
		}
		if j-i+1 == n-1 && stones[j]-stones[i] == n-2 {
			mi = min(mi, 2)
		} else {
			mi = min(mi, n-(j-i+1))
		}
	}
	return []int{mi, mx}
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Sliding Window and Greedy Approach

Time Complexity: O(n log n) because of sorting. Space Complexity: O(1), as it operates in-place on constant sized additional space.

Brute Force with Optimization

Time Complexity: O(n^2) worst-case from redundant checks. Space Complexity: O(1).

Default Approach–

Complexity analysis

ApproachTimeSpaceWhen to Use
Brute Force with OptimizationO(n^2)O(1)Good for understanding the problem by testing every possible consecutive window.
Sliding Window and GreedyO(n log n)O(1)Best practical solution after sorting. Efficiently finds the largest valid window using two pointers.

Frequently asked questions

Is Moving Stones Until Consecutive II easy or hard?

Moving Stones Until Consecutive II is rated Medium on LeetCode. The challenge comes from recognizing the sliding window pattern and handling the special edge case for minimum moves. Once the greedy insight is clear, the implementation is relatively short.

Moving Stones Until Consecutive II Python/Java solution

Most implementations follow the same pattern: sort the array, compute maximum moves using gap calculations, and compute minimum moves using a sliding window. This logic translates directly across Python, Java, C++, C, and JavaScript with identical time complexity of O(n log n).

How to solve Moving Stones Until Consecutive II in O(n)?

After sorting, the core logic for the minimum moves runs in O(n) using a sliding window. Two pointers maintain the largest window where stones[right] - stones[left] + 1 <= n. The stones outside this window represent the moves needed, with a special case when n-1 stones fit but require two moves due to endpoint rules.

What is the best approach for Moving Stones Until Consecutive II?

The optimal solution uses sorting followed by a sliding window with a greedy calculation. Sorting the stones allows a two-pointer window to track the largest group that already fits within a range of size n. The minimum moves come from stones outside this window, while the maximum moves are derived from the boundary gaps. The total complexity is O(n log n) due to sorting.

Is Moving Stones Until Consecutive II asked at Google/Amazon/Meta?

This problem type appears in interviews at large tech companies because it combines greedy reasoning, sorting, and two-pointer techniques. Variants involving intervals, sliding windows, and gap counting are commonly discussed in companies like Google, Amazon, and Meta.

What data structure is used in Moving Stones Until Consecutive II?

The solution primarily uses an array combined with sorting and a two-pointer sliding window. No advanced data structures are required. The algorithm relies on calculating gaps between sorted positions and maintaining a moving window over the array.

What is the time complexity of Moving Stones Until Consecutive II?

The optimal algorithm runs in O(n log n) time because the stone positions must be sorted first. After sorting, a sliding window with two pointers scans the array in linear time O(n). Space complexity remains O(1) since the computation uses only a few variables.

Comments

Next problem · similarMinimum Number of Operations to Make Array ContinuousHard
Now write it yourselfClose this page and solve Moving Stones Until Consecutive II in the editor, without looking.
Practise Moving Stones Until Consecutive II