Minimum Moves to Make Array Complementary solution and explanation
Google
9 more videos on this problem
Minimum Moves to Make Array Complementary | Beginner Friendly | Super Detailed | Leetcode 1674 | MIKcodestorywithMIK · 55:12 · 10K views
LeetCode 1674. Minimum Moves to Make Array ComplementaryHappy Coding · 27:11 · 4K views
1674. Minimum Moves to Make Array Complementary | Leetcode Daily - PythonLeetcode Daily · 8:12 · 4K views
leetcode 1674 | Minimum Moves to Make Array Complementary | Leetcode POTD | Prefix sum | DSACode With Vick · 21:30 · 2K views
Minimum Moves to Make Array Complementary | LeetCode 1674 | Brute Force | Prefix SumStreak To Scale · 17:39 · 2K views
1674. Minimum Moves to Make Array Complementary (Leetcode Medium)Programming Live with Larry · 43:29 · 1K views
Minimum Moves to Make Array Complementary | Leetcode - 1674Shivam Gupta · 24:21 · 1K views
Leetcode 1674. Minimum Moves to Make Array Complementary (1d difference array)LetsCode · 19:25 · 921 views
Minimum Moves to Make Array Complementary | LeetCode 1674 | Java Code | Developer CoderDeveloper Coder · 30:07 · 647 views
Daily Leetcode #2234: May 13, 2026 - 1674. Minimum Moves to Make Array ComplementaryProgramming Live with Larry · 28:39 · 541 views
The problem
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 <= 105nis 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.
def min_moves(nums, limit):
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)
delta[2] += 2
delta[low] -= 1
delta[a + b] -= 1
delta[a + b + 1] += 1
delta[high + 1] += 1
moves = float('inf')
current_moves = 0
for sum_ in range(2, 2 * limit + 1):
current_moves += delta[sum_]
if sum_ >= n:
moves = min(moves, current_moves)
return moves#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int minMoves(vector<int>& nums, int limit) {
int n = nums.size();
vector<int> delta(2 * limit + 2, 0);
for (int i = 0; i < n / 2; ++i) {
int a = nums[i];
int b = nums[n - i - 1];
int low = 1 + min(a, b);
int high = limit + max(a, b);
delta[2] += 2;
delta[low] -= 1;
delta[a + b] -= 1;
delta[a + b + 1] += 1;
delta[high + 1] += 1;
}
int moves = INT_MAX;
int current_moves = 0;
for (int sum = 2; sum <= 2 * limit; ++sum) {
current_moves += delta[sum];
if (sum >= n) {
moves = min(moves, current_moves);
}
}
return moves;
}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.
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.
public int minMoves(int[] nums, int limit) {
int n = nums.length;
int minMoves = n; // worst case is changing every pair
for (int target = 2; target <= 2 * limit; ++target) {
int currentMoves = 0;
for (int i = 0; i < n / 2; ++i) {
int a = nums[i];
int b = nums[n - 1 - i];
int sumAB = a + b;
if (sumAB != target) {
currentMoves += 2; // Initially assume both need change
// Try minimizing: Check possibilities
if (target - a >= 1 && target - a <= limit) --currentMoves;
if (target - b >= 1 && target - b <= limit) --currentMoves;
}
}
minMoves = Math.min(minMoves, currentMoves);
}
return minMoves;
}function minMoves(nums, limit) {
let n = nums.length;
let minMoves = n;
for (let target = 2; target <= 2 * limit; ++target) {
let currentMoves = 0;
for (let i = 0; i < n / 2; ++i) {
let a = nums[i];
let b = nums[n - 1 - i];
let sumAB = a + b;
if (sumAB !== target) {
currentMoves += 2;
if (target - a >= 1 && target - a <= limit) currentMoves -= 1;
if (target - b >= 1 && target - b <= limit) currentMoves -= 1;
}
}
minMoves = Math.min(minMoves, currentMoves);
}
return minMoves;
}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.
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.
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 xory + limit + 1 \le s \le 2 times limit.
That is:
- In the range
[2,..x],2replacements are needed. - In the range
[x+1,..x+y-1],1replacement is needed. - At
[x+y], no replacement is needed. - In the range
[x+y+1,..y + limit],1replacement is needed. - In the range
[y + limit + 1,..2 times limit],2replacements 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:
function minMoves(nums: number[], limit: number): number {
const n = nums.length;
const d: number[] = Array(limit * 2 + 2).fill(0);
for (let i = 0; i < n >> 1; ++i) {
const x = Math.min(nums[i], nums[n - 1 - i]);
const y = Math.max(nums[i], nums[n - 1 - i]);
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;
}
let ans = n;
let s = 0;
for (let i = 2; i < d.length; ++i) {
s += d[i];
ans = Math.min(ans, s);
}
return ans;
}func minMoves(nums []int, limit int) int {
n := len(nums)
d := make([]int, 2*limit+2)
for i := 0; i < n/2; i++ {
x, y := nums[i], nums[n-1-i]
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
}
ans, s := n, 0
for _, x := range d[2:] {
s += x
ans = min(ans, s)
}
return ans
}Complexity comparison
| 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 | – |
Complexity analysis
| 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. |
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.