Problem Description

You have stones placed at various positions along the X-axis, represented by an integer array stones containing their positions.

An endpoint stone is defined as a stone at either the smallest or largest position among all stones. In each move, you can pick up an endpoint stone and move it to any unoccupied position, but the new position must ensure the stone is no longer an endpoint.

For example, with stones = [1,2,5]:

• The endpoint stones are at positions 1 (smallest) and 5 (largest)
• If you move the stone at position 5, you cannot place it at positions like 0 or 3 because it would still remain an endpoint stone
• Valid moves would place it between the current minimum and maximum positions

The game continues until no more valid moves can be made, which happens when all stones occupy consecutive positions (like [3,4,5]).

Your task is to find both:

1. The minimum number of moves needed to reach the end state
2. The maximum number of moves possible to reach the end state

Return these two values as an array [minimum_moves, maximum_moves].

The key insight is that the game ends when stones form a consecutive sequence of length n, where n is the total number of stones. The challenge lies in finding the optimal strategy for both minimizing and maximizing the number of moves while respecting the endpoint movement rules.

Intuition

To understand this problem, let's think about what the final state looks like: all stones must be in consecutive positions. If we have n stones, they'll occupy exactly n consecutive positions like [k, k+1, k+2, ..., k+n-1] for some starting position k.

For the maximum moves:

The key observation is that once we move an endpoint stone, it creates a "gap" that we can exploit. To maximize moves, we want to keep the stones spread out as long as possible.

Consider that we can move stones one at a time from one end toward the other. The maximum number of moves depends on how many "empty spaces" exist between the stones initially. If stones span from position a to b, there are b - a + 1 total positions, but only n are occupied, leaving (b - a + 1) - n empty spaces.

However, we need to be careful about which endpoint to move first. Moving the left endpoint gives us access to spaces between stones[1] and stones[-1], while moving the right endpoint gives us spaces between stones[0] and stones[-2]. We choose the direction that gives us more empty spaces: max(stones[-1] - stones[1] + 1, stones[-2] - stones[0] + 1) - (n - 1).

For the minimum moves:

We want to find a "window" of consecutive positions where we already have the most stones placed. This minimizes how many stones need to be moved.

We use a sliding window approach: for each possible window of size n, we count how many stones are already within that window. The stones outside this window need to be moved in. If a window contains k stones, we need n - k moves to bring the remaining stones into consecutive positions.

There's a special edge case: when we have n-1 stones already consecutive (like [1,2,3,5] for 4 stones). In this case, we can't directly place the outlier stone to complete the sequence in one move because it's an endpoint. We need 2 moves: first move one endpoint to create a gap, then move the outlier into position.

This edge case is detected when: j - i + 1 == n - 1 (we have n-1 stones in our window) and stones[j] - stones[i] == n - 2 (these n-1 stones are consecutive).

Learn more about Math, Sorting and Sliding Window patterns.

Solution Approach

The implementation uses sorting and a sliding window technique to solve both parts of the problem.

Step 1: Sort the stones

stones.sort()

First, we sort the stones array to work with positions in ascending order. This makes it easier to identify endpoints and calculate gaps.

Step 2: Calculate maximum moves

mx = max(stones[-1] - stones[1] + 1, stones[-2] - stones[0] + 1) - (n - 1)

For maximum moves, we calculate the empty spaces available when moving stones from either end:

• Moving from the left: spaces between stones[1] and stones[-1] is stones[-1] - stones[1] + 1 positions total
• Moving from the right: spaces between stones[0] and stones[-2] is stones[-2] - stones[0] + 1 positions total
• We subtract (n - 1) because in the final state, n stones occupy exactly n consecutive positions with n-1 gaps between them

Step 3: Calculate minimum moves using sliding window

mi = n = len(stones)
i = 0
for j, x in enumerate(stones):
    while x - stones[i] + 1 > n:
        i += 1

We initialize mi to n (worst case: all stones need to move). We use two pointers i and j to maintain a sliding window:

• The window represents consecutive positions that can hold at most n stones
• stones[j] - stones[i] + 1 gives the span of positions in the current window
• When the span exceeds n, we shrink the window by advancing i

Step 4: Handle the special case

if j - i + 1 == n - 1 and x - stones[i] == n - 2:
    mi = min(mi, 2)

This checks for the edge case where n-1 stones are already consecutive:

