Moving Stones Until Consecutive II

The problem is asking us to find both the minimum and maximum number of moves required to arrange the stones in consecutive positions. Here’s an approach to solve this problem:

  1. Sort the Stones: First, we sort the stones to determine their relative positions.
  2. Calculate Maximum Moves: The maximum number of moves will be the maximum of moving the leftmost or the rightmost stones, minus the number of stones already in place.
  3. Calculate Minimum Moves: We’ll iterate through the stones and use a sliding window approach to calculate the minimum moves needed.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def numMovesStonesII(self, stones: List[int]) -> List[int]:
        stones.sort()
        n = len(stones)
        
        # Calculate the maximum moves
        max_moves = max(stones[-1] - stones[1] - n + 2, stones[-2] - stones[0] - n + 2)

        # Initialize the variables for calculating minimum moves
        min_moves = max_moves
        j = 0

        # Sliding window to calculate minimum moves
        for i in range(n):
            while stones[i] - stones[j] >= n:
                j += 1
            if i - j + 1 == n - 1 and stones[i] - stones[j] == n - 2:
                min_moves = min(min_moves, 2)
            else:
                min_moves = min(min_moves, n - (i - j + 1))

        return [min_moves, max_moves]

Explanation:

  • Calculate Maximum Moves: The maximum number of moves is determined by moving the leftmost stones to the rightmost empty positions, or vice versa, minus the number of stones already in place.
  • Sliding Window: We use a sliding window to find the minimum moves. If the current window contains n-1 stones, and the difference between the maximum and minimum is n-2, then it takes two moves to fill the gap. Otherwise, it will take n minus the number of stones in the current window to make them consecutive.
  • Return the Result: The final result will be an array containing the minimum and maximum number of moves.

This code will handle all the constraints and provide the correct result for the given problem.