Minimum Moves to Make Array Complementary: Difference Array Pattern

You are given an integer array nums of even length n and an integer limit. In one move, you can replace any element with any integer between 1 and limit, inclusive. The array is complementary if for all indices i, nums[i] + nums[n-1-i] equals the same value. Return the minimum number of moves required to make the array complementary.

This is LeetCode 1674: Minimum Moves to Make Array Complementary.

Why this problem matters

The brute force approach is tempting: for every possible target sum T, iterate through all pairs and count the moves. But with T ranging from 2 to 2 * limit and up to n/2 pairs, that gives you O(n * limit) work, which is too slow when both n and limit reach 10^5. You need a way to evaluate all target sums simultaneously without looping over each one individually.

This is where the difference array technique comes in. Instead of computing the cost for every target sum from scratch, you observe that each pair contributes a cost function that changes at only a few critical thresholds. Between those thresholds, the cost is constant. You can encode each pair's contribution as a handful of updates to a difference array, then recover the total cost for every target sum with a single prefix sum pass.

The difference array pattern appears in many problems beyond this one. It is the same idea behind "Corporate Flight Bookings" (LeetCode 1109), "Car Pooling" (LeetCode 1094), and any scenario where you need to apply range updates and then query the accumulated result. Mastering this pattern here means you will recognize it instantly in those other problems.

The key insight

For each pair (a, b) where a = nums[i] and b = nums[n-1-i], there are ranges of target sums T where you need 0, 1, or 2 moves:

• 0 moves when T = a + b (the pair already sums to T).
• 1 move when T is in the range [min(a, b) + 1, max(a, b) + limit]. You can change one element to make the pair sum to T without violating the [1, limit] constraint.
• 2 moves for any other valid T in [2, 2 * limit]. You must change both elements.

Instead of looping over every T for every pair, you record each pair's cost transitions in a difference array. Each pair contributes exactly five updates. After processing all pairs, a single prefix sum sweep gives you the total cost at every target sum. The minimum value in that sweep is your answer.

The solution

def minMoves(nums, limit):
    n = len(nums)
    diff = [0] * (2 * limit + 2)

    for i in range(n // 2):
        a, b = nums[i], nums[n - 1 - i]
        lo = min(a, b) + 1
        hi = max(a, b) + limit
        s = a + b

        diff[2] += 2
        diff[lo] -= 1
        diff[s] -= 1
        diff[s + 1] += 1
        diff[hi + 1] += 1

    result = n
    curr = 0
    for t in range(2, 2 * limit + 1):
        curr += diff[t]
        result = min(result, curr)

    return result

The outer loop runs through each pair once. For each pair (a, b), we make five constant-time updates to the difference array. The first update, diff[2] += 2, assumes every target sum costs 2 moves for this pair. Then diff[lo] -= 1 marks where the cost drops to 1 (entering the 1-move zone). At diff[s] -= 1, the cost drops to 0 (the exact sum). At diff[s + 1] += 1, the cost rises back to 1 (leaving the 0-move zone). Finally, diff[hi + 1] += 1 marks where the cost goes back to 2 (leaving the 1-move zone).

The second loop computes the running prefix sum of the difference array and tracks the minimum. Each value of curr at position t represents the total number of moves across all pairs if the target sum is t.

Visual walkthrough

Let's trace through nums = [1, 2, 4, 3] with limit = 4. There are two pairs: (1, 3) and (2, 4). Watch how each pair's cost ranges overlap in the difference array, and how the prefix sum reveals the minimum.

The bar chart at the end shows the total cost at each target sum after combining both pairs. The minimum is 1, which occurs at both T = 4 (where pair A costs 0 and pair B costs 1) and T = 6 (where pair A costs 1 and pair B costs 0). You only need to change one element in one pair.

Complexity analysis

Time is O(n + limit). The first loop processes n/2 pairs with O(1) work each, giving O(n). The second loop sweeps the difference array from 2 to 2 * limit, giving O(limit). Total: O(n + limit).

Space is O(limit) for the difference array of size 2 * limit + 2. No additional data structures are needed beyond a few variables.

The building blocks

1. Difference array for range updates

The core data structure is a difference array that lets you apply range increments in O(1):

diff = [0] * size
diff[left] += delta
diff[right + 1] -= delta

To recover the actual values, compute the prefix sum of diff. This gives you the accumulated value at every position. You will see this pattern in flight booking problems, car pooling, and any scenario where many intervals overlap and you need the aggregate.

2. Pair analysis for cost ranges

For each pair (a, b) with values in [1, limit], you determine the thresholds where the cost changes:

lo = min(a, b) + 1
hi = max(a, b) + limit
s = a + b

The range [lo, hi] is where one move suffices. The point s is where zero moves are needed. Everything outside [lo, hi] but inside [2, 2 * limit] costs two moves. These boundaries come from the constraint that replacement values must be between 1 and limit. If you want the pair to sum to T with one change, the changed element must be T - a or T - b, and that value must be in [1, limit]. Working out the algebra gives you the lo and hi boundaries.

Edge cases

• All pairs already have the same sum. The difference array naturally handles this. The prefix sum at T = a + b will be 0 for all pairs, and the answer is 0.
• limit equals 1. Every element is 1, every pair sums to 2, and the array is already complementary. The answer is 0.
• Array of length 2. There is exactly one pair. The answer is 0 if both elements sum to any value (which they always do), so the answer is always 0 for length-2 arrays.
• All elements equal to 1. Every pair sums to 2. Zero moves needed since they already share the same sum.
• Pairs with maximum spread. When one element is 1 and the other is limit, the 1-move range is [2, 2 * limit], covering all valid targets. The 0-move point is at 1 + limit.

From understanding to recall

The conceptual jump in this problem is realizing that you do not need to iterate over target sums for each pair. Once you see that each pair's cost function is piecewise constant with at most five breakpoints, the difference array becomes the natural tool. You encode the transitions, sweep once, and read off the answer.

When reviewing this problem, focus on two things. First, make sure you can derive the five difference array updates from the pair analysis without looking them up. The logic is: start at cost 2 for the full range, subtract 1 when entering the 1-move zone, subtract 1 more at the exact sum, then reverse those reductions when leaving each zone. Second, practice writing the prefix sum sweep. The implementation is only a few lines, but getting the boundaries right (starting at 2, ending at 2 * limit) matters for correctness.

Related posts

• Minimum Number of K Consecutive Bit Flips - Uses a similar "lazy propagation" idea where you track the net effect of overlapping operations with a queue instead of applying each one individually
• Corporate Flight Bookings - A clean example of the difference array pattern for range updates, which is the same core technique used here
• Car Pooling - Another application of the difference array where you track passenger counts over a timeline of pickup and dropoff events

CodeBricks breaks this problem into its difference array and pair analysis building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a range-update problem shows up in your interview, you do not think about it. You just write it.