We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Moving Stones Until Consecutive II

Number: 1113

Difficulty: Medium

Paid? No

Companies: Meta

Problem Description

Given an array of unique stone positions on the X-axis, you can move only the endpoint stones (i.e. the stone with the smallest or largest position) to any unoccupied position such that after the move the stone is no longer an endpoint. The objective is to play moves until the stones occupy consecutive positions. Return an array [minMoves, maxMoves] where minMoves is the minimum number of moves required and maxMoves is the maximum number of moves that can be made.

Key Insights

  • First sort the stone positions to work with meaningful intervals.
  • The maximum number of moves is determined by “pushing in” the interval from one end; it can be computed as the larger gap from either the second stone to the last stone or the first stone to the second-to-last stone minus the number of stones already in between.
  • The minimum number of moves can be computed using a sliding window technique to find the largest contiguous group of stones that can already be part of a consecutive sequence.
  • A special edge-case occurs when the stones form nearly a consecutive sequence except for a single gap of size two, in which case 2 moves are required instead of 1.

Space and Time Complexity

Time Complexity: O(n) after sorting, so overall O(n log n) due to the sort. Space Complexity: O(1) extra space (apart from the space used to store the sorted list).

Solution

The solution begins by sorting the stone positions so that the endpoints and gaps can be easily identified.

  1. To compute the maximum number of moves, consider the two possibilities: moving the left endpoint towards the right and the right endpoint towards the left. Specifically, calculate:
    • Option 1: moves = (last stone position - second stone position) - (n - 2)
    • Option 2: moves = (second-to-last stone position - first stone position) - (n - 2) The maximum moves is the larger of these two values.
  2. The minimum moves are determined by a sliding window algorithm. Slide a window over the sorted array where the window size is such that the distance between the current right and left indices is less than n. The number of stones outside the window gives the candidate for moves. However, if the window already holds n-1 stones and the stones are almost consecutive (i.e. the gap is exactly n-2), then the result must be set to 2 moves to handle the edge case. This algorithm carefully checks each possible contiguous segment to guarantee the smallest number of moves needed to achieve consecutive positions.

Code Solutions

# Python solution with detailed comments
def numMovesStonesII(stones):
    # Sort the stone positions to assess intervals and endpoints
    stones.sort()
    n = len(stones)
    
    # Calculate the maximum moves.
    # Option 1: Move the left endpoint inward.
    # Option 2: Move the right endpoint inward.
    max_moves = max(stones[-1] - stones[1], stones[-2] - stones[0]) - (n - 2)
    
    # Calculate the minimum moves using a sliding window approach.
    min_moves = n
    i = 0  # Left pointer for sliding window
    for j in range(n):  # j is the right pointer of the sliding window
        # Expand window until the gap becomes too large (>= n)
        while stones[j] - stones[i] >= n:
            i += 1
        current_window = j - i + 1
        # Special edge-case: when we have n-1 stones in the window and the gap is exactly n-2,
        # we cannot fix the configuration in one move.
        if current_window == n - 1 and stones[j] - stones[i] == n - 2:
            min_moves = min(min_moves, 2)
        else:
            min_moves = min(min_moves, n - current_window)
    
    return [min_moves, max_moves]

# Example usage:
print(numMovesStonesII([7, 4, 9]))  # Output should be [1, 2]
← Back to All Questions