#1674

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Minimum Moves to Make Array Complementary

Find the minimum moves to make an array complementary by analyzing paired sums and using hash lookups for efficiency.

Problem Statement

Given an integer array nums of even length n and an integer limit, you can replace any number in nums with an integer between 1 and limit in one move. Your goal is to minimize the total number of moves needed to transform nums.

An array is complementary if, for all indices i, the sum nums[i] + nums[n - 1 - i] is equal across every pair. Return the minimum number of moves required to make nums complementary.

Examples

Example 1

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

Output: 1

In 1 move, you can change nums to [1,2,2,3] (underlined elements are changed). nums[0] + nums[3] = 1 + 3 = 4. nums[1] + nums[2] = 2 + 2 = 4. nums[2] + nums[1] = 2 + 2 = 4. nums[3] + nums[0] = 3 + 1 = 4. Therefore, nums[i] + nums[n-1-i] = 4 for every i, so nums is complementary.

Example 2

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

Output: 2

In 2 moves, you can change nums to [2,2,2,2]. You cannot change any number to 3 since 3 > limit.

Example 3

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

Output: 0

nums is already complementary.

Constraints

n == nums.length
2 <= n <= 105
1 <= nums[i] <= limit <= 105
n is even.

Solution Approach

Pair Analysis and Target Range

For each pair nums[i] and nums[n-1-i], calculate the minimum and maximum sum achievable with at most one move. Store the effects of 0, 1, or 2 moves in a prefix sum array to efficiently track total changes for every possible target sum.

Prefix Sum Aggregation

Increment and decrement the prefix sum array at the boundaries of each pair's impact. After processing all pairs, scan the array to compute cumulative moves needed for each potential complementary sum, capturing the minimal total efficiently.

Result Selection

Select the target sum that results in the lowest cumulative moves. This step leverages the array scanning plus hash lookup pattern, avoiding nested loops over every sum and keeping time complexity linear relative to array length and limit.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + limit) due to scanning each pair and updating the prefix sum array, while space complexity is O(limit) to store the range modifications for sums.

What Interviewers Usually Probe

Asks about optimizing without checking every possible sum explicitly.
Hints at using prefix sum or cumulative counting for range updates.
Wants discussion on handling pairs with 0, 1, or 2 required moves.

Common Pitfalls or Variants

Common pitfalls

Assuming every pair always requires exactly one move without checking current sum.
Overlooking the range boundaries when updating prefix sums, leading to incorrect totals.
Using brute-force nested loops over all sums, causing timeouts on large limits.

Follow-up variants

Finding minimal moves when array can have odd length and one unmatched element.
Allowing replacements outside 1 to limit, introducing negative or larger sums.
Determining complementary arrays under additional constraints, such as fixed first element.

FAQ

What does 'array scanning plus hash lookup' mean in this problem?

It refers to scanning each pair of nums[i] and nums[n-1-i] while using a hash or prefix sum array to track move ranges for every possible sum.

Can we solve this problem without a prefix sum array?

Yes, but without prefix sums, counting moves for all target sums becomes less efficient and may lead to timeouts on large arrays or limits.

Why does each pair contribute 0, 1, or 2 moves?

Because a pair's current sum might already match the target (0 moves), need one element replaced (1 move), or require changing both numbers (2 moves) to reach a specific sum.

Is it necessary to consider every possible target sum between 2 and 2*limit?

Yes, because each pair's sum range can influence which total sum yields minimal moves, and ignoring any possible sum could miss the optimal solution.

How do we apply this approach to the example nums = [1,2,4,3], limit = 4?

Analyze pairs (1,3) and (2,4), update prefix sums for move ranges, then find the target sum with minimal cumulative moves, which is 1 in this case.

terminal

Solution

Solution 1: Difference Array

Assume that in the final array, the sum of the pair $\textit{nums}[i]$ and $\textit{nums}[n-i-1]$ is $s$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        d = [0] * (2 * limit + 2)
        n = len(nums)
        for i in range(n // 2):
            x, y = nums[i], nums[-i - 1]
            if x > y:
                x, y = y, x
            d[2] += 2
            d[x + 1] -= 2
            d[x + 1] += 1
            d[x + y] -= 1
            d[x + y + 1] += 1
            d[y + limit + 1] -= 1
            d[y + limit + 1] += 2
        return min(accumulate(d[2:]))

Continue Practicing

#1658 minimum operations to reduce x to zero #1590 make sum divisible by p #1546 maximum number of non overlapping subarrays with sum equals target