Skip to content

1674. Minimum Moves to Make Array Complementary

Description

You are given an integer array nums of even length n and an integer limit. In one move, you can replace any integer from nums with another integer between 1 and limit, inclusive.

The array nums is complementary if for all indices i (0-indexed), nums[i] + nums[n - 1 - i] equals the same number. For example, the array [1,2,3,4] is complementary because for all indices i, nums[i] + nums[n - 1 - i] = 5.

Return the minimum number of moves required to make nums complementary.

 

Example 1:

Input: nums = [1,2,4,3], limit = 4
Output: 1
Explanation: In 1 move, you can change nums to [1,2,2,3] (underlined elements are changed).
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
Therefore, nums[i] + nums[n-1-i] = 4 for every i, so nums is complementary.

Example 2:

Input: nums = [1,2,2,1], limit = 2
Output: 2
Explanation: In 2 moves, you can change nums to [2,2,2,2]. You cannot change any number to 3 since 3 > limit.

Example 3:

Input: nums = [1,2,1,2], limit = 2
Output: 0
Explanation: nums is already complementary.

 

Constraints:

  • n == nums.length
  • 2 <= n <= 105
  • 1 <= nums[i] <= limit <= 105
  • n is even.

Solutions

Solution 1: Difference Array

Assume that in the final array, the sum of the pair \(\textit{nums}[i]\) and \(\textit{nums}[n-i-1]\) is \(s\).

Let's denote \(x\) as the smaller value between \(\textit{nums}[i]\) and \(\textit{nums}[n-i-1]\), and \(y\) as the larger value.

For each pair of numbers, we have the following scenarios:

  • If no replacement is needed, then \(x + y = s\).
  • If one replacement is made, then \(x + 1 \le s \le y + \textit{limit}\).
  • If two replacements are made, then \(2 \le s \le x\) or \(y + \textit{limit} + 1 \le s \le 2 \times \textit{limit}\).

That is:

  • In the range \([2,..x]\), \(2\) replacements are needed.
  • In the range \([x+1,..x+y-1]\), \(1\) replacement is needed.
  • At \([x+y]\), no replacement is needed.
  • In the range \([x+y+1,..y + \textit{limit}]\), \(1\) replacement is needed.
  • In the range \([y + \textit{limit} + 1,..2 \times \textit{limit}]\), \(2\) replacements are needed.

We enumerate each pair of numbers and use a difference array to update the number of replacements needed in different ranges for each pair.

Finally, we find the minimum value among the prefix sums from index \(2\) to \(2 \times \textit{limit}\), which is the minimum number of replacements needed.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array \(\textit{nums}\).

Similar problems:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        d = [0] * (2 * limit + 2)
        n = len(nums)
        for i in range(n // 2):
            x, y = nums[i], nums[-i - 1]
            if x > y:
                x, y = y, x
            d[2] += 2
            d[x + 1] -= 2
            d[x + 1] += 1
            d[x + y] -= 1
            d[x + y + 1] += 1
            d[y + limit + 1] -= 1
            d[y + limit + 1] += 2
        return min(accumulate(d[2:]))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minMoves(int[] nums, int limit) {
        int[] d = new int[2 * limit + 2];
        int n = nums.length;
        for (int i = 0; i < n / 2; ++i) {
            int x = Math.min(nums[i], nums[n - i - 1]);
            int y = Math.max(nums[i], nums[n - i - 1]);
            d[2] += 2;
            d[x + 1] -= 2;
            d[x + 1] += 1;
            d[x + y] -= 1;
            d[x + y + 1] += 1;
            d[y + limit + 1] -= 1;
            d[y + limit + 1] += 2;
        }
        int ans = n;
        for (int i = 2, s = 0; i < d.length; ++i) {
            s += d[i];
            ans = Math.min(ans, s);
        }
        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
26
27
class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        int n = nums.size();
        int d[limit * 2 + 2];
        memset(d, 0, sizeof(d));
        for (int i = 0; i < n / 2; ++i) {
            int x = nums[i], y = nums[n - i - 1];
            if (x > y) {
                swap(x, y);
            }
            d[2] += 2;
            d[x + 1] -= 2;
            d[x + 1] += 1;
            d[x + y] -= 1;
            d[x + y + 1] += 1;
            d[y + limit + 1] -= 1;
            d[y + limit + 1] += 2;
        }
        int ans = n;
        for (int i = 2, s = 0; i <= limit * 2; ++i) {
            s += d[i];
            ans = min(ans, s);
        }
        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
func minMoves(nums []int, limit int) int {
    n := len(nums)
    d := make([]int, 2*limit+2)
    for i := 0; i < n/2; i++ {
        x, y := nums[i], nums[n-1-i]
        if x > y {
            x, y = y, x
        }
        d[2] += 2
        d[x+1] -= 2
        d[x+1] += 1
        d[x+y] -= 1
        d[x+y+1] += 1
        d[y+limit+1] -= 1
        d[y+limit+1] += 2
    }
    ans, s := n, 0
    for _, x := range d[2:] {
        s += x
        ans = min(ans, s)
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function minMoves(nums: number[], limit: number): number {
    const n = nums.length;
    const d: number[] = Array(limit * 2 + 2).fill(0);
    for (let i = 0; i < n >> 1; ++i) {
        const x = Math.min(nums[i], nums[n - 1 - i]);
        const y = Math.max(nums[i], nums[n - 1 - i]);
        d[2] += 2;
        d[x + 1] -= 2;
        d[x + 1] += 1;
        d[x + y] -= 1;
        d[x + y + 1] += 1;
        d[y + limit + 1] -= 1;
        d[y + limit + 1] += 2;
    }
    let ans = n;
    let s = 0;
    for (let i = 2; i < d.length; ++i) {
        s += d[i];
        ans = Math.min(ans, s);
    }
    return ans;
}

Comments