1674. Minimum Moves to Make Array Complementary

Time: O(n + limit)

Space: O(limit)

Intuition

Instead of checking all 2*limit possible targets and recounting moves for each, use a difference array to track incremental changes. For each complementary pair, determine when the move cost changes as the target increases. This reduces redundant recounting.

Algorithm

1Initialise delta array of size 2*limit+2.
2For each complementary pair (nums[i], nums[n-1-i]):
3 Determine ranges: if target ∈ [min(a,b)+1, a+b), exactly one element changes.
4 If target ∈ [a+b, max(a,b)+limit+1), both could need change or neither.
5 Use delta to mark range transitions: decrement at start, increment at end.
6Compute prefix sum of delta from target=2 to 2*limit, tracking minimum moves.

Example Walkthrough

Input: nums = [1,2,1,2], limit = 5

1.Pairs: (1,2) and (1,2).
2.For pair (1,2): min=1, max=2, sum=3.
3. delta[min+1]=delta[2]--; delta[sum]=delta[3]--; delta[sum+1]=delta[4]++; delta[max+limit+1]=delta[8]++.
4.Initial moves at target=2: both pairs need 1 move each, total=2.
5.Target=3: delta adds moves (or reduces); compute incrementally.
6.Continue through target=2*5=10, track minimum seen.

Output: varies based on exact deltas

Common Pitfalls

•The delta array tracks transitions in the move-cost function as target increases; understand that multiple pairs contribute simultaneously.
•Ranges depend on min, max, sum, and limit; off-by-one errors in boundaries are common.
•Start with moves at target=2 computed explicitly; subsequent targets use cumulative delta.

1674.cs

// Approach: Use a difference array (delta) to track move-count changes as target sum increases from 2 to 2*limit.
// For each pair (nums[i], nums[n-1-i]), determine the range of targets where one or both values need to change.
// Incrementally update the move count using cumulative deltas; track the minimum.
// Time: O(n + limit) Space: O(limit)

public class Solution
{
    public int MinMoves(int[] nums, int limit)
    {
        int n = nums.Length;
        int ans = n;
        // delta[i] := the number of moves needed when target goes from i - 1 to i
        int[] delta = new int[limit * 2 + 2];

        for (int i = 0; i < n / 2; ++i)
        {
            int a = nums[i];
            int b = nums[n - 1 - i];
            delta[Math.Min(a, b) + 1]--;
            delta[a + b]--;
            delta[a + b + 1]++;
            delta[Math.Max(a, b) + limit + 1]++;
        }

        // Initially, we need `moves` when the target is 2.
        for (int i = 2, moves = n; i <= limit * 2; ++i)
        {
            moves += delta[i];
            ans = Math.Min(ans, moves);
        }

        return ans;
    }
}

Was this solution helpful?