Minimum Moves to Make Array Complementary

Med

#1536Time: O(n * limit). The outer loop runs `2 * limit` times, and for each iteration, the inner loop runs `n/2` times.Space: O(1), as we only use a few variables to store counts and intermediate values.1 company

Patterns

Prefix Sum

Data structures

Array Hash Table

Companies

CureFit

Prompt

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 <= 10⁵
1 <= nums[i] <= limit <= 10⁵
n is even.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves checking every possible target sum for the pairs (nums[i], nums[n-1-i]). The possible sums range from 2 (by changing both numbers to 1) to 2 * limit (by changing both to limit). For each potential target sum, we calculate the total number of moves required to make all pairs sum up to it. We keep track of the minimum moves found across all target sums.

Algorithm

Initialize minMoves to a very large value, for instance, n (the maximum possible moves).
Iterate through every possible targetSum from 2 to 2 * limit.
For each targetSum, initialize a counter currentMoves to 0.
Iterate through the first half of the array, considering pairs (nums[i], nums[n - 1 - i]).
For each pair (a, b):
- If a + b == targetSum, the cost is 0 moves.
- If a + b != targetSum but the targetSum can be achieved with one change (i.e., targetSum is in the range [1 + min(a, b), limit + max(a, b)]), add 1 to currentMoves.
- Otherwise, two changes are necessary, so add 2 to currentMoves.
After checking all pairs, currentMoves holds the total moves for the current targetSum. Update minMoves = min(minMoves, currentMoves).
After iterating through all possible targetSum values, minMoves will hold the minimum moves required.

Walkthrough

The core idea is to find a targetSum that minimizes the total moves. The targetSum can range from 2 to 2 * limit.

We iterate through each possible targetSum in this range. For each targetSum, we then iterate through all n/2 pairs of elements (a, b) where a = nums[i] and b = nums[n - 1 - i]. For each pair, we calculate the moves needed to make their sum equal to targetSum:

0 moves: if a + b is already equal to targetSum.
1 move: if a + b != targetSum, but we can change just one of the numbers to achieve the targetSum. This is possible if the targetSum is within the range [1 + min(a, b), limit + max(a, b)].
2 moves: if we must change both numbers. This is the case for any targetSum that cannot be achieved with 0 or 1 move.

We sum the moves for all pairs to get the total moves for the current targetSum. The minimum of these totals over all possible targetSums is the answer.

