Skip to content

1040. Moving Stones Until Consecutive II 👎

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  vector<int> numMovesStonesII(vector<int>& stones) {
    const int n = stones.size();
    int minMoves = n;

    ranges::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 = 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)};
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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)};
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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)]