LeetCode Solutions
1040. Moving Stones Until Consecutive II
Time: Space:
class Solution {
public:
vector<int> numMovesStonesII(vector<int>& stones) {
const int n = stones.size();
int minMoves = n;
sort(begin(stones), end(stones));
for (int l = 0, r = 0; r < n; ++r) {
while (stones[r] - stones[l] + 1 > n)
++l;
int alreadyStored = r - l + 1;
if (alreadyStored == n - 1 && stones[r] - stones[l] + 1 == n - 1)
minMoves = min(minMoves, 2);
else
minMoves = min(minMoves, n - alreadyStored);
}
return {minMoves, max(stones[n - 1] - stones[1] - n + 2,
stones[n - 2] - stones[0] - n + 2)};
}
};
class Solution {
public int[] numMovesStonesII(int[] stones) {
final int n = stones.length;
int minMoves = n;
Arrays.sort(stones);
for (int l = 0, r = 0; r < n; ++r) {
while (stones[r] - stones[l] + 1 > n)
++l;
int alreadyStored = r - l + 1;
if (alreadyStored == n - 1 && stones[r] - stones[l] + 1 == n - 1)
minMoves = Math.min(minMoves, 2);
else
minMoves = Math.min(minMoves, n - alreadyStored);
}
return new int[] {
minMoves, Math.max(stones[n - 1] - stones[1] - n + 2, stones[n - 2] - stones[0] - n + 2)};
}
}
class Solution:
def numMovesStonesII(self, stones: List[int]) -> List[int]:
n = len(stones)
minMoves = n
stones.sort()
l = 0
for r, stone in enumerate(stones):
while stone - stones[l] + 1 > n:
l += 1
alreadyStored = r - l + 1
if alreadyStored == n - 1 and stone - stones[l] + 1 == n - 1:
minMoves = 2
else:
minMoves = min(minMoves, n - alreadyStored)
return [minMoves, max(stones[n - 1] - stones[1] - n + 2, stones[n - 2] - stones[0] - n + 2)]