We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Array Changes to Make Differences Equal

Number: 3498

Difficulty: Medium

Paid? No

Companies: Google, Airbus SE

Problem Description

Given an even‐length integer array nums and an integer k, you can change any element (to any integer in the range [0, k]) an arbitrary number of times. Your goal is to achieve that there exists some nonnegative integer X such that for every symmetric pair (nums[i], nums[n-i-1]), the absolute difference |nums[i] - nums[n-i-1]| equals X. Return the minimum number of changes required.

Key Insights

  • We work with symmetric pairs; let m = n/2.

  • For each pair (a, b), the “current difference” is diff = |a - b|. If diff already equals the chosen X, no change is needed.

  • With one change on exactly one of the two numbers we may get the required difference X—but only when X is “reachable.” In particular, when keeping one element fixed, one may adjust the other to either (fixed + X) or (fixed - X) provided the new value remains in [0,k].

  • For each pair the best we can do is:

    • 0 operations if X equals the original diff.
    • 1 operation if X differs from diff but X is within “reach” by changing one number.
    • 2 operations otherwise (because with two changes we can choose any pair having difference X as long as some valid pair exists in [0,k]).

  • A key trick is to pre‐compute, for every symmetric pair, the largest value T for which one of the two numbers can be “fixed” so that a single change on its partner is enough. In fact, for a pair (a, b) we have:

    T = max(a, b, k - a, k - b)

    so that for any X in [0, T] one change is enough (if X is not already equal to diff) while for X > T two changes are forced.

  • Then, the cost for that pair when choosing a target difference X is:

    • 0 if X == diff
    • 1 if X ≤ T and X != diff
    • 2 if X > T

  • We can “sweep” over all potential target values X in the range [0,k] efficiently using a difference array and a frequency table of the original diffs.

  • Finally, the total minimum cost equals the minimum over all X in [0,k] of:

    Total cost(X) = (2 * m) – (# of pairs that can be fixed with one change for this X) – (number of pairs that already have diff == X).

Space and Time Complexity

Time Complexity: O(n + k)
Space Complexity: O(k)
(Here n is the length of nums and k is the given bound; note that k can be as large as 10^5.)

Solution

We start by noting that every symmetric pair (a, b) can be “fixed” as follows:

  • If the current absolute difference diff equals our target X, no change is needed.

  • Otherwise, we check if one change is enough. One change is sufficient if X is not “too large” compared to a and b (more precisely, if X ≤ T where T = max(a, b, k - a, k - b)). If X is larger than T, one change will not let you reach X (for example, if both numbers are 3 and k=6 then you cannot get a difference of 4 by changing only one element because 3+4 is 7 which is out of range and 3-4 is negative).

  • To efficiently try all possible X (from 0 to k), we initially assume every pair would cost 2 changes. Then, for each pair, for every X in [0, T] we “save” one change (using a difference array technique). Also, if the pair’s current difference is diff, we record an extra saving (i.e. cost becomes 0 rather than 1) when X equals diff.

  • After processing every pair, for each X in [0,k] the total cost becomes:

    Total cost(X) = (2 * (n/2)) – (number of pairs with X ≤ T for that pair) – (frequency of X as the original difference)

    and we take the minimum over all X.

The solution uses a difference array to accumulate the “one-change saves” per valid X interval and then a frequency array for pairs that need 0 changes. Finally, we iterate over X in [0,k] to compute the candidate cost and choose the minimum.

Code Solutions

# Python solution with line-by-line comments

def minArrayChanges(nums, k):
    n = len(nums)
    m = n // 2  # number of symmetric pairs
    max_k = k  # valid target differences range from 0 to k

    # Initialize a difference array for one-change savings
    one_change_diff = [0] * (max_k + 2)

    # Frequency array for pairs that already have a given diff (0-change possibility)
    freq = [0] * (max_k + 1)

    # Process each symmetric pair
    for i in range(m):
        a = nums[i]
        b = nums[n - i - 1]
        diff = abs(a - b)
        # For a pair (a, b), one-change is possible for any target X that is at most:
        # T = max(a, b, k - a, k - b)
        T = max(a, b, k - a, k - b)
        # One-change saving is applicable for all X in [0, T]
        one_change_diff[0] += 1
        one_change_diff[T + 1] -= 1
        # Record the frequency for the original difference -> 0 operations needed if we choose this X.
        freq[diff] += 1

    # Build prefix array from the difference array to know for each X how many pairs can be fixed with one change.
    one_change_possible = [0] * (max_k + 1)
    running = 0
    for X in range(max_k + 1):
        running += one_change_diff[X]
        one_change_possible[X] = running

    total_pairs = m
    min_operations = float('inf')
    # For each possible target difference X in [0,k], compute total cost
    for X in range(max_k + 1):
        # Base cost: assume 2 changes for every pair.
        total_cost = 2 * total_pairs
        # For every pair where X is within range [0, T] we gain a saving of one operation.
        total_cost -= one_change_possible[X]
        # For every pair already having diff = X, we gain an additional saving (making cost 0 for that pair).
        total_cost -= freq[X]
        if total_cost < min_operations:
            min_operations = total_cost
    return min_operations

# Example usage:
print(minArrayChanges([1,0,1,2,4,3], 4))  # Expected output: 2
print(minArrayChanges([0,1,2,3,3,6,5,4], 6))  # Expected output: 2
← Back to All Questions