Problem Description

You are given an array stones of length n, where each element represents the position of a stone on the X-axis. Each position is unique and all stones are placed at different integer coordinates.

In one move, you can pick up a stone at position stones[i] and move it to an unoccupied position between the current minimum and maximum positions of all stones (exclusive). That is, you cannot move a stone to a position outside the range defined by the smallest and largest stone positions, nor can you move it to a position already occupied by another stone.

The goal is to make the stones' positions consecutive (i.e., form a sequence of n consecutive integers). You are asked to return two integers:

• The minimum number of moves needed to make the stones consecutive.
• The maximum number of moves needed to make the stones consecutive.

Constraints:

• 1 <= n <= 10⁴
• 0 <= stones[i] <= 10⁹
• All stones[i] are distinct

Thought Process

At first glance, the problem seems to suggest brute-forcing every possible move sequence, but with up to 10,000 stones, that's computationally infeasible. Instead, we notice a few key things:

• Since stones can only be moved within the current min and max, the "range" is fixed for the duration of the process.
• We can only move stones into empty spots between the endpoints, and each move fills exactly one gap.
• Making the stones consecutive is really about filling in all the gaps between the smallest and largest stone positions.

For the maximum number of moves, we can always move stones one at a time from the ends inward, filling in the largest available gaps. For the minimum number of moves, we need to find the "largest cluster" of stones that are already consecutive (or nearly so), and see how few moves it takes to fill the rest.

This suggests using sorting and sliding window techniques for optimization, rather than brute force.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Sort the Stones:
   • Sorting helps us easily identify gaps and work with consecutive ranges.
2. Calculate the Maximum Moves:
   • The maximum number of moves is achieved by always moving the endpoint stones inward, one space at a time, until all stones are consecutive.
   • For n stones, the total number of positions between the endpoints is stones[n-1] - stones[0] + 1. The number of empty positions is stones[n-1] - stones[0] + 1 - n.
   • However, if the gap at one end is smaller (i.e., the second stone is very close to the first, or the second-to-last is close to the last), you cannot always move the endpoint stone directly inward. So, the maximum is the larger of stones[n-2] - stones[0] - (n-2) and stones[n-1] - stones[1] - (n-2).
3. Calculate the Minimum Moves:
   • We want to find the smallest window of size n that contains the most stones. The minimum number of moves is n minus the size of the largest such cluster.
   • We use a sliding window: for each stone, look ahead as far as possible (without exceeding a window of size n-1), and count how many stones are in this window.
   • Special case: If the window contains n-1 stones and is only missing one position at the end (i.e., the gap is exactly n-2), then you need 2 moves (not 1), because you can't move a stone from the end directly into the gap.

We use sorting for O(n log n) time, and a sliding window for O(n) time, making the entire approach efficient.

Example Walkthrough

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

1. Sort Stones: [3, 4, 5, 6, 10]
2. Calculate Maximum Moves:
   • Range: 10 - 3 + 1 = 8
   • Empty positions: 8 - 5 = 3
   • But, check both ends:
     • Left: stones[3] - stones[0] - (n-2) = 6 - 3 - 3 = 0
     • Right: stones[4] - stones[1] - (n-2) = 10 - 4 - 3 = 3
   • Maximum moves: max(0, 3) = 3
3. Calculate Minimum Moves (Sliding Window):
   • Window 1: [3,4,5,6] (positions 3 to 6): 4 stones, 1 missing (positions = 4, so gap = 3, so only 1 missing)
   • Window 2: [4,5,6,10] (positions 4 to 10): 4 stones, gap = 6, missing 2
   • Window 3: [3,4,5,6,10] (positions 3 to 10): 5 stones, gap = 7, missing 2
   • Best window is [3,4,5,6] with 4 stones in a window of size 4, so min moves = 5 - 4 = 1. But since the window is of length 4 and missing one at the end, and the gap is not at the end, we need to check for the special case. Here, since the gap is at the end, we need only 1 move.
