Skip to main content
Talentd

Minimum Moves to Make Array Complementary - Solution & Explanation

MediumArrayHash TablePrefix Sum15 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

You are 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, inclusive.

The array nums is complementary if for all indices i (0-indexed), nums[i] + nums[n - 1 - i] equals the same number. For example, the array [1,2,3,4] is complementary because for all indices i, nums[i] + nums[n - 1 - i] = 5.

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

 

Example 1:

Input: nums = [1,2,4,3], limit = 4
Output: 1
Explanation: 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
Explanation: 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
Explanation: nums is already complementary.

 

Constraints:

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

Approach Overview

Problem Overview: You are given an array nums and a value limit. The array is considered complementary if for every index i, the pair (nums[i], nums[n-1-i]) has the same sum. You can change any element to any value between 1 and limit. The task is to compute the minimum number of moves required so every mirrored pair produces the same target sum.

Approach 1: Brute Force Pair Simulation (O(n * limit) time, O(1) space)

Each mirrored pair contributes to a potential target sum between 2 and 2 * limit. The brute force strategy iterates over every possible target sum and calculates how many changes are required for all pairs to match that sum. For a pair (a, b), three cases exist: zero moves if a + b == target, one move if one value can be adjusted within [1, limit] to reach the target, otherwise two moves. You iterate through all n/2 pairs for every possible target sum. This approach clearly models the rules but becomes expensive when limit is large.

Approach 2: Sweep Line with Delta Array (O(n + limit) time, O(limit) space)

The optimized solution treats the problem as a range update problem using a sweep line idea built on prefix sum. For each pair (a, b), analyze how many moves are required for every possible target sum. Normally each pair costs two moves. However, within certain ranges the cost drops to one move, and exactly one value (the current sum a + b) requires zero moves. Instead of evaluating each target sum separately, update a delta array that records how the cost changes across ranges.

For each pair you mark intervals where the required moves decrease: from min(a,b)+1 to max(a,b)+limit the cost becomes one move, and at a+b the cost becomes zero. These changes are recorded using difference array updates. After processing all pairs, run a prefix accumulation over the delta array to compute the total moves for each possible target sum between 2 and 2*limit. The minimum value across this sweep is the answer.

This technique combines ideas from arrays, range updates, and prefix sums. Instead of recalculating costs repeatedly, it aggregates how each pair influences the global cost function.

Recommended for interviews: Start by describing the brute force reasoning so the interviewer sees you understand the pair constraints and move rules. Then transition to the sweep line optimization using a delta array. The optimized approach reduces the complexity to O(n + limit) and demonstrates strong understanding of prefix sums and range contribution techniques.

Approach 1: Sweep Line Technique using Delta Array

This approach involves using a delta array to track the number of moves required at different sum targets. We iterate through each pair and update the delta array to reflect how many changes are needed to achieve complementary sums across all pairs.

For each pair, calculate the impact on various ranges of sum values using the delta array, then compute the minimum moves required by iterating through these changes.

This Python function utilizes a delta array to manage the moves needed for each potential sum in the array. For each array pair, it updates the array with its constraints. The ultimate minimum move count is computed by iterating through possible sums and tracking the changes in move count.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n + limit). We iterate through the pairs and calculate a constant number of operations per pair, then sweep through a range determined by the limit.
Space Complexity: O(limit). We use an auxiliary array of size relative to the limit.

Try this approach in the editor →

Approach 2: Brute Force Simulation

In this approach, we simulate changes by examining the effect of each possible sum of elements at symmetric positions and manually adjusting values to reach consistency. While computationally intensive, this method can be helpful in understanding or verifying optimal solutions.

This Java solution simulates the problem by brute-forcing through each possible sum and counting the number of moves needed to adjust pairs accordingly. It uses loops to examine all combinations for potential replacement and identifies the minimum required changes.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(n * limit). The approach considers each pair for every possible target sum.
Space Complexity: O(1). Only a constant amount of additional space is used.

Try this approach in the editor →