• j - i + 1 == n - 1: we have exactly n-1 stones in the window
• x - stones[i] == n - 2: these stones span exactly n-1 positions (they're consecutive)
• In this case, we need exactly 2 moves to complete the sequence

Step 5: Calculate moves for normal cases

else:
    mi = min(mi, n - (j - i + 1))

For each valid window:

• j - i + 1 is the number of stones already in the window
• n - (j - i + 1) is the number of stones that need to be moved into this window
• We track the minimum across all possible windows

Step 6: Return the result

return [mi, mx]

Finally, return both the minimum and maximum number of moves as required.

The algorithm runs in O(n log n) time due to sorting, and the sliding window traversal is O(n). Space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the solution with stones = [1, 2, 5, 8, 10].

Step 1: Sort the array The array is already sorted: [1, 2, 5, 8, 10]

Step 2: Calculate Maximum Moves

• n = 5 stones
• Moving from left: spaces between stones[1] and stones[4] = 10 - 2 + 1 = 9 positions
• Moving from right: spaces between stones[0] and stones[3] = 8 - 1 + 1 = 8 positions
• Maximum empty spaces: max(9, 8) - (5-1) = 9 - 4 = 5 moves

To achieve maximum moves, we'd move stones one by one from position 1 into gaps: 1→3, then 2→4, then 3→6, then 4→7, then 6→9, resulting in consecutive positions [7,8,9,10,11] after 5 moves.

Step 3-5: Calculate Minimum Moves using Sliding Window

We'll examine windows of size at most 5 consecutive positions:

• Window [1,2,5]: spans positions 1-5 (5 positions)

  • Contains 3 stones
  • Regular case: need 5 - 3 = 2 moves

• Window [2,5,8]: spans positions 2-8 (7 positions > 5)

  • Window too large, advance i pointer

• Window [5,8,10]: spans positions 5-10 (6 positions > 5)

  • Window too large, advance i pointer

• Window [8,10]: spans positions 8-10 (3 positions ≤ 5)

  • Contains 2 stones
  • Regular case: need 5 - 2 = 3 moves

The minimum across all windows is 2 moves.

To achieve minimum moves: We can move stones at positions 8 and 10 to positions 3 and 4, resulting in [1,2,3,4,5] with just 2 moves.

Step 6: Return Result Return [2, 5] - minimum of 2 moves and maximum of 5 moves.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n) where n is the length of the stones array.

• The initial sorting operation takes O(n log n) time
• Computing the maximum moves involves constant time operations: O(1)
• The nested loop structure with the sliding window approach takes O(n) time total:
  • The outer loop iterates through all n stones
  • The inner while loop moves the pointer i forward, but each position is visited at most once throughout the entire execution
  • Inside the loops, all operations (comparisons, min calculations) are O(1)
• Overall: O(n log n) + O(1) + O(n) = O(n log n)

Space Complexity: O(1) or O(n) depending on whether we count the sorting space.

• If we use in-place sorting (like Python's Timsort which modifies the input): O(1) auxiliary space
• If we consider the sorting algorithm's space requirements: O(n) in the worst case for Timsort
• Variables used (mi, mx, i, j, x, n) all require constant space: O(1)
• The output list of size 2 is O(1)
• Overall auxiliary space (excluding input): O(1) best case, O(n) worst case depending on sorting implementation

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Special Case Logic

The Pitfall: Many implementations fail to correctly identify or handle the special case where n-1 stones are already consecutive with exactly one gap. The condition stones[j] - stones[i] == n - 2 might seem counterintuitive at first glance.

Why it happens: When you have n-1 stones in consecutive positions, they span exactly n-1 positions (with n-2 gaps between them). For example, with stones [1,2,3,4,6] where n=5:

• Stones at positions 1,2,3,4 are consecutive (4 stones)
• They span positions 1 to 4, which is 4-1=3 gaps between them
• The formula stones[j] - stones[i] gives us 4-1=3, which equals n-2

The Solution: Always verify both conditions for the special case:

# Correct special case check
if right - left + 1 == n - 1 and stone_pos - stones[left] == n - 2:
    min_moves = min(min_moves, 2)

2. Incorrect Maximum Moves Calculation

The Pitfall: A common mistake is to calculate maximum moves without considering both endpoints properly, or forgetting to subtract the final configuration size:

# WRONG: Only considering one side
max_moves = stones[-1] - stones[0] - (n - 1)

# WRONG: Not subtracting the final configuration
max_moves = max(stones[-1] - stones[1], stones[-2] - stones[0])

Why it matters: The maximum moves depend on which endpoint we start moving first. We need to consider both possibilities and take the maximum, then account for the fact that n stones in their final position occupy exactly n consecutive spots.

The Solution:

# CORRECT: Consider both sides and subtract final configuration
max_moves = max(stones[-1] - stones[1] + 1, stones[-2] - stones[0] + 1) - (n - 1)

3. Off-by-One Errors in Window Size Calculation

The Pitfall: Forgetting to add 1 when calculating the span of positions:

# WRONG: Missing +1 for inclusive range
while stones[right] - stones[left] > n:
    left += 1

Why it happens: The span from position a to position b includes both endpoints, so it contains b - a + 1 positions total.

The Solution:

# CORRECT: Include both endpoints in the span calculation
while stones[right] - stones[left] + 1 > n:
    left += 1

4. Not Handling Edge Cases with Small Arrays

The Pitfall: The algorithm might fail for arrays with 2 or 3 stones if not carefully implemented:

# Potential issue with small arrays
if len(stones) == 2:
    # Special handling might be needed

The Solution: The current implementation naturally handles small arrays because:

• The sliding window approach works for any n ≥ 2
• The special case check won't trigger incorrectly for small arrays
• Maximum calculation remains valid

However, it's good practice to test with minimal inputs:

# Test cases to verify:
assert numMovesStonesII([7, 4, 9]) == [1, 2]  # n=3
assert numMovesStonesII([6, 5]) == [1, 1]     # n=2, already consecutive