1040. Moving Stones Until Consecutive II #

Problem #

On an infinite number line, the position of the i-th stone is given by stones[i]. Call a stone an endpoint stone if it has the smallest or largest position.

Each turn, 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, ie. the stones are in consecutive positions.

When the game ends, what is the minimum and maximum number of moves that you could have made? Return the answer as an length 2 array: answer = [minimum_moves, maximum_moves]

Example 1:

Input: [7,4,9]
Output: [1,2]
Explanation: 
We can move 4 -> 8 for one move to finish the game.
Or, we can move 9 -> 5, 4 -> 6 for two moves to finish the game.

Example 2:

Input: [6,5,4,3,10]
Output: [2,3]
We can move 3 -> 8 then 10 -> 7 to finish the game.
Or, we can move 3 -> 7, 4 -> 8, 5 -> 9 to finish the game.
Notice we cannot move 10 -> 2 to finish the game, because that would be an illegal move.

Example 3:

Input: [100,101,104,102,103]
Output: [0,0]

Note:

3 <= stones.length <= 10^4
1 <= stones[i] <= 10^9
stones[i] have distinct values.

Problem Summary #

On an infinite number line, the position of the i-th stone is stones[i]. If a stone has the smallest/largest position, then this stone is called an endpoint stone. Each turn, you can pick up an endpoint stone and move it to an unoccupied position so that this stone is no longer an endpoint stone. It is worth noting that if the stones are like stones = [1,2,5], you will not be able to move the endpoint stone at position 5, because no matter where you move it (for example, 0 or 3), this stone will still be an endpoint stone. When you cannot make any more moves, that is, when the positions of these stones are consecutive, the game ends.

To end the game, what are the minimum and maximum number of moves you can make? Return the answer as an array of length 2: answer = [minimum_moves, maximum_moves].

Hints:

3 <= stones.length <= 10^4
1 <= stones[i] <= 10^9
stones[i] have distinct values.

Solution Ideas #

Given an array, the elements in the array represent the coordinates of stones. The task is to move the stones so that these stones’ coordinates eventually form a consecutive sequence of natural numbers. However, it is stipulated that when a stone is an endpoint, it cannot be moved, for example [1,2,5]. 5 is an endpoint, and you cannot move 5 to position 3 or 0, because after the move, this stone would still be an endpoint. Finally output the minimum and maximum number of moves required to arrange all stones into a consecutive sequence of natural numbers.
The key to this problem is how to ensure the restriction that endpoint stones cannot be moved to endpoints again. For example, [5,6,8,9,20], 20 is an endpoint, but 20 can be moved to position 7, ultimately forming the consecutive sequence [5,6,7,8,9]. But for [5,6,7,8,20], in this case 20 cannot be moved to 9. We can only move 8 to 9 first, then move 20 to position 8, ultimately still forming [5,6,7,8,9], but it requires 2 moves. From the above analysis, we can see that endpoint stones can only be moved into gaps in the middle. If there is no gap in the middle, then another stone must first be used to create a gap, and then the endpoint stone can be inserted into the middle, so at least 2 moves are required.

Next consider the extreme cases. First look at the maximum number of moves. The maximum number of moves must be obtained by moving slowly, one position at a time, and moving the maximum number of positions. There are two extreme cases here: move all the numbers in the array to the left endpoint, and move all the numbers in the array to the right endpoint. Move only one position each time. For example, move everything to the right endpoint:

  [3,4,5,6,10] // Initial state, consecutive case
  [4,5,6,7,10] // First step, move 3 to the first place on the right where it can be inserted, namely 7
  [5,6,7,8,10] // Second step, move 4 to the first place on the right where it can be inserted, namely 8
  [6,7,8,9,10] // Third step, move 5 to the first place on the right where it can be inserted, namely 9
    
    
  [1,3,5,7,10] // Initial state, non-consecutive case
  [3,4,5,7,10] // First step, move 1 to the first place on the right where it can be inserted, namely 4
  [4,5,6,7,10] // Second step, move 3 to the first place on the right where it can be inserted, namely 6
  [5,6,7,8,10] // Third step, move 4 to the first place on the right where it can be inserted, namely 8
  [6,7,8,9,10] // Fourth step, move 5 to the first place on the right where it can be inserted, namely 9

The moving process is similar to rolling: move the leftmost stone to the first place on the right where it can be put down. Then keep rolling to the right. Moving all the numbers in the array to the left side is analogous. Comparing the maximum of these two cases gives the maximum number of moves.

Now look at the minimum number of moves. This involves a sliding window. Since we eventually need to form a consecutive sequence of natural numbers, the size of the sliding window is already fixed as n. The window can slide to the right from index 0 of the array. The more numbers this window can contain, the fewer numbers there are outside the window, and therefore the fewest moves are needed to put these numbers into the window. Thus the minimum number of moves can be obtained. There is a relatively tricky point here, which is the restriction in the problem that “an endpoint cannot still be an endpoint after being moved”. For this case, extra judgment is needed. If the current window already has n-1 elements, meaning only one endpoint is outside the window, and the value of the window’s right boundary minus the value of its left boundary is also equal to n-1, this means the numbers inside this window are already consecutive. In this case, for the endpoint to merge into this consecutive sequence, at least 2 moves are needed (as analyzed above).
Pay attention to some boundary cases. If the window slides from left to right and the right boundary of the window has slid to the far right, but the number at the right boundary minus the number at the left boundary is still less than the window size n, this means it has already slid to the end, and we can directly break out. Why has it slid to the end? Because after the array is sorted in ascending order, the numbers get larger toward the right. The current number is a small value, and stones[right]-stones[left] < n is already satisfied. Continuing to move the left boundary to the right will only make stones[left] larger, making it even more less than n. What we need to find is the boundary point where stones[right]-stones[left] >= n, which definitely can no longer be found.

Code #


package leetcode

import (
	"math"
	"sort"
)

func numMovesStonesII(stones []int) []int {
	if len(stones) == 0 {
		return []int{0, 0}
	}
	sort.Ints(stones)
	n := len(stones)
	maxStep, minStep, left, right := max(stones[n-1]-stones[1]-n+2, stones[n-2]-stones[0]-n+2), math.MaxInt64, 0, 0
	for left < n {
		if right+1 < n && stones[right]-stones[left] < n {
			right++
		} else {
			if stones[right]-stones[left] >= n {
				right--
			}
			if right-left+1 == n-1 && stones[right]-stones[left]+1 == n-1 {
				minStep = min(minStep, 2)
			} else {
				minStep = min(minStep, n-(right-left+1))
			}
			if right == n-1 && stones[right]-stones[left] < n {
				break
			}
			left++
		}
	}
	return []int{minStep, maxStep}
}