Approach 3: Difference Array

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

Let's denote x as the smaller value between nums[i] and nums[n-i-1], and y as the larger value.

For each pair of numbers, we have the following scenarios:

  • If no replacement is needed, then x + y = s.
  • If one replacement is made, then x + 1 \le s \le y + limit.
  • If two replacements are made, then 2 \le s \le x or y + limit + 1 \le s \le 2 times limit.

That is:

  • In the range [2,..x], 2 replacements are needed.
  • In the range [x+1,..x+y-1], 1 replacement is needed.
  • At [x+y], no replacement is needed.
  • In the range [x+y+1,..y + limit], 1 replacement is needed.
  • In the range [y + limit + 1,..2 times limit], 2 replacements are needed.

We enumerate each pair of numbers and use a difference array to update the number of replacements needed in different ranges for each pair.

Finally, we find the minimum value among the prefix sums from index 2 to 2 times limit, which is the minimum number of replacements needed.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.

Similar problems:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sweep Line Technique using Delta Array

Time Complexity: O(n + limit). We iterate through the pairs and calculate a constant number of operations per pair, then sweep through a range determined by the limit.
Space Complexity: O(limit). We use an auxiliary array of size relative to the limit.

Brute Force Simulation

Time Complexity: O(n * limit). The approach considers each pair for every possible target sum.
Space Complexity: O(1). Only a constant amount of additional space is used.

Difference Array—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair SimulationO(n * limit)O(1)Good for understanding the rules and validating logic when constraints are small.
Sweep Line with Delta Array (Prefix Sum)O(n + limit)O(limit)Best for large inputs. Converts pair cost updates into range updates using prefix sum.

Video Solution

Minimum Moves to Make Array Complementary | Beginner Friendly | Super Detailed | Leetcode 1674 | MIK • codestorywithMIK • 10,329 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Moves to Make Array Complementary easy or hard?
The problem is rated Medium on LeetCode. The brute force logic is straightforward, but recognizing the sweep line optimization with a delta array and prefix sums requires stronger algorithmic insight.
Minimum Moves to Make Array Complementary Python/Java solution
Python and C++ implementations typically use the sweep line delta array method with prefix sums to achieve O(n + limit) complexity. Java and JavaScript versions can also implement the same optimized logic, though brute force simulations are sometimes used for clarity when constraints are smaller.
How to solve Minimum Moves to Make Array Complementary in O(n)?
Treat each mirrored pair as contributing cost changes across ranges of possible sums. Use a delta array to record where the move cost decreases from two moves to one move and where it becomes zero. After processing all pairs, compute a prefix sum over the delta array to determine the cost for each target sum. The smallest value is the answer.
What is the best approach for Minimum Moves to Make Array Complementary?
The most efficient approach uses a sweep line technique with a delta array and prefix sum. Instead of evaluating every possible target sum independently, each pair contributes range updates to a difference array. After processing all pairs, a prefix scan computes the total moves for each sum. This reduces the complexity to O(n + limit).
Is Minimum Moves to Make Array Complementary asked at Google/Amazon/Meta?
Problems involving sweep line techniques, prefix sums, and range contribution patterns frequently appear in interviews at companies like Google, Amazon, and Meta. This specific problem tests optimization skills and understanding of transforming brute force counting into prefix sum range updates.
What data structure is used in Minimum Moves to Make Array Complementary?
The optimized solution uses arrays and a difference (delta) array combined with prefix sum processing. No complex structures are required, but understanding range updates and cumulative sums is essential for achieving the optimal time complexity.
What is the time complexity of Minimum Moves to Make Array Complementary?
The optimal algorithm runs in O(n + limit) time and O(limit) space using a sweep line with prefix sum. A brute force strategy that checks every target sum for every pair takes O(n * limit) time and becomes inefficient when limit is large.

Ready to solve this problem?

Practice Minimum Moves to Make Array Complementary with our built-in code editor and test cases.

Practice on FleetCode
Previous

Zero Array Transformation II

Next

Zero Array Transformation III