Minimum Moves to Make Array Complementary

Medium
1352.

Minimum Moves to Make Array Complementary

Minimum Moves to Make Array Complementary is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon and Google interviews.

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.length
  • 2 <= n <= 10^5
  • 1 <= nums[i] <= limit <= 10^5
  • n is even
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} limit
 * @return {number}
 */
var minMoves = function(nums, limit) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.length
  • 2 <= n <= 10^5
  • 1 <= nums[i] <= limit <= 10^5
  • n is even

Hints for Minimum Moves to Make Array Complementary

  1. Hint 1

    Try every possible common sum T from 2 to 2 * limit. For one pair (a, b), how many moves does it need to reach T?

  2. Hint 2

    A pair costs 0 if a + b == T; 1 if T lies in [min(a,b) + 1, max(a,b) + limit] (change only the bigger or only the smaller element); otherwise 2.

  3. Hint 3

    Each pair's cost as a function of T is a step function with four breakpoints. Add all of them into a difference array over T and 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

  1. Create a difference array diff over sums 0 .. 2 * limit + 1.
  2. For each pair (a, b) with lo = min(a, b) and hi = max(a, b): the cost starts at 2 (diff[2] += 2), drops to 1 from lo + 1 (diff[lo + 1] -= 1), drops to 0 at exactly a + b (diff[a + b] -= 1, diff[a + b + 1] += 1), and returns to 2 after hi + limit (diff[hi + limit + 1] += 1).
  3. Sweep T from 2 to 2 * limit, keeping a running sum of diff; the running sum is the total moves for that T.
  4. 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 T against 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 * limit are 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 best

Java

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