1040. Moving Stones Until Consecutive II

Problem Statement

link: LeetCode.cn LeetCode There are some stones in different positions on the X-axis. You are given an integer array stones, the positions of the stones.

Call a stone an endpoint stone if it has the smallest or largest position. In one move, you pick up an endpoint stone and move it to an unoccupied position so that it is no longer an endpoint stone.

In particular, if the stones are at say, stones = [1,2,5], you cannot move the endpoint stone at position 5, since moving it to any position (such as 0, or 3) will still keep that stone as an endpoint stone. The game ends when you cannot make any more moves (i.e., the stones are in three consecutive positions).

Return an integer array answer of length 2 where:

answer[0] is the minimum number of moves you can play, and answer[1] is the maximum number of moves you can play.

Example:

Input: stones = [7,4,9] Output: [1,2]

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

Constraints: 3 <= stones.length <= 104 1 <= stones[i] <= 109 All the values of stones are unique.

Solution Approach

The solution involves sorting the stones, then calculating the minimum and maximum number of moves needed by sliding a window of size n over the sorted stones to find the optimal placements.

Algorithm

1. Sorting the Stones: First, sort the stones array to arrange the positions in ascending order, which simplifies the process of determining how to move them into consecutive positions.
2. Sliding Window for Minimum Moves: Use a sliding window of size n (where n is the number of stones) to find the minimum number of moves required. The goal is to maximize the number of stones within any subarray of length n and calculate the moves needed to bring the rest into this window.
3. Calculating Maximum Moves: The maximum number of moves is determined by considering how far the stones at the endpoints can be moved inward, ensuring that each move still leaves one of the current endpoints as an endpoint. The formula accounts for moving the stones closest to the endpoints inward as much as possible.

Implement

    class Solution:
    def numMovesStonesII(self, stones: List[int]) -> List[int]:
        n = len(stones)
        stones.sort()
        if stones[-1] - stones[0] + 1 == n:
            return [0, 0]
        ma = max(stones[-2] - stones[0] + 1, stones[-1] - stones[1] + 1) - (n - 1)
        mi = n
        j = 0
        for i in range(n):
            while j + 1 < n and stones[j + 1] - stones[i] + 1 <= n:
                j += 1
            if j - i + 1 == n - 1 and stones[j] - stones[i] + 1 == n - 1:
                mi = min(mi, 2)
            else:
                mi = min(mi, n - (j - i + 1))
        return [mi, ma]

  

    
    

Twitter  facebook  Email