Scale Engineer

Minimum Moves to Make Array Complementary

Med
#1536Time: O(n * limit). The outer loop runs `2 * limit` times, and for each iteration, the inner loop runs `n/2` times.Space: O(1), as we only use a few variables to store counts and intermediate values.1 company
Patterns
Prefix Sum
Data structures
ArrayHash Table
Companies
CureFit

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves checking every possible target sum for the pairs (nums[i], nums[n-1-i]). The possible sums range from 2 (by changing both numbers to 1) to 2 * limit (by changing both to limit). For each potential target sum, we calculate the total number of moves required to make all pairs sum up to it. We keep track of the minimum moves found across all target sums.

Algorithm

  • Initialize minMoves to a very large value, for instance, n (the maximum possible moves).
  • Iterate through every possible targetSum from 2 to 2 * limit.
  • For each targetSum, initialize a counter currentMoves to 0.
  • Iterate through the first half of the array, considering pairs (nums[i], nums[n - 1 - i]).
  • For each pair (a, b):
    • If a + b == targetSum, the cost is 0 moves.
    • If a + b != targetSum but the targetSum can be achieved with one change (i.e., targetSum is in the range [1 + min(a, b), limit + max(a, b)]), add 1 to currentMoves.
    • Otherwise, two changes are necessary, so add 2 to currentMoves.
  • After checking all pairs, currentMoves holds the total moves for the current targetSum. Update minMoves = min(minMoves, currentMoves).
  • After iterating through all possible targetSum values, minMoves will hold the minimum moves required.

Walkthrough

The core idea is to find a targetSum that minimizes the total moves. The targetSum can range from 2 to 2 * limit.

We iterate through each possible targetSum in this range. For each targetSum, we then iterate through all n/2 pairs of elements (a, b) where a = nums[i] and b = nums[n - 1 - i]. For each pair, we calculate the moves needed to make their sum equal to targetSum:

  • 0 moves: if a + b is already equal to targetSum.
  • 1 move: if a + b != targetSum, but we can change just one of the numbers to achieve the targetSum. This is possible if the targetSum is within the range [1 + min(a, b), limit + max(a, b)].
  • 2 moves: if we must change both numbers. This is the case for any targetSum that cannot be achieved with 0 or 1 move.

We sum the moves for all pairs to get the total moves for the current targetSum. The minimum of these totals over all possible targetSums is the answer.

class Solution {    public int minMoves(int[] nums, int limit) {        int n = nums.length;        int minMoves = n; // Maximum possible moves         for (int targetSum = 2; targetSum <= 2 * limit; targetSum++) {            int currentMoves = 0;            for (int i = 0; i < n / 2; i++) {                int a = nums[i];                int b = nums[n - 1 - i];                                if (a + b == targetSum) {                    // 0 moves needed                    continue;                }                                int minVal = Math.min(a, b);                int maxVal = Math.max(a, b);                if (targetSum >= 1 + minVal && targetSum <= limit + maxVal) {                    currentMoves += 1;                } else {                    currentMoves += 2;                }            }            minMoves = Math.min(minMoves, currentMoves);        }        return minMoves;    }}

Complexity

Time

O(n * limit). The outer loop runs `2 * limit` times, and for each iteration, the inner loop runs `n/2` times.

Space

O(1), as we only use a few variables to store counts and intermediate values.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires minimal space.

Cons

  • The time complexity is very high, making it impractical for the given constraints.

  • It will result in a 'Time Limit Exceeded' error on most online judges for this problem.

Solutions

class Solution {public  int minMoves(int[] nums, int limit) {    int n = nums.length;    int[] d = new int[limit * 2 + 2];    for (int i = 0; i < n >> 1; ++i) {      int a = Math.min(nums[i], nums[n - i - 1]);      int b = Math.max(nums[i], nums[n - i - 1]);      d[2] += 2;      d[limit * 2 + 1] -= 2;      d[a + 1] -= 1;      d[b + limit + 1] += 1;      d[a + b] -= 1;      d[a + b + 1] += 1;    }    int ans = n, s = 0;    for (int i = 2; i <= limit * 2; ++i) {      s += d[i];      if (ans > s) {        ans = s;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem