Minimum Moves to Make Array Complementary — Solution
Minimum Moves to Make Array Complementary solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Moves to Make Array Complementary is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums of even length n and an integer limit. In one move you may replace any single element of nums with any integer between 1 and limit, inclusive.
The array is complementary when every mirrored pair has the same sum: there is one number T with nums[i] + nums[n - 1 - i] == T for every index i. For example, [1,2,3,4] is complementary because both pairs sum to 5.
Return the minimum number of moves needed to make nums complementary.
Example 1
Input: nums = [2,5,3,4], limit = 5
Output: 1
Explanation: The pairs are (2,4) with sum 6 and (5,3) with sum 8. Changing the 5 to a 3 makes both sums 6.
Example 2
Input: nums = [3,1,1,3], limit = 3
Output: 2
Explanation: The pairs (3,3) and (1,1) sum to 6 and 2. One change moves (3,3) only to sums 4..6 and (1,1) only to sums 2..4, so no target is fixed by a single move; target 4 costs one move per pair, e.g. `[3,1,3,1]`.
Example 3
Input: nums = [4,1,6,3], limit = 6
Output: 0
Explanation: Both pairs already sum to 7.
Constraints
n == nums.length2 <= n <= 10^51 <= nums[i] <= limit <= 10^5n is even
Hints for Minimum Moves to Make Array Complementary
Hint 1
Try every possible common sum
Tfrom2to2 * limit. For one pair(a, b), how many moves does it need to reachT?Hint 2
A pair costs 0 if
a + b == T; 1 ifTlies in[min(a,b) + 1, max(a,b) + limit](change only the bigger or only the smaller element); otherwise 2.Hint 3
Each pair's cost as a function of
Tis a step function with four breakpoints. Add all of them into a difference array overTand take the smallest prefix sum.
How to solve Minimum Moves to Make Array Complementary
For a fixed target sum T, each mirrored pair independently needs 0, 1 or 2 moves, and its cost changes only at four points. Recording those changes in a difference array lets us evaluate every T at once.
Approach
- Create a difference array
diffover sums0 .. 2 * limit + 1. - For each pair
(a, b)withlo = min(a, b)andhi = max(a, b): the cost starts at 2 (diff[2] += 2), drops to 1 fromlo + 1(diff[lo + 1] -= 1), drops to 0 at exactlya + b(diff[a + b] -= 1,diff[a + b + 1] += 1), and returns to 2 afterhi + limit(diff[hi + limit + 1] += 1). - Sweep
Tfrom 2 to2 * limit, keeping a running sum ofdiff; the running sum is the total moves for thatT. - Return the smallest running sum.
Why it works
Changing one element of the pair (a, b) can produce any sum from lo + 1 (replace hi by 1) to hi + limit (replace lo by limit), and two changes reach any sum in [2, 2 * limit]. So the per-pair cost is exactly 2 / 1 / 0 / 1 / 2 across those breakpoints, and since pairs are independent the total for a given T is the sum of the pair costs — which is what the prefix sum of the difference array computes.
Complexity
- Time —
O(n + limit) - Space —
O(limit)
Pitfalls
- Trying every
Tagainst every pair directly is O(n · limit) — up to 10^10 operations. - The one-move range is
[lo + 1, hi + limit], built from the smaller and the larger element respectively; swapping them gives wrong bounds. - The target must be reachable for every pair, so only sums
2 .. 2 * limitare candidates.
Reference solution
Python
from typing import List
def minMoves(nums: List[int], limit: int) -> int:
n = len(nums)
diff = [0] * (2 * limit + 2)
for i in range(n // 2):
a = nums[i]
b = nums[n - 1 - i]
lo = min(a, b)
hi = max(a, b)
diff[2] += 2
diff[lo + 1] -= 1
diff[a + b] -= 1
diff[a + b + 1] += 1
diff[hi + limit + 1] += 1
best = n
cur = 0
for t in range(2, 2 * limit + 1):
cur += diff[t]
if cur < best:
best = cur
return bestJava
public static int minMoves(int[] nums, int limit) {
int n = nums.length;
int[] diff = new int[2 * limit + 2];
for (int i = 0; i < n / 2; i++) {
int a = nums[i], b = nums[n - 1 - i];
int lo = Math.min(a, b), hi = Math.max(a, b);
diff[2] += 2;
diff[lo + 1] -= 1;
diff[a + b] -= 1;
diff[a + b + 1] += 1;
diff[hi + limit + 1] += 1;
}
int best = n, cur = 0;
for (int t = 2; t <= 2 * limit; t++) {
cur += diff[t];
if (cur < best) best = cur;
}
return best;
}C++
int minMoves(vector<int>& nums, int limit) {
int n = nums.size();
vector<int> diff(2 * limit + 2, 0);
for (int i = 0; i < n / 2; i++) {
int a = nums[i], b = nums[n - 1 - i];
int lo = min(a, b), hi = max(a, b);
diff[2] += 2;
diff[lo + 1] -= 1;
diff[a + b] -= 1;
diff[a + b + 1] += 1;
diff[hi + limit + 1] += 1;
}
int best = n, cur = 0;
for (int t = 2; t <= 2 * limit; t++) {
cur += diff[t];
if (cur < best) best = cur;
}
return best;
}JavaScript
var minMoves = function(nums, limit) {
var n = nums.length;
var diff = new Array(2 * limit + 2).fill(0);
for (var i = 0; i < n / 2; i++) {
var a = nums[i], b = nums[n - 1 - i];
var lo = Math.min(a, b), hi = Math.max(a, b);
diff[2] += 2;
diff[lo + 1] -= 1;
diff[a + b] -= 1;
diff[a + b + 1] += 1;
diff[hi + limit + 1] += 1;
}
var best = n, cur = 0;
for (var t = 2; t <= 2 * limit; t++) {
cur += diff[t];
if (cur < best) best = cur;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets