Skip to content

1674. Minimum Moves to Make Array Complementary 👍

  • Time: $O(n + \texttt{limit})$
  • Space: $O(\texttt{limit})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  int minMoves(vector<int>& nums, int limit) {
    const int n = nums.size();
    int ans = n;
    // delta[i] := the number of moves needed when target goes from i - 1 to i
    vector<int> delta(limit * 2 + 2);

    for (int i = 0; i < n / 2; ++i) {
      const int a = nums[i];
      const int b = nums[n - 1 - i];
      --delta[min(a, b) + 1];
      --delta[a + b];
      ++delta[a + b + 1];
      ++delta[max(a, b) + limit + 1];
    }

    // Initially, we need `moves` when the target is 2.
    for (int i = 2, moves = n; i <= limit * 2; ++i) {
      moves += delta[i];
      ans = min(ans, moves);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public int minMoves(int[] nums, int limit) {
    final int n = nums.length;
    int ans = n;
    // delta[i] := the number of moves needed when target goes from i - 1 to i
    int[] delta = new int[limit * 2 + 2];

    for (int i = 0; i < n / 2; ++i) {
      final int a = nums[i];
      final int b = nums[n - 1 - i];
      --delta[Math.min(a, b) + 1];
      --delta[a + b];
      ++delta[a + b + 1];
      ++delta[Math.max(a, b) + limit + 1];
    }

    // Initially, we need `moves` when the target is 2.
    for (int i = 2, moves = n; i <= limit * 2; ++i) {
      moves += delta[i];
      ans = Math.min(ans, moves);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def minMoves(self, nums: list[int], limit: int) -> int:
    n = len(nums)
    ans = n
    # delta[i] := the number of moves needed when target goes from i - 1 to i
    delta = [0] * (limit * 2 + 2)

    for i in range(n // 2):
      a = nums[i]
      b = nums[n - 1 - i]
      delta[min(a, b) + 1] -= 1
      delta[a + b] -= 1
      delta[a + b + 1] += 1
      delta[max(a, b) + limit + 1] += 1

    # Initially, we need `moves` when the target is 2.
    moves = n
    for i in range(2, limit * 2 + 1):
      moves += delta[i]
      ans = min(ans, moves)

    return ans