# Minimum Operations to Make the Array Alternating
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-operations-to-make-the-array-alternating)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-make-the-array-alternating
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
---
## Problem
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
## Sorting-Based Frequency Counting
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.
**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.
**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.
### Explanation
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)`.
```java
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);
        }
    }
}
```
### 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)`.

## Optimal Approach using Frequency Counting
This approach provides an optimal solution by directly counting the frequencies of numbers at even and odd positions without the need for sorting. By using hash maps or frequency arrays, we can find the counts of all unique numbers in linear time. After identifying the top two most frequent numbers for both even and odd positions, we can apply the same logic as in the previous approach to find the minimum number of operations.
**Time:** O(n + V), where `n` is the length of the array and `V` is the maximum possible value of an element (10^5). `O(n)` for populating the frequency arrays and `O(V)` for finding the top two frequencies. Since `V` is a constant, this simplifies to `O(n)`. · **Space:** O(V). We use two frequency arrays of size `V+1`, where `V` is the maximum possible value (10^5). This is constant space as `V` is fixed.
**Pros:** Most efficient solution with linear time complexity.; Avoids the overhead of sorting.
**Cons:** Requires extra space for the frequency maps/arrays. The space is dependent on the range of values in the input array, which might be large, although it's constant in this problem (10^5).
### Explanation
The core idea is to determine the most frequent number for even-indexed positions and the most frequent number for odd-indexed positions. These will be our primary candidates for the two alternating values in the final array.
We use two frequency maps (or arrays, since the values are bounded up to 10^5), `even_counts` and `odd_counts`, to store the frequency of each number at even and odd indices, respectively.
We iterate through the input array `nums` once. For each element `nums[i]`, we update the corresponding frequency map based on whether the index `i` is even or odd.
After populating the maps, we iterate through each map to find the two most frequent numbers and their counts. Let's call them (`even1_val`, `even1_count`), (`even2_val`, `even2_count`) for even positions, and (`odd1_val`, `odd1_count`), (`odd2_val`, `odd2_count`) for odd positions. We initialize the counts of the second most frequent elements to 0 in case a sub-array contains only one unique number.
Finally, we calculate the minimum operations. The total number of operations is `n` minus the maximum number of elements we can keep.
- If the most frequent number for evens (`even1_val`) is different from the most frequent for odds (`odd1_val`), we can keep `even1_count + odd1_count` elements. The result is `n - (even1_count + odd1_count)`.
- If `even1_val == odd1_val`, we have a conflict. We must choose the second most frequent number for one of the positions. We compare keeping `even1_count + odd2_count` versus `even2_count + odd1_count` and take the maximum. The result is `n - max(even1_count + odd2_count, even2_count + odd1_count)`.
```java
class Solution {
    public int minimumOperations(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return 0;
        }

        // Since values are <= 10^5, we can use arrays as frequency maps.
        int[] evenCounts = new int[100001];
        int[] oddCounts = new int[100001];

        int evenLen = 0;
        int oddLen = 0;

        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                evenCounts[nums[i]]++;
                evenLen++;
            } else {
                oddCounts[nums[i]]++;
                oddLen++;
            }
        }

        int even1_val = 0, even1_count = 0;
        int even2_val = 0, even2_count = 0;
        for (int i = 1; i <= 100000; i++) {
            if (evenCounts[i] > even1_count) {
                even2_count = even1_count;
                even2_val = even1_val;
                even1_count = evenCounts[i];
                even1_val = i;
            } else if (evenCounts[i] > even2_count) {
                even2_count = evenCounts[i];
                even2_val = i;
            }
        }

        int odd1_val = 0, odd1_count = 0;
        int odd2_val = 0, odd2_count = 0;
        for (int i = 1; i <= 100000; i++) {
            if (oddCounts[i] > odd1_count) {
                odd2_count = odd1_count;
                odd2_val = odd1_val;
                odd1_count = oddCounts[i];
                odd1_val = i;
            } else if (oddCounts[i] > odd2_count) {
                odd2_count = oddCounts[i];
                odd2_val = i;
            }
        }

        if (even1_val != odd1_val) {
            return n - (even1_count + odd1_count);
        } else {
            // Two choices if most frequent are the same
            // 1. Keep most frequent for evens, second most for odds
            int changes1 = (evenLen - even1_count) + (oddLen - odd2_count);
            // 2. Keep second most for evens, most frequent for odds
            int changes2 = (evenLen - even2_count) + (oddLen - odd1_count);
            return Math.min(changes1, changes2);
            // This is equivalent to:
            // return n - Math.max(even1_count + odd2_count, even2_count + odd1_count);
        }
    }
}
```
### Algorithm
- Initialize two frequency arrays, `even_counts` and `odd_counts`, of size 100001 to zero.
- Get the total number of elements `n`, and the number of elements at even (`len_even`) and odd (`len_odd`) positions.
- Iterate through `nums` from `i = 0` to `n-1`. If `i` is even, increment `even_counts[nums[i]]`. If `i` is odd, increment `odd_counts[nums[i]]`.
- Find the top two frequencies for `even_counts`. Iterate from 1 to 100000, keeping track of the top two counts and their corresponding values (`even1_val`, `even1_count`, `even2_val`, `even2_count`).
- Do the same for `odd_counts` to find (`odd1_val`, `odd1_count`, `odd2_val`, `odd2_count`).
- If `even1_val != odd1_val`, the minimum operations is `(len_even - even1_count) + (len_odd - odd1_count)`, which simplifies to `n - (even1_count + odd1_count)`.
- If `even1_val == odd1_val`, the minimum operations is the minimum of two choices:
a) Change evens to `even1_val` and odds to `odd2_val`: `(len_even - even1_count) + (len_odd - odd2_count)`.
b) Change evens to `even2_val` and odds to `odd1_val`: `(len_even - even2_count) + (len_odd - odd1_count)`.
This simplifies to `n - max(even1_count + odd2_count, even2_count + odd1_count)`.

# Solutions
### Java

```java
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}};
  }
}

```

### CPP

```cpp
typedef pair < int , int > PII ; class Solution { public: int minimumOperations ( vector < int >& nums ) { int ans = INT_MAX ; int n = nums . size (); for ( auto & [ a , n1 ] : get ( 0 , nums )) for ( auto & [ b , n2 ] : get ( 1 , nums )) if ( a != b ) ans = min ( ans , n - ( n1 + n2 )); return ans ; } vector < PII > get ( int i , vector < int >& nums ) { unordered_map < int , int > freq ; for (; i < nums . size (); i += 2 ) ++ freq [ nums [ i ]]; int a = 0 , n1 = 0 , b = 0 , n2 = 0 ; for ( auto & [ k , v ] : freq ) { if ( v > n1 ) { b = a ; n2 = n1 ; a = k ; n1 = v ; } else if ( v > n2 ) { b = k ; n2 = v ; } } return { { a , n1 }, { b , n2 } }; } };
```

### Python

```python
class Solution:
    def minimumOperations(self, nums: List[int]) -> int: def get(i): c = Counter(nums[i:: 2]). most_common(2) if not c: return [(0, 0), (0, 0)] if len(c) == 1: return [c[0], (0, 0)] return c n = len(nums) return min(n - (n1 + n2) for a, n1 in get(0) for b, n2 in get(1) if a != b)

```