Problem Statement in English

You’re 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.

The array nums is complementary if for every 0 <= i < n / 2, nums[i] + nums[n - 1 - i] equals the same number. For example, the array nums = [1, 2, 3, 4] is complementary because 1 + 4 == 2 + 3. However, the array nums = [1, 2, 3, 5] is not complementary because 1 + 5 != 2 + 3.

Return the minimum number of moves required to make nums complementary.

Approach

To visualise the solution to this problem, it helps to think of the solution as a piecewise function of the target sum x that we want all pairs to equal. For each pair of numbers (A, B), where A <= B, we can determine how many moves it would take to make their sum equal to x:

  • The minimum sum of the pair is 2 (when both numbers are 1), and the maximum sum is 2 * limit (when both numbers are limit). So, we only need to consider target sums in the range [2, 2 * limit].

Assume that it takes 2 moves to change both numbers in the pair to achieve the target sum. We can then identify intervals for x where the number of moves changes:

• At S = A + 1, the cost drops from 2 moves to 1 move (a change of -1, since we only change B to 1). • At S = A + B, the cost drops from 1 move to 0 moves (a change of -1, since nothing needs to be changed). • At S = A + B + 1, the cost goes back up from 0 moves to 1 move (a change of +1, since either A or B needs to be changed). • At S = B + limit + 1, the cost goes back up from 1 move to 2 moves (a change of +1, since both A and B need to be changed).

Now we can use a sweeping line technique to calculate the total moves for all pairs for each possible target sum. Since we have n/2 pairs, we need only n/2 iterations to process the pairs. For each pair, remember to ensure that A <= B to simplify the logic.

Now because of the structure of the cost changes, it’s guaranteed that we first encoutner negative changes (cost reductions) before positive changes (cost increases) as we sweep through the target sums. This allows us to maintain a running total of moves and update it efficiently as we encounter the changes.

Thus we can start our running total of moves at n (since if we did 2 moves for all pairs, that would be n/2 * 2 = n moves) and then apply the changes from the delta array as we sweep through the target sums to find the minimum moves required.

As we iterate we just need to keep track of the minimum moves encountered - which will be our final answer.

And we’re done!

Solution in Python


class Solution:
    def minMoves(self, nums: list[int], limit: int) -> int:
        n = len(nums)
        # delta array to record the changes in moves. 
        # Size is 2 * limit + 2 to safely handle boundary indices.
        delta = [0] * (2 * limit + 2)
        
        # Process each symmetric pair
        for i in range(n // 2):
            A = nums[i]
            B = nums[n - 1 - i]
            
            # Ensure A <= B for our logic formulas
            if A > B:
                A, B = B, A
                
            # Interval 1: [2, A] -> 2 moves
            # Interval 2: [A + 1, B + limit] -> 1 move
            # Interval 3: [B + limit + 1, 2 * limit] -> 2 moves
            # Special point: A + B -> 0 moves
            
            # Initially, assume 2 moves for everything.
            # At A + 1, moves drop from 2 to 1 (-1)
            delta[A + 1] -= 1
            # At A + B, moves drop from 1 to 0 (-1)
            delta[A + B] -= 1
            # At A + B + 1, moves increase from 0 to 1 (+1)
            delta[A + B + 1] += 1
            # At B + limit + 1, moves increase from 1 to 2 (+1)
            delta[B + limit + 1] += 1
            
        res = float('inf')
        current_moves = n # If we did 2 moves for all n/2 pairs, total moves = n
        
        # Sweep through all possible target sums from 2 to 2 * limit
        for x in range(2, 2 * limit + 1):
            current_moves += delta[x]
            res = min(res, current_moves)
                
        return res

Complexity

  • Time: $O(n + limit)$
    Since we process each pair in O(n) and then sweep through the delta array in O(limit).

  • Space: $O(limit)$
    Since we use a delta array of size proportional to limit.

Mistakes I Made

I had to look this up :(

And we are done.