Moving Stones Until Consecutive II

medium sliding window sorting two pointers

Problem

Stones sit at distinct positions on the X-axis. An endpoint stone is one at the smallest or largest position. In one move you pick up an endpoint stone and place it at an unoccupied position so that it is no longer an endpoint. The game ends when the stones occupy n consecutive positions. Return [minimum_moves, maximum_moves].

Inputstones = [1, 2, 5]

Output[1, 1]

Move the stone at 5 to 3 (now [1,2,3]) — one move. Maximum is also 1.

stones (comma-separated)

def num_moves_stones_ii(stones):
    stones.sort()
    n = len(stones)
    # Maximum: slide all but one endpoint into the freed span.
    most = max(stones[-1] - stones[1], stones[-2] - stones[0]) - (n - 2)
    least = n
    left = 0
    for right in range(n):
        while stones[right] - stones[left] + 1 > n:
            left += 1
        inside = right - left + 1
        if inside == n - 1 and stones[right] - stones[left] + 1 == n - 1:
            least = min(least, 2)
        else:
            least = min(least, n - inside)
    return [least, most]

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

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

vector<int> numMovesStonesII(vector<int>& stones) {
    sort(stones.begin(), stones.end());
    int n = stones.size();
    int most = max(stones[n - 1] - stones[1], stones[n - 2] - stones[0]) - (n - 2);
    int least = n, left = 0;
    for (int right = 0; right < n; right++) {
        while (stones[right] - stones[left] + 1 > n) left++;
        int inside = right - left + 1;
        if (inside == n - 1 && stones[right] - stones[left] + 1 == n - 1) {
            least = min(least, 2);
        } else {
            least = min(least, n - inside);
        }
    }
    return { least, most };
}

Explanation

The goal is to end with n stones on n consecutive spots, and we want both the fewest and the most moves to get there. After sorting the positions, the two answers come from two different pieces of reasoning.

For the maximum, the slow way is to move one endpoint inward first, then fill the rest one at a time. The wide gap to cover is either stones[n-1] - stones[1] (ignoring the leftmost) or stones[n-2] - stones[0] (ignoring the rightmost); we take the bigger span minus the n - 2 stones already sitting between the ends.

For the minimum, we slide a window of width n across the sorted positions. For each right end, we push left forward while the span stones[right] - stones[left] + 1 exceeds n. The stones already inside that window can stay, so a window holding inside stones needs roughly n - inside moves.

There is one tricky case: when a window already holds n - 1 stones packed into a span of exactly n - 1 (so the only gap is a single slot at the very edge), you cannot finish in one move — it actually takes 2. The code handles that with a special check.

Example: stones = [1, 2, 5]. The endpoint at 5 slides to 3, giving [1,2,3] in a single move, and the maximum is also 1, so the answer is [1, 1].

Time: O(n log n) Space: O(1)