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.length2 <= n <= 1051 <= nums[i] <= limit <= 105n is even.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.
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.
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.
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.
Java
JavaScript
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.
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:
x + y = s.x + 1 \le s \le y + limit.2 \le s \le x or y + limit + 1 \le s \le 2 times limit.That is:
[2,..x], 2 replacements are needed.[x+1,..x+y-1], 1 replacement is needed.[x+y], no replacement is needed.[x+y+1,..y + limit], 1 replacement is needed.[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:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| 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. |
| Brute Force Simulation | Time Complexity: O(n * limit). The approach considers each pair for every possible target sum. |
| Difference Array | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Simulation | O(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. |
LeetCode 1674. Minimum Moves to Make Array Complementary • Happy Coding • 3,901 views views
Watch 6 more video solutions →Practice Minimum Moves to Make Array Complementary with our built-in code editor and test cases.
Practice on FleetCode