# Minimum Moves to Make Array Complementary
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-moves-to-make-array-complementary)
Canonical: https://scaleengineer.com/dsa/problems/minimum-moves-to-make-array-complementary
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table
**Companies:** [CureFit](https://scaleengineer.com/companies/curefit)
---
## Problem
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.

# Approaches
## Brute Force by Iterating All Possible Target Sums
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.
**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.
**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.
### Explanation
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 `targetSum`s is the answer.

```java
class Solution {
    public int minMoves(int[] nums, int limit) {
        int n = nums.length;
        int minMoves = n; // Maximum possible moves

        for (int targetSum = 2; targetSum <= 2 * limit; targetSum++) {
            int currentMoves = 0;
            for (int i = 0; i < n / 2; i++) {
                int a = nums[i];
                int b = nums[n - 1 - i];
                
                if (a + b == targetSum) {
                    // 0 moves needed
                    continue;
                }
                
                int minVal = Math.min(a, b);
                int maxVal = Math.max(a, b);
                if (targetSum >= 1 + minVal && targetSum <= limit + maxVal) {
                    currentMoves += 1;
                } else {
                    currentMoves += 2;
                }
            }
            minMoves = Math.min(minMoves, currentMoves);
        }
        return minMoves;
    }
}
```
### 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.

## Optimized Approach using Difference Array (Sweep Line)
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.
**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`.
**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.
### Explanation
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 `targetSum`s. 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`.

```java
class Solution {
    public int minMoves(int[] nums, int limit) {
        int n = nums.length;
        // delta[i] stores the change in moves when the target sum changes from i-1 to i.
        int[] delta = new int[2 * limit + 2];

        for (int i = 0; i < n / 2; i++) {
            int a = nums[i];
            int b = nums[n - 1 - i];
            int minVal = Math.min(a, b);
            int maxVal = Math.max(a, b);
            int sum = a + b;

            // For any target sum, we assume 2 moves are needed initially.
            // The total moves start at n (2 moves for each of n/2 pairs).

            // Range where 1 move is sufficient: [1 + minVal, limit + maxVal]
            // For sums in this range, we save 1 move (cost changes from 2 to 1).
            // We apply a decrement over this range using the difference array.
            delta[1 + minVal]--;
            delta[limit + maxVal + 1]++;

            // For the specific sum `a + b`, 0 moves are needed.
            // This saves another move (cost changes from 1 to 0).
            // We apply another decrement for this single sum.
            delta[sum]--;
            delta[sum + 1]++;
        }

        // Calculate the actual moves for each possible target sum by taking a prefix sum.
        int currentMoves = n; // Start with the baseline of 2 moves per pair.
        int minMoves = n;

        for (int targetSum = 2; targetSum <= 2 * limit; targetSum++) {
            currentMoves += delta[targetSum];
            minMoves = Math.min(minMoves, currentMoves);
        }

        return minMoves;
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
public
  int minMoves(int[] nums, int limit) {
    int n = nums.length;
    int[] d = new int[limit * 2 + 2];
    for (int i = 0; i < n >> 1; ++i) {
      int a = Math.min(nums[i], nums[n - i - 1]);
      int b = Math.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;
    }
    int ans = n, s = 0;
    for (int i = 2; i <= limit * 2; ++i) {
      s += d[i];
      if (ans > s) {
        ans = s;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minMoves(vector<int> &nums, int limit) {
    int n = nums.size();
    vector<int> d(limit * 2 + 2);
    for (int i = 0; i < n >> 1; ++i) {
      int a = min(nums[i], nums[n - i - 1]);
      int b = 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;
    }
    int ans = n, s = 0;
    for (int i = 2; i <= limit * 2; ++i) {
      s += d[i];
      if (ans > s) {
        ans = s;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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

```