LeetCode 1674 - Minimum Moves to Make Array Complementary

LeetCode Problem 1674

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Prefix Sum

Solution

Problem Understanding

The problem requires us to transform an array nums of even length n into a complementary array. An array is complementary if for every index i, the sum of nums[i] + nums[n - 1 - i] is the same constant value. Each element in nums can be changed to any integer in the range [1, limit] in one move, and we want to determine the minimum number of moves to achieve this property.

In simpler terms, we are pairing elements symmetrically from the ends of the array and trying to make all pairs sum to the same number using as few replacements as possible. The key observations are that every element can change within [1, limit] and that we only need to consider sums of pairs, not individual elements in isolation.

The constraints tell us that n can be up to 10^5 and limit can be up to 10^5, which rules out solutions that iterate through all possible sums or modify elements naively. Edge cases include arrays that are already complementary, arrays that require maximum changes, and arrays where limit is very small or very large relative to the elements.

Important guarantees: the array length n is even, and all nums[i] are within [1, limit].

Approaches

Brute Force

A naive approach would consider every possible target sum S from 2 to 2 * limit and, for each, calculate the number of moves needed to make every pair sum equal to S. For each pair (a, b) = (nums[i], nums[n-1-i]), we determine if zero moves, one move, or two moves are required depending on whether a + b == S or if changing one or both elements can achieve S. While correct, this approach would take O(n * limit) time in the worst case, which is far too slow for n up to 10^5 and limit up to 10^5.

Optimal Approach

The key insight is that for a pair (a, b), the number of moves required depends on the range of sums achievable with one move. Specifically, one move can make the sum any number between 1 + min(a, b) and limit + max(a, b). Outside this range, two moves are needed. By using a prefix sum difference array, we can efficiently compute the minimum moves for all possible sums from 2 to 2 * limit without checking each sum individually for every pair.

Steps of the insight:

1. For each pair (a, b), identify:

• Minimum sum requiring 2 moves (2)
• Range of sums requiring 1 move (1 + min(a, b) to limit + max(a, b))
• Sum that requires 0 moves (a + b)

2. Use a difference array delta where delta[s] indicates changes in moves required at sum s. Add +2 moves initially, subtract or add 1 at boundaries to encode ranges, and then compute prefix sums to get moves for all sums efficiently.

This approach reduces the complexity to linear in n plus linear in limit, which is feasible given the constraints.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * limit)	O(1)	Check all possible sums for every pair
Optimal	O(n + limit)	O(limit)	Use prefix sum / difference array to compute moves efficiently

Algorithm Walkthrough

1. Initialize a difference array delta of length 2 * limit + 2 to store change in moves at each sum.
2. Iterate over each pair (a, b) = (nums[i], nums[n-1-i]).
3. For each pair, initially assume 2 moves for all sums.
4. Update delta to account for the sum ranges where 1 move or 0 moves is possible:

• Increment at 2 by 2 (start of 2-move sums)
• Decrement at 1 + min(a, b) by 1 (start of 1-move sums)
• Decrement at a + b by 1 (0-move sum)
• Increment at a + b + 1 by 1 (end of 0-move sum)
• Increment at limit + max(a, b) + 1 by 1 (end of 1-move sums)

5. Compute the prefix sum of delta to get the actual moves required for each sum.
6. Return the minimum value among all sums.

Why it works: The difference array encodes how many moves each sum needs. The prefix sum converts the difference array into actual moves, allowing us to efficiently compute the minimum moves across all sums without checking each one explicitly for every pair.

Python Solution

from typing import List

class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        n = len(nums)
        delta = [0] * (2 * limit + 2)
        
        for i in range(n // 2):
            a, b = nums[i], nums[n - 1 - i]
            low = 1 + min(a, b)
            high = limit + max(a, b)
            sum_ab = a + b
            
            delta[2] += 2
            delta[low] -= 1
            delta[sum_ab] -= 1
            delta[sum_ab + 1] += 1
            delta[high + 1] += 1
        
        moves = float('inf')
        current = 0
        for s in range(2, 2 * limit + 1):
            current += delta[s]
            moves = min(moves, current)
        
        return moves

The Python implementation follows the algorithm directly. The difference array encodes moves, and a single pass computes the prefix sum to determine the minimum moves efficiently.

Go Solution

func minMoves(nums []int, limit int) int {
    n := len(nums)
    delta := make([]int, 2*limit+2)
    
    for i := 0; i < n/2; i++ {
        a, b := nums[i], nums[n-1-i]
        low := 1 + min(a, b)
        high := limit + max(a, b)
        sumAB := a + b
        
        delta[2] += 2
        delta[low] -= 1
        delta[sumAB] -= 1
        delta[sumAB+1] += 1
        delta[high+1] += 1
    }
    
    moves := int(1e9)
    current := 0
    for s := 2; s <= 2*limit; s++ {
        current += delta[s]
        if current < moves {
            moves = current
        }
    }
    return moves
}

func min(a, b int) int {
    if a < b { return a }
    return b
}

func max(a, b int) int {
    if a > b { return a }
    return b
}

The Go solution mirrors the Python version, using slices and integer functions for min and max. It avoids explicit type conversions since all values are within int range.

Worked Examples

Example 1: nums = [1,2,4,3], limit = 4

Pairs: (1,3) and (2,4)

For pair (1,3):

• sum = 4, low = 2, high = 7
• delta updates: delta[2] +=2, delta[2]-=1, delta[4]-=1, delta[5]+=1, delta[8]+=1

For pair (2,4):

• sum = 6, low = 3, high = 8
• delta updates accordingly

Prefix sum over sums 2..8 gives moves: minimum = 1

Example 2: nums = [1,2,2,1], limit = 2

Pairs: (1,1) and (2,2)

• All sums outside achievable range require moves
• Prefix sum calculation shows minimum = 2

Example 3: nums = [1,2,1,2], limit = 2

Pairs: (1,2) and (2,1)

• Already complementary (sum = 3)
• Prefix sum shows minimum moves = 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + limit)	O(n) to process pairs and O(limit) to compute prefix sum
Space	O(limit)	Difference array of size 2 * limit + 2

The algorithm scales linearly with array size and the limit range, making it efficient for large inputs.

Test Cases

# provided examples
assert Solution().minMoves([1,2,4,3], 4) == 1  # one move needed
assert Solution().minMoves([1,2,2,1], 2) == 2  # two moves needed
assert Solution().minMoves([1,2,1,2], 2) == 0  # already complementary

# edge cases
assert Solution().minMoves([1,1