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]
Solution:
Let's play the game for a while.
First of all, we should put the stones in the right positions, otherwise this game won't be a playable fun game.
For maximum it is just the sum of the gaps between each stone. We can move the left boundary stone next to the right boundary stone, then move right boundary stone next to the left boundary stone, so on and so forth. Each move shrinks the total length by one. But if we take the 1st stone then we cannot count the gaps between 1st and 2nd stone. Similarly if we take the last stone then we cannot count the gaps between last and 2nd last stone. Thus we need to take the maximum of these two cases.
Next let's work on the minimum number of moves. For the first move, let's pick up the stone from the side that will eliminate more empty spaces after moving, a reasonable choice. Where should the stone be put down? There are many choices which all makes sense, but those positions should be somewhere in the range with most dense stone populations. That tuition leads us to a mathematical imagination for how the end game should look like.
For minimum number of moves, the final arrangement will be of the form [a, a+1, a+2, ... a+L-1] for L stones for some 'a'. The possible values of 'a' are all the stone positions in the given input array. The reason a is at stone position is because, if it is not at stone position, we can move the range to [a+1, a+2, ... a+L], which didn't lost a stone at left boundary, but could possibly included a new stone at the right boundary. More stone in the range is a favorable situation. We can keep doing this until a is at the next stone position. The right boundary a+L-1 could be at either stone position or empty position.
For each possible 'a', check how many positions (from a to a+L-1) already have stones. We need to fill in the missing remaining positions. Thus if there are K missing positions we need K moves to fill them. Compute K for each value of 'a' and take their minimum.
To achieve the goal, we can use sliding window. The window initially contains 2 stones. The stones in the window exclude the right boundary. We expand the window one stone interval if the positions inside the window can not hold L stones, otherwise register a min move count, then shrink the window one stone interval.
When register a min move count, there are 2 conditions:
First of all, we should put the stones in the right positions, otherwise this game won't be a playable fun game.
For maximum it is just the sum of the gaps between each stone. We can move the left boundary stone next to the right boundary stone, then move right boundary stone next to the left boundary stone, so on and so forth. Each move shrinks the total length by one. But if we take the 1st stone then we cannot count the gaps between 1st and 2nd stone. Similarly if we take the last stone then we cannot count the gaps between last and 2nd last stone. Thus we need to take the maximum of these two cases.
Next let's work on the minimum number of moves. For the first move, let's pick up the stone from the side that will eliminate more empty spaces after moving, a reasonable choice. Where should the stone be put down? There are many choices which all makes sense, but those positions should be somewhere in the range with most dense stone populations. That tuition leads us to a mathematical imagination for how the end game should look like.
For minimum number of moves, the final arrangement will be of the form [a, a+1, a+2, ... a+L-1] for L stones for some 'a'. The possible values of 'a' are all the stone positions in the given input array. The reason a is at stone position is because, if it is not at stone position, we can move the range to [a+1, a+2, ... a+L], which didn't lost a stone at left boundary, but could possibly included a new stone at the right boundary. More stone in the range is a favorable situation. We can keep doing this until a is at the next stone position. The right boundary a+L-1 could be at either stone position or empty position.
For each possible 'a', check how many positions (from a to a+L-1) already have stones. We need to fill in the missing remaining positions. Thus if there are K missing positions we need K moves to fill them. Compute K for each value of 'a' and take their minimum.
To achieve the goal, we can use sliding window. The window initially contains 2 stones. The stones in the window exclude the right boundary. We expand the window one stone interval if the positions inside the window can not hold L stones, otherwise register a min move count, then shrink the window one stone interval.
When register a min move count, there are 2 conditions:
- There is only one empty position in the sliding window. In that case, we have to move the right boundary stone to complete the game. We don't move the left boundary stone to complete the game, because in the next iteration, when we shrink the sliding window, that case will be covered. When we move the right boundary stone to finish the game, we need to make sure the empty position is not next to the right boundary.
- There are more than one empty positions in the sliding window. In that case, we know there are at least 2 stones outside the sliding window. We can use 1 stone to fill the empty position next to the right boundary of the sliding window, so that we won't get into condition 1 in later moves.
import java.util.*;
class Solution {
public static void main(String...args) {
int[] pos = new int[]{7,4,9};
int[] ans = maxmin(pos);
System.out.println("[" + ans[0] + ", " + ans[1] + "]");
}
public static int[] maxmin(int[] pos) {
if(pos.length == 2) {
throw new RuntimeException("more than 3 stones please");
}
int[] ans = new int[2];
Arrays.sort(pos);
ans[0] = min(pos);
ans[1] = max(pos);
return ans;
}
//4 . . 7 . 9
private static int min(int[] pos) {
int l = 0; //sliding window left boundary
int r = 1; //sliding window right boundary
int min = Integer.MAX_VALUE;
int stones = 1;
int gaps = 0;
while(r < pos.length) {
if(pos[r] <= pos[l] + pos.length-1) { //expand sliding window
stones++;
r++;
} else {
gaps = pos.length - stones;
if(gaps == 1 && pos[r - 1] == pos[l] + pos.length - 1 || gaps != 1) {
min = Math.min(min, gaps);
}
l++; //shrink sliding window
stones--;
}
}
gaps = pos.length - stones;
if(gaps == 1 && pos[r - 1] == pos[l] + pos.length - 1 || gaps != 1) {
min = Math.min(min, gaps);
}
return min;
}
//4 . . 7 . 9
private static int max(int[] pos) {
int total = pos[pos.length - 1] - pos[0] + 1; //9 - 4 + 1 = 6
int space = total - pos.length;
//remove 1st interval or last interval
return Math.max(space - (pos[1] - pos[0] - 1), space - (pos[pos.length - 1] - pos[pos.length - 2] - 1));
}
}
class Solution {
public static void main(String...args) {
int[] pos = new int[]{7,4,9};
int[] ans = maxmin(pos);
System.out.println("[" + ans[0] + ", " + ans[1] + "]");
}
public static int[] maxmin(int[] pos) {
if(pos.length == 2) {
throw new RuntimeException("more than 3 stones please");
}
int[] ans = new int[2];
Arrays.sort(pos);
ans[0] = min(pos);
ans[1] = max(pos);
return ans;
}
//4 . . 7 . 9
private static int min(int[] pos) {
int l = 0; //sliding window left boundary
int r = 1; //sliding window right boundary
int min = Integer.MAX_VALUE;
int stones = 1;
int gaps = 0;
while(r < pos.length) {
if(pos[r] <= pos[l] + pos.length-1) { //expand sliding window
stones++;
r++;
} else {
gaps = pos.length - stones;
if(gaps == 1 && pos[r - 1] == pos[l] + pos.length - 1 || gaps != 1) {
min = Math.min(min, gaps);
}
l++; //shrink sliding window
stones--;
}
}
gaps = pos.length - stones;
if(gaps == 1 && pos[r - 1] == pos[l] + pos.length - 1 || gaps != 1) {
min = Math.min(min, gaps);
}
return min;
}
//4 . . 7 . 9
private static int max(int[] pos) {
int total = pos[pos.length - 1] - pos[0] + 1; //9 - 4 + 1 = 6
int space = total - pos.length;
//remove 1st interval or last interval
return Math.max(space - (pos[1] - pos[0] - 1), space - (pos[pos.length - 1] - pos[pos.length - 2] - 1));
}
}
The time complexity for sorting is O(NlogN), the space complexity is O(1).
