Minimum Moves to Make Array Complementary - Video Solutions

Problem Overview: You are given an array nums and a value limit. The array is considered complementary if for every index i, the pair (nums[i], nums[n-1-i]) has the same sum. You can change any element to any value between 1 and limit. The task is to compute the minimum number of moves required so every mirrored pair produces the same target sum.

Approach 1: Brute Force Pair Simulation (O(n * limit) time, O(1) space)

Each mirrored pair contributes to a potential target sum between 2 and 2 * limit. The brute force strategy iterates over every possible target sum and calculates how many changes are required for all pairs to match that sum. For a pair (a, b), three cases exist: zero moves if a + b == target, one move if one value can be adjusted within [1, limit] to reach the target, otherwise two moves. You iterate through all n/2 pairs for every possible target sum. This approach clearly models the rules but becomes expensive when limit is large.

Approach 2: Sweep Line with Delta Array (O(n + limit) time, O(limit) space)

The optimized solution treats the problem as a range update problem using a sweep line idea built on prefix sum. For each pair (a, b), analyze how many moves are required for every possible target sum. Normally each pair costs two moves. However, within certain ranges the cost drops to one move, and exactly one value (the current sum a + b) requires zero moves. Instead of evaluating each target sum separately, update a delta array that records how the cost changes across ranges.

For each pair you mark intervals where the required moves decrease: from min(a,b)+1 to max(a,b)+limit the cost becomes one move, and at a+b the cost becomes zero. These changes are recorded using difference array updates. After processing all pairs, run a prefix accumulation over the delta array to compute the total moves for each possible target sum between 2 and 2*limit. The minimum value across this sweep is the answer.

This technique combines ideas from arrays, range updates, and prefix sums. Instead of recalculating costs repeatedly, it aggregates how each pair influences the global cost function.

Recommended for interviews: Start by describing the brute force reasoning so the interviewer sees you understand the pair constraints and move rules. Then transition to the sweep line optimization using a delta array. The optimized approach reduces the complexity to O(n + limit) and demonstrates strong understanding of prefix sums and range contribution techniques.