We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Moves to Make Array Complementary

Number: 1793

Difficulty: Medium

Paid? No

Companies: Google, CureFit

Problem Description

Given an even-length integer array nums and an integer limit, you can change any element in nums to any value between 1 and limit in one move. The array is called complementary if for every index i, the sum nums[i] + nums[n-1-i] is the same. The goal is to compute the minimum number of moves required to convert nums into a complementary array.

Key Insights

  • Every pair (nums[i], nums[n-1-i]) contributes to a target sum.
  • Without any changes, each pair would require 2 moves.
  • However, if one of the elements in the pair can be adjusted smartly, some sums may be achievable with only 1 move or even 0 moves.
  • For each pair, there is a range of sums that can be achieved with 1 move.
  • A difference array (or prefix sum technique) can efficiently tally the change in cost for all potential sums.
  • After processing all pairs, iterating over all possible sums gives the minimal total moves required.

Space and Time Complexity

Time Complexity: O(n + limit) – each pair is processed in constant time and then we iterate over 2limit possible sums.
Space Complexity: O(limit) – using an auxiliary array of size proportional to 2limit to store differences.

Solution

We start by noting that without any modifications, each pair would need 2 moves. For each symmetric pair (a, b), we can achieve the following:

  • With 0 moves if the pair already sums to a desired value.
  • With 1 move if we can change one of them such that the new sum lies in the interval [min(a, b) + 1, max(a, b) + limit].
  • With 2 moves if neither of the above conditions is possible.

We use a difference array (or prefix sum array) to track the change in the number of moves required for each possible target sum. For each pair:

  • We add an initial cost of 2 moves.
  • In the interval [min(a, b) + 1, max(a, b) + limit], we can reduce the cost by 1 (making it 1 move in total).
  • At exactly the sum a + b, we can reduce the cost by another move (making it 0 moves).

After processing all pairs, we compute a prefix sum over the difference array to derive the total moves required for each possible target sum. Finally, we take the minimum value as our answer.

Code Solutions

# Python solution for Minimum Moves to Make Array Complementary

def minMoves(nums, limit):
    n = len(nums)
    # Maximum sum possible is 2 * limit.
    max_sum = 2 * limit
    # Initialize difference array of size max_sum + 2 (1-indexed for sums from 2 to 2*limit).
    diff = [0] * (max_sum + 2)
    
    # Base cost: for each pair, assume it needs 2 moves.
    # The baseline contribution for any sum in [2, 2*limit] is 2 moves per pair.
    for i in range(n // 2):
        a = nums[i]
        b = nums[n - 1 - i]
        low = min(a, b) + 1       # One move can result in any sum >= min+1.
        high = max(a, b) + limit  # One move can result in any sum <= max+limit.
        pair_sum = a + b
        
        # Initially, every sum gets a cost of +2 moves (this will be applied later).
        # For sums in range [low, high], one move suffices, so we subtract 1 move.
        diff[low] -= 1
        diff[high + 1] += 1
        
        # For the exact sum equal to pair_sum, we can reduce the cost by an additional move (0 moves needed).
        diff[pair_sum] -= 1
        diff[pair_sum + 1] += 1
    
    best = float('inf')
    curr = 0
    totalPairs = n // 2
    
    # For every possible sum from 2 to 2*limit
    for target in range(2, max_sum + 1):
        curr += diff[target]
        # Start with baseline of 2 moves per pair and add the adjustments from diff.
        moves = curr + totalPairs * 2
        best = min(best, moves)
    
    return best

# Example usage:
# print(minMoves([1,2,4,3], 4))  # Output: 1
← Back to All Questions