Problem Description

You have an integer array nums with an even length n and an integer limit. You can perform moves where each move allows you to replace any integer in nums with another integer between 1 and limit (inclusive).

The goal is to make the array complementary. An array is complementary when for every index i (0-indexed), the sum nums[i] + nums[n - 1 - i] equals the same value across all pairs.

In other words, you need to make it so that:

• nums[0] + nums[n-1] equals some value s
• nums[1] + nums[n-2] equals the same value s
• nums[2] + nums[n-3] equals the same value s
• And so on for all pairs

For example, the array [1,2,3,4] is complementary because:

• nums[0] + nums[3] = 1 + 4 = 5
• nums[1] + nums[2] = 2 + 3 = 5

All pairs sum to 5, so the array is complementary.

Your task is to find the minimum number of moves (replacements) required to make the array complementary.

Intuition

The key insight is that we need to choose a target sum s that all pairs must equal to, and then count how many replacements are needed to achieve this sum for each pair.

For each pair (nums[i], nums[n-1-i]), let's call them x and y where x ≤ y. We need to understand how many replacements are required for different possible target sums:

1. Current sum (x + y): If we choose s = x + y, no replacements are needed for this pair.

2. One replacement possible: If we replace just one number in the pair:

   • Replacing x with something between 1 and limit gives us sums in range [1 + y, limit + y]
   • Replacing y with something between 1 and limit gives us sums in range [x + 1, x + limit]
   • The overlap of these ranges where exactly one replacement works is [x + 1, y + limit]

