Minimum Moves : An Elegant Approach to Complementary Arrays | Java 
Intuition | ApproachDetailed Explanation and Intuition for Minimum Moves to Make Array ComplementaryProblem SummaryGiven an array nums of even length and a limi
# Intuition | Approach
## **Detailed Explanation and Intuition for Minimum Moves to Make Array Complementary**

### **Problem Summary**
Given an array `nums` of even length and a limit, we need to make all pairs of numbers in the array complementary with the minimum number of moves. Two numbers are complementary if their sum falls within a specific valid range. We can adjust each number in the pair by at most `1` move within the range `[1, limit]`.

### **Core Idea and Approach**
The problem can be broken down into calculating the cost of adjusting each pair’s sum to make it valid. The goal is to minimize the total number of moves required across all pairs.

To achieve this efficiently, we use a **difference array** (`pos[]`) combined with a prefix sum technique. This allows us to update cost ranges incrementally without iterating through every possible pair or sum directly.

---

### **Key Steps in the Solution**

#### **1. Default Initialization**
We assume the **worst-case cost** for all sums initially, which is 2 moves for every sum in the range of valid sums:

```java
pos[2] += 2;  // Starting from the smallest sum, add 2 cost.
pos[2 * limit + 1] += -2;  // Stop adding cost beyond the largest sum.
```

- **Intuition**: This sets the base cost of 2 moves for all possible sums, which we then reduce for specific sums based on the given pairs.
- **Boundary Condition**: Beyond `2 * limit`, no valid sums exist, so we stop adding costs there.

#### **2. Updating Costs for 1 Move**
For each pair `(a, b)` in the array:
- Calculate the possible range of sums achievable with 1 move:
  - (min(a, b) + 1)  to  (max(a, b) + limit).
- Adjust the difference array `pos[]`:
  ```java
  pos[min(a, b) + 1] += -1;  // Start reducing cost from here.
  pos[max(a, b) + limit + 1] += 1;  // Stop reducing cost beyond this point.
  ```

- **Intuition**: This indicates that sums within this range require only 1 move instead of 2. Beyond this range, the cost returns to 2 moves.

#### **3. Updating Costs for 0 Moves**
For sums that are already valid without any moves:
- The exact sum achievable by the pair without adjustment is \( a + b \).
- Adjust the difference array `pos[]`:
  ```java
  pos[a + b] += -1;  // Subtract 1 to reflect no moves needed here.
  pos[a + b + 1] += 1;  // Restore cost after this sum.
  ```

- **Intuition**: This ensures that the cost for the specific sum `a + b` is reduced to 0, while sums just beyond it revert to the normal cost.

#### **4. Applying the Prefix Sum**
After updating the difference array for all pairs:
- Compute the prefix sum over `pos[]` to calculate the total cost for every possible sum.
- Track the minimum cost while iterating through the prefix sum array.

---

### **Walkthrough Example**
#### Input:
```java
nums = [1, 2, 4, 3], limit = 4;
```

#### Steps:
**1. Default Initialization:**
- Start with all sums having a cost of 2:
  ```java
  pos[2] += 2;
  pos[9] += -2;  // (2 * limit + 1 = 9)
  ```

**2. Process Each Pair:**

**Pair 1:** `(1, 3)`
- Possible sum range with 1 move: \( 2 \) to \( 7 \).
  ```java
  pos[2] += -1;
  pos[8] += 1;
  ```
- Exact sum without moves: \( 1 + 3 = 4 \).
  ```java
  pos[4] += -1;
  pos[5] += 1;
  ```

**Pair 2:** `(2, 4)`
- Possible sum range with 1 move: \( 3 \) to \( 8 \).
  ```java
  pos[3] += -1;
  pos[9] += 1;
  ```
- Exact sum without moves: \( 2 + 4 = 6 \).
  ```java
  pos[6] += -1;
  pos[7] += 1;
  ```

**3. Prefix Sum Calculation:**
Compute the prefix sum over `pos[]` to determine the cost for each sum.

**4. Track Minimum Cost:**
Iterate through the prefix sum array and find the minimum cost.

---

### **Key Intuitions for Each Part**

1. **Default Initialization:**
   - Assumes every sum starts with the worst-case cost of 2 moves. This sets the baseline to adjust from.

2. **1 Move Range Updates:**
   - Reduces the cost to 1 move for sums within a specific range achievable by adjusting one number in the pair.

3. **0 Move Updates:**
   - Reduces the cost to 0 for the exact sums achievable without any moves.

4. **Prefix Sum:**
   - Efficiently calculates the final cost for each sum after applying all adjustments from the difference array.

---

### **Final Notes**
- **Why Difference Array?**
  - Instead of iterating through all possible sums for each pair, we efficiently update only the relevant ranges. This reduces the time complexity to \( O(n + \text{limit}) \).

- **Why Prefix Sum?**
  - The prefix sum converts the range-based updates in the difference array into actual cumulative costs for each sum.

This approach ensures we solve the problem efficiently while accurately minimizing the number of moves needed.





# Complexity
- Time complexity: O(N/2 + 2*Limit)

- Space complexity: O[2 * Limit + 2] (Here the +2 is added because we take maximum of 2*limit + 1 in our array for the last cost reduction so to accomodate that we need 2 * limit + 1 + 1) ~ O(2Limit)


# Code
```java []
class Solution {
    public int minMoves(int[] nums, int limit) {
        int diff[] = new int[2* limit + 2], n = nums.length;

        for(int i = 0 ; i < nums.length/2 ; i++){

            int left = nums[i], right = nums[n - i - 1];
            int min = Math.min(left, right), max = Math.max(left, right);

            diff[2] += 2;

            diff[min + 1] += -1;

            diff[left + right] += -1;
            diff[left + right + 1] += 1;

            diff[max + limit + 1] += 1; 

            diff[2*limit + 1] += -2;
        }

        int minCounts = Integer.MAX_VALUE; 
        for(int i = 2 ; i <= 2*limit ; i++){
            diff[i] = diff[i] + diff[i - 1];
            minCounts = Math.min(minCounts, diff[i]);
        }

        return minCounts; 
    }
}
```
['Java']