4. Result: [1, 3]

Time and Space Complexity

• Brute-force Approach:
  • Would involve trying all permutations of moves, leading to exponential time complexity (O(n!)), which is not feasible for n up to 10⁴.
• Optimized Approach:
  • Sorting the stones: O(n log n)
  • Sliding window to find the minimal moves: O(n)
  • Calculating maximum moves: O(1) after sorting
  • Overall time complexity: O(n log n)
  • Space complexity: O(1) extra (in-place sorting if allowed), or O(n) if not.

Summary

The problem asks us to make stones consecutive with as few and as many moves as possible. By sorting the stones and using a sliding window, we can efficiently determine the minimal moves needed to cluster them, and by considering the largest endpoint gaps, we find the maximal moves. The key insight is to focus on clusters and gaps, rather than simulating every possible move, which leads to an elegant and efficient O(n log n) solution.

Code Implementation

class Solution:
    def numMovesStonesII(self, stones):
        stones.sort()
        n = len(stones)
        max_moves = max(
            stones[-1] - stones[1] - n + 2,
            stones[-2] - stones[0] - n + 2
        )
        min_moves = n
        left = 0
        for right in range(n):
            # Move left pointer to keep window size <= n
            while stones[right] - stones[left] + 1 > n:
                left += 1
            current = right - left + 1
            if current == n - 1 and stones[right] - stones[left] + 1 == n - 1:
                # Special case: need 2 moves instead of 1
                min_moves = min(min_moves, 2)
            else:
                min_moves = min(min_moves, n - current)
        return [min_moves, max_moves]
      

class Solution {
public:
    vector<int> numMovesStonesII(vector<int>& stones) {
        sort(stones.begin(), stones.end());
        int n = stones.size();
        int maxMoves = max(stones[n-2] - stones[0] - n + 2,
                           stones[n-1] - stones[1] - n + 2);
        int minMoves = n;
        int left = 0;
        for (int right = 0; right < n; ++right) {
            while (stones[right] - stones[left] + 1 > n) {
                ++left;
            }
            int current = right - left + 1;
            if (current == n - 1 && stones[right] - stones[left] + 1 == n - 1) {
                minMoves = min(minMoves, 2);
            } else {
                minMoves = min(minMoves, n - current);
            }
        }
        return {minMoves, maxMoves};
    }
};
      

import java.util.Arrays;

class Solution {
    public int[] numMovesStonesII(int[] stones) {
        Arrays.sort(stones);
        int n = stones.length;
        int maxMoves = Math.max(stones[n-2] - stones[0] - n + 2,
                                stones[n-1] - stones[1] - n + 2);
        int minMoves = n;
        int left = 0;
        for (int right = 0; right < n; ++right) {
            while (stones[right] - stones[left] + 1 > n) {
                left++;
            }
            int current = right - left + 1;
            if (current == n - 1 && stones[right] - stones[left] + 1 == n - 1) {
                minMoves = Math.min(minMoves, 2);
            } else {
                minMoves = Math.min(minMoves, n - current);
            }
        }
        return new int[]{minMoves, maxMoves};
    }
}
      

var numMovesStonesII = function(stones) {
    stones.sort((a, b) => a - b);
    const n = stones.length;
    let maxMoves = Math.max(
        stones[n-2] - stones[0] - n + 2,
        stones[n-1] - stones[1] - n + 2
    );
    let minMoves = n;
    let left = 0;
    for (let right = 0; right < n; ++right) {
        while (stones[right] - stones[left] + 1 > n) {
            left++;
        }
        let current = right - left + 1;
        if (current === n - 1 && stones[right] - stones[left] + 1 === n - 1) {
            minMoves = Math.min(minMoves, 2);
        } else {
            minMoves = Math.min(minMoves, n - current);
        }
    }
    return [minMoves, maxMoves];
};