Scale Engineer

Minimum Operations to Make the Array Alternating

Med
#1977Time: O(n log n). The dominant operation is sorting the `evens` and `odds` lists, which have lengths proportional to `n`.Space: O(n). We need to store the `evens` and `odds` lists, which together contain all `n` elements of the original array.
Patterns
GreedyCounting
Data structures
ArrayHash Table

Prompt

You are given a 0-indexed array nums consisting of n positive integers.

The array nums is called alternating if:

  • nums[i - 2] == nums[i], where 2 <= i <= n - 1.
  • nums[i - 1] != nums[i], where 1 <= i <= n - 1.

In one operation, you can choose an index i and change nums[i] into any positive integer.

Return the minimum number of operations required to make the array alternating.

 

Example 1:

Input: nums = [3,1,3,2,4,3]
Output: 3
Explanation:
One way to make the array alternating is by converting it to [3,1,3,1,3,1].
The number of operations required in this case is 3.
It can be proven that it is not possible to make the array alternating in less than 3 operations.

Example 2:

Input: nums = [1,2,2,2,2]
Output: 2
Explanation:
One way to make the array alternating is by converting it to [1,2,1,2,1].
The number of operations required in this case is 2.
Note that the array cannot be converted to [2,2,2,2,2] because in this case nums[0] == nums[1] which violates the conditions of an alternating array.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves separating the array elements based on their indices (even or odd) into two separate lists. These lists are then sorted to facilitate counting the frequencies of each number. By finding the most and second-most frequent numbers in each list, we can determine the optimal pair of values for the alternating array and calculate the minimum changes required.

Algorithm

  • Create two lists, evens and odds.
  • Iterate through nums from i = 0 to n-1. If i is even, add nums[i] to evens. If i is odd, add nums[i] to odds.
  • Sort the evens and odds lists.
  • Create a helper function getTopTwoFrequencies(List<Integer> list) that takes a sorted list and returns the values and counts of the two most frequent elements.
  • Call this helper for both evens and odds to get (even1_val, even1_count, even2_val, even2_count) and (odd1_val, odd1_count, odd2_val, odd2_count).
  • If even1_val != odd1_val, return n - (even1_count + odd1_count).
  • Otherwise, return n - max(even1_count + odd2_count, even2_count + odd1_count).

Walkthrough

First, we partition the input array nums into two sub-arrays: evens containing elements from even indices and odds containing elements from odd indices. We then sort both the evens and odds arrays in ascending order. After sorting, we can easily find the frequencies of all unique numbers in each sub-array by iterating through them. We need to identify the two most frequent numbers and their counts for both evens and odds. Let's denote them as (even1_val, even1_count), (even2_val, even2_count) for the evens array, and (odd1_val, odd1_count), (odd2_val, odd2_count) for the odds array. A helper function can be created to extract these top two frequencies from a sorted array in a single pass. The goal is to make the array alternating, like [v1, v2, v1, v2, ...], which means all even-indexed elements become v1 and all odd-indexed elements become v2, with v1 != v2. The number of operations is minimized by maximizing the number of elements we don't change. We consider two main scenarios:

  • If the most frequent element in evens (even1_val) is different from the most frequent element in odds (odd1_val), we can choose them as our target values. The number of elements we keep is even1_count + odd1_count. The operations needed are n - (even1_count + odd1_count).
  • If even1_val is the same as odd1_val, we cannot use both. We must choose the second-best option for either the even or odd positions. The two possibilities are: a) Use even1_val for even positions and odd2_val for odd positions. Kept elements: even1_count + odd2_count. b) Use even2_val for even positions and odd1_val for odd positions. Kept elements: even2_count + odd1_count. We choose the combination that maximizes the number of kept elements. The operations are n - max(even1_count + odd2_count, even2_count + odd1_count).
class Solution {    // Helper class to store frequency info    class Freq {        int val;        int count;        Freq(int v, int c) {            val = v;            count = c;        }    }     // Helper function to get top two frequencies from a sorted list    private List<Freq> getTopTwoFrequencies(List<Integer> list) {        if (list.isEmpty()) {            return Arrays.asList(new Freq(0, 0), new Freq(0, 0));        }         List<Freq> freqs = new ArrayList<>();        if (list.size() > 0) {            int currentVal = list.get(0);            int currentCount = 1;            for (int i = 1; i < list.size(); i++) {                if (list.get(i) == currentVal) {                    currentCount++;                } else {                    freqs.add(new Freq(currentVal, currentCount));                    currentVal = list.get(i);                    currentCount = 1;                }            }            freqs.add(new Freq(currentVal, currentCount));        }         freqs.sort((a, b) -> b.count - a.count);         Freq top1 = freqs.get(0);        Freq top2 = freqs.size() > 1 ? freqs.get(1) : new Freq(0, 0);        return Arrays.asList(top1, top2);    }     public int minimumOperations(int[] nums) {        int n = nums.length;        if (n <= 1) {            return 0;        }         List<Integer> evens = new ArrayList<>();        List<Integer> odds = new ArrayList<>();        for (int i = 0; i < n; i++) {            if (i % 2 == 0) {                evens.add(nums[i]);            } else {                odds.add(nums[i]);            }        }         Collections.sort(evens);        Collections.sort(odds);         List<Freq> evenFreqs = getTopTwoFrequencies(evens);        List<Freq> oddFreqs = getTopTwoFrequencies(odds);         int even1_val = evenFreqs.get(0).val;        int even1_count = evenFreqs.get(0).count;        int even2_count = evenFreqs.get(1).count;         int odd1_val = oddFreqs.get(0).val;        int odd1_count = oddFreqs.get(0).count;        int odd2_count = oddFreqs.get(1).count;         if (even1_val != odd1_val) {            return n - (even1_count + odd1_count);        } else {            return n - Math.max(even1_count + odd2_count, even2_count + odd1_count);        }    }}

Complexity

Time

O(n log n). The dominant operation is sorting the `evens` and `odds` lists, which have lengths proportional to `n`.

Space

O(n). We need to store the `evens` and `odds` lists, which together contain all `n` elements of the original array.

Trade-offs

Pros

  • Conceptually straightforward, leveraging a standard sorting algorithm.

  • Correctly solves the problem.

Cons

  • The O(n log n) time complexity from sorting is not optimal.

  • Requires O(n) extra space for the two sub-arrays.

Solutions

class Solution {private  int[] nums;private  int n;public  int minimumOperations(int[] nums) {    this.nums = nums;    n = nums.length;    int ans = Integer.MAX_VALUE;    for (int[] e1 : get(0)) {      for (int[] e2 : get(1)) {        if (e1[0] != e2[0]) {          ans = Math.min(ans, n - (e1[1] + e2[1]));        }      }    }    return ans;  }private  int[][] get(int i) {    Map<Integer, Integer> freq = new HashMap<>();    for (; i < n; i += 2) {      freq.put(nums[i], freq.getOrDefault(nums[i], 0) + 1);    }    int a = 0;    int n1 = 0;    int b = 0;    int n2 = 0;    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {      int k = e.getKey();      int v = e.getValue();      if (v > n1) {        b = a;        n2 = n1;        a = k;        n1 = v;      } else if (v > n2) {        b = k;        n2 = v;      }    }    return new int[][]{{a, n1}, {b, n2}};  }}

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