3. Two replacements needed: For sums outside the one-replacement range, we need to replace both numbers. This happens when:

   • s < x + 1 (sum too small, even replacing the smaller number with 1 isn't enough)
   • s > y + limit (sum too large, even replacing the larger number with limit isn't enough)

Instead of trying every possible sum s from 2 to 2 * limit and counting replacements for each, we can use a difference array to efficiently track how many replacements each pair needs across all possible sums.

For each pair, we mark ranges of sums with their replacement costs:

• [2, x]: needs 2 replacements
• [x + 1, x + y - 1]: needs 1 replacement
• [x + y, x + y]: needs 0 replacements
• [x + y + 1, y + limit]: needs 1 replacement
• [y + limit + 1, 2 * limit]: needs 2 replacements

By using a difference array to accumulate these costs for all pairs simultaneously, we can then find the sum s that minimizes the total number of replacements across all pairs.

Learn more about Prefix Sum patterns.

Solution Approach

We use a difference array to efficiently track the number of replacements needed for each possible target sum across all pairs.

Step 1: Initialize the difference array

• Create a difference array d of size 2 * limit + 2 to cover all possible sums from 2 to 2 * limit.
• This array will accumulate the replacement costs for all pairs.

Step 2: Process each pair For each pair (nums[i], nums[n-1-i]) where i goes from 0 to n//2 - 1:

• Let x = min(nums[i], nums[n-1-i]) and y = max(nums[i], nums[n-1-i])
• We need to update the difference array to reflect the replacement costs for this pair across different sum ranges.

Step 3: Update difference array for each range Using the difference array technique, we mark the start and end of each cost range:

• Range [2, x]: Needs 2 replacements

  • d[2] += 2 (start adding 2 at index 2)
  • d[x + 1] -= 2 (stop adding 2 after index x)

• Range [x + 1, x + y - 1]: Needs 1 replacement

  • d[x + 1] += 1 (start adding 1 at index x+1)
  • d[x + y] -= 1 (stop adding 1 at index x+y-1)

• Point [x + y]: Needs 0 replacements

  • No additional update needed (the previous -1 at d[x + y] handles this)

• Range [x + y + 1, y + limit]: Needs 1 replacement

  • d[x + y + 1] += 1 (start adding 1 at index x+y+1)
  • d[y + limit + 1] -= 1 (stop adding 1 after index y+limit)

• Range [y + limit + 1, 2 * limit]: Needs 2 replacements

  • d[y + limit + 1] += 2 (start adding 2 at index y+limit+1)
  • No end marker needed as it goes until the array end

Step 4: Find the minimum cost

• Use accumulate(d[2:]) to compute the prefix sum, which gives us the actual number of replacements needed for each possible sum.
• Return the minimum value from these prefix sums, which represents the minimum number of moves required.

The time complexity is O(n) where n is the length of the array, as we process each pair once and the difference array operations are constant time. The space complexity is O(limit) for the difference array.

Example Walkthrough

Let's walk through the solution with nums = [1, 5, 3, 3] and limit = 6.

Step 1: Identify pairs

• Pair 1: (nums[0], nums[3]) = (1, 3) → x = 1, y = 3
• Pair 2: (nums[1], nums[2]) = (5, 3) → x = 3, y = 5

Step 2: Analyze replacement costs for each pair

For Pair 1 (x=1, y=3):

• Current sum: 1 + 3 = 4 (needs 0 replacements)
• One replacement ranges:
  • Can achieve sums [x+1, y+limit] = [2, 9] with 1 replacement
  • But sum 4 needs 0, so we split: [2,3] needs 1, [4,4] needs 0, [5,9] needs 1
• Two replacements: sums outside [2, 9] would need 2 (but max sum is 2*6=12)

For Pair 2 (x=3, y=5):

• Current sum: 3 + 5 = 8 (needs 0 replacements)
• One replacement ranges:
  • Can achieve sums [x+1, y+limit] = [4, 11] with 1 replacement
  • But sum 8 needs 0, so we split: [4,7] needs 1, [8,8] needs 0, [9,11] needs 1
• Two replacements: sums [2,3] and [12,12] need 2

Step 3: Build difference array

Initialize d = [0] * 14 (size 2*limit + 2)

For Pair 1 (x=1, y=3):

• [2, 1]: needs 2 → d[2] += 2 (but 1 < 2, so this range is empty)
• [2, 3]: needs 1 → d[2] += 1, d[4] -= 1
• [4, 4]: needs 0 → already handled by the -1 at d[4]
• [5, 9]: needs 1 → d[5] += 1, d[10] -= 1
• [10, 12]: needs 2 → d[10] += 2

For Pair 2 (x=3, y=5):

• [2, 3]: needs 2 → d[2] += 2, d[4] -= 2
• [4, 7]: needs 1 → d[4] += 1, d[8] -= 1
• [8, 8]: needs 0 → already handled by the -1 at d[8]
• [9, 11]: needs 1 → d[9] += 1, d[12] -= 1
• [12, 12]: needs 2 → d[12] += 2

Step 4: Compute prefix sum

After all updates:

d = [0, 0, 3, 0, -2, 1, 0, 0, -1, 1, 1, 0, 1, 0]

Computing prefix sum from index 2:

Sum  | 2  3  4  5  6  7  8  9  10 11 12
Cost | 3  3  1  2  2  2  1  2  3  3  4

Step 5: Find minimum

The minimum cost is 1 at sum 4 and sum 8.

This means we need only 1 move to make the array complementary:

• If we choose target sum 4: Replace nums[1]=5 with 1 to get [1,1,3,3]
• If we choose target sum 8: Replace nums[0]=1 with 5 to get [5,5,3,3]

Both options require exactly 1 replacement to make all pairs sum to the same value.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + limit)

The algorithm iterates through n/2 pairs of elements (where n is the length of the input array), performing constant-time operations for each pair. This gives us O(n) for the first loop. The accumulate function then processes the difference array d[2:] which has a length of approximately 2 * limit, taking O(limit) time. The min function also takes O(limit) time to find the minimum value from the accumulated results. Therefore, the overall time complexity is O(n + limit).

Space Complexity: O(limit)

The algorithm creates a difference array d of size 2 * limit + 2, which requires O(limit) space. The accumulate function creates an iterator that generates values on-the-fly, and min processes these values without storing them all at once, so no additional space proportional to the array size is needed. The only significant space usage is the difference array d, resulting in a space complexity of O(limit).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Difference Array Updates Leading to Overlapping Ranges

One of the most common mistakes is incorrectly updating the difference array boundaries, which causes overlapping or gaps in the cost ranges. The code shown has this exact issue.

The Problem: In the provided code, the updates are:

diff_array[2] += 2
diff_array[left_val + 1] -= 2
diff_array[left_val + 1] += 1
diff_array[left_val + right_val] -= 1
diff_array[left_val + right_val + 1] += 1
diff_array[right_val + limit + 1] -= 1
diff_array[right_val + limit + 1] += 2

This creates overlapping updates at left_val + 1 and right_val + limit + 1, making the logic confusing and error-prone.

The Solution: Simplify by updating each range boundary only once:

# Range [2, left_val]: 2 moves
diff_array[2] += 2
diff_array[left_val + 1] -= 1  # Reduce by 1 (from 2 to 1)

# Range [left_val + 1, left_val + right_val - 1]: 1 move (already set)

# Point [left_val + right_val]: 0 moves
diff_array[left_val + right_val] -= 1  # Reduce by 1 (from 1 to 0)
diff_array[left_val + right_val + 1] += 1  # Back to 1

# Range [left_val + right_val + 1, right_val + limit]: 1 move (already set)

# Range [right_val + limit + 1, 2*limit]: 2 moves
diff_array[right_val + limit + 1] += 1  # Increase by 1 (from 1 to 2)

2. Array Index Out of Bounds

The Problem: When right_val + limit + 1 exceeds the difference array size, it causes an index out of bounds error. This happens when processing pairs where one element is already at the limit.

The Solution: Add boundary checks before updating:

if right_val + limit + 1 < len(diff_array):
    diff_array[right_val + limit + 1] += 1

3. Not Handling Edge Cases for Small Limits

The Problem: When limit is very small (e.g., 1 or 2), the ranges might overlap or become invalid, leading to incorrect calculations.

The Solution: Ensure all range boundaries are valid:

# Ensure we don't go out of bounds
max_sum = min(right_val + limit, 2 * limit)
if max_sum + 1 < len(diff_array):
    diff_array[max_sum + 1] += 1

Corrected Code:

from typing import List
from itertools import accumulate

class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        diff_array = [0] * (2 * limit + 2)
        n = len(nums)
      
        for i in range(n // 2):
            left_val = min(nums[i], nums[n - 1 - i])
            right_val = max(nums[i], nums[n - 1 - i])
          
            # Start with 2 moves for all sums
            diff_array[2] += 2
          
            # From left_val + 1, only 1 move needed
            diff_array[left_val + 1] -= 1
          
            # At exact sum, 0 moves needed
            diff_array[left_val + right_val] -= 1
          
            # After exact sum, back to 1 move
            diff_array[left_val + right_val + 1] += 1
          
            # After right_val + limit, back to 2 moves
            if right_val + limit + 1 < len(diff_array):
                diff_array[right_val + limit + 1] += 1
      
        # Calculate prefix sum and find minimum
        return min(accumulate(diff_array[2:2 * limit + 1]))