1class Solution {2    public int minMoves(int[] nums, int limit) {3        int n = nums.length;4        int minMoves = n; // Maximum possible moves5 6        for (int targetSum = 2; targetSum <= 2 * limit; targetSum++) {7            int currentMoves = 0;8            for (int i = 0; i < n / 2; i++) {9                int a = nums[i];10                int b = nums[n - 1 - i];11                12                if (a + b == targetSum) {13                    // 0 moves needed14                    continue;15                }16                17                int minVal = Math.min(a, b);18                int maxVal = Math.max(a, b);19                if (targetSum >= 1 + minVal && targetSum <= limit + maxVal) {20                    currentMoves += 1;21                } else {22                    currentMoves += 2;23                }24            }25            minMoves = Math.min(minMoves, currentMoves);26        }27        return minMoves;28    }29}

Complexity

Time

O(n * limit). The outer loop runs `2 * limit` times, and for each iteration, the inner loop runs `n/2` times.

Space

O(1), as we only use a few variables to store counts and intermediate values.

Trade-offs

Pros

Simple to understand and implement.
Requires minimal space.

Cons

The time complexity is very high, making it impractical for the given constraints.
It will result in a 'Time Limit Exceeded' error on most online judges for this problem.

This approach improves upon the brute-force method by avoiding recalculating the total moves for each target sum from scratch. It uses a difference array, a technique related to sweep-line algorithms, to efficiently calculate the moves for all possible target sums simultaneously. We analyze how the number of moves changes as the target sum increases and use an array to record these changes at specific 'event points'. By processing these changes in a single pass, we can find the optimal target sum efficiently.

Algorithm

Create a difference array delta of size 2 * limit + 2, initialized to all zeros. This array will store the change in the number of moves as the target sum increases.
Iterate through the n/2 pairs (a, b) from the input array.
For each pair, determine the move savings and update the delta array:
- A 1-move cost is achievable for targetSum in [1 + min(a, b), limit + max(a, b)]. This is a reduction of 1 move from the default 2 moves. We record this by decrementing delta at the start of the range and incrementing it after the end: delta[1 + min(a, b)]-- and delta[limit + max(a, b) + 1]++.
- A 0-move cost is achievable for targetSum = a + b. This is a further reduction of 1 move. We record this by delta[a + b]-- and delta[a + b + 1]++.
After populating the delta array, calculate the actual moves for each targetSum.
Initialize currentMoves to n (the baseline cost of 2 moves for each of the n/2 pairs) and minMoves to n.
Iterate from targetSum = 2 to 2 * limit. In each step, update currentMoves by adding delta[targetSum]. This gives the total moves for the current targetSum.
Update minMoves = min(minMoves, currentMoves) in each step.
Return minMoves.

Walkthrough

The total number of moves for any targetSum can be calculated by starting with a baseline and applying adjustments. The baseline cost is 2 moves for each of the n/2 pairs, totaling n moves. We can then find how many moves can be saved for each targetSum.

For a pair (a, b), we can save moves depending on the targetSum:

Save 1 move (cost becomes 1): If we only need to change one number. This is possible for any targetSum in the range [1 + min(a, b), limit + max(a, b)].
Save 2 moves (cost becomes 0): If a + b is already equal to the targetSum. This is an additional saving of 1 move on top of the previous case.

We can model these savings as updates over ranges of targetSums. A difference array, let's call it delta, is perfect for this. delta[T] will store the change in the total number of moves as we go from targetSum = T-1 to T. After populating delta by processing all pairs, we can find the actual cost for each targetSum by computing the prefix sum of delta and adding it to the baseline cost of n.

1class Solution {2    public int minMoves(int[] nums, int limit) {3        int n = nums.length;4        // delta[i] stores the change in moves when the target sum changes from i-1 to i.5        int[] delta = new int[2 * limit + 2];6 7        for (int i = 0; i < n / 2; i++) {8            int a = nums[i];9            int b = nums[n - 1 - i];10            int minVal = Math.min(a, b);11            int maxVal = Math.max(a, b);12            int sum = a + b;13 14            // For any target sum, we assume 2 moves are needed initially.15            // The total moves start at n (2 moves for each of n/2 pairs).16 17            // Range where 1 move is sufficient: [1 + minVal, limit + maxVal]18            // For sums in this range, we save 1 move (cost changes from 2 to 1).19            // We apply a decrement over this range using the difference array.20            delta[1 + minVal]--;21            delta[limit + maxVal + 1]++;22 23            // For the specific sum `a + b`, 0 moves are needed.24            // This saves another move (cost changes from 1 to 0).25            // We apply another decrement for this single sum.26            delta[sum]--;27            delta[sum + 1]++;28        }29 30        // Calculate the actual moves for each possible target sum by taking a prefix sum.31        int currentMoves = n; // Start with the baseline of 2 moves per pair.32        int minMoves = n;33 34        for (int targetSum = 2; targetSum <= 2 * limit; targetSum++) {35            currentMoves += delta[targetSum];36            minMoves = Math.min(minMoves, currentMoves);37        }38 39        return minMoves;40    }41}

Complexity

Time

O(n + limit). We iterate through `n/2` pairs once to populate the `delta` array (`O(n)`), and then iterate through the `delta` array of size `O(limit)` once to find the minimum moves (`O(limit)`).

Space

O(limit), as we need a `delta` array of size `2 * limit + 2`.

Trade-offs

Pros

Highly efficient and optimal for the given constraints.
Solves the problem within the time limits.

Cons

Requires extra space proportional to limit.
The logic is more complex to understand and implement compared to the brute-force approach.

Solutions

Solution

1class Solution {2public3  int minMoves(int[] nums, int limit) {4    int n = nums.length;5    int[] d = new int[limit * 2 + 2];6    for (int i = 0; i < n >> 1; ++i) {7      int a = Math.min(nums[i], nums[n - i - 1]);8      int b = Math.max(nums[i], nums[n - i - 1]);9      d[2] += 2;10      d[limit * 2 + 1] -= 2;11      d[a + 1] -= 1;12      d[b + limit + 1] += 1;13      d[a + b] -= 1;14      d[a + b + 1] += 1;15    }16    int ans = n, s = 0;17    for (int i = 2; i <= limit * 2; ++i) {18      s += d[i];19      if (ans > s) {20        ans = s;21      }22    }23    return ans;24  }25}

1class Solution {2public:3  int minMoves(vector<int> &nums, int limit) {4    int n = nums.size();5    vector<int> d(limit * 2 + 2);6    for (int i = 0; i < n >> 1; ++i) {7      int a = min(nums[i], nums[n - i - 1]);8      int b = max(nums[i], nums[n - i - 1]);9      d[2] += 2;10      d[limit * 2 + 1] -= 2;11      d[a + 1] -= 1;12      d[b + limit + 1] += 1;13      d[a + b] -= 1;14      d[a + b + 1] += 1;15    }16    int ans = n, s = 0;17    for (int i = 2; i <= limit * 2; ++i) {18      s += d[i];19      if (ans > s) {20        ans = s;21      }22    }23    return ans;24  }25};

1class Solution:2    def minMoves(self, nums: List[int], limit: int) -> int: d = [0] * (limit * 2 + 2) n = len(nums) for i in range(n >> 1): a, b = min(nums[i], nums[n - i - 1]), max(nums[i], nums[n - i - 1]) d[2] += 2 d[limit * 2 + 1] -= 2 d[a + 1] -= 1 d[b + limit + 1] += 1 d[a + b] -= 1 d[a + b + 1] += 1 ans, s = n, 0 for v in d[2: limit * 2 + 1]: s += v if ans > s: ans = s return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem