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)]