Minimum Operations to Make the Array Alternating

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 theminimum number of operations required to make the array alternating.

Examples

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 <= 10^5
• 1 <= nums[i] <= 10^5

Solution

Method 1 – Counting & Greedy

Intuition

We want to alternate two values in the array, one for even indices and one for odd indices, and they must be different. The minimum operations is the total length minus the sum of the most frequent value in even positions and the most frequent value in odd positions, unless they are the same, in which case we must pick the second most frequent for one side.

Approach

1. Count the frequency of each value at even and odd indices separately.
2. Find the most and second most frequent values for both even and odd positions.
3. If the most frequent values for even and odd are different, use them; else, try both combinations using the second most frequent value for one side.
4. The answer is the minimum number of changes needed.
5. Edge case: If the array is already alternating, answer is 0.

Code

C++

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> even, odd;
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0) even[nums[i]]++;
            else odd[nums[i]]++;
        }
        vector<pair<int, int>> e, o;
        for (auto& p : even) e.push_back({p.second, p.first});
        for (auto& p : odd) o.push_back({p.second, p.first});
        sort(e.rbegin(), e.rend());
        sort(o.rbegin(), o.rend());
        int e1 = e.size() > 0 ? e[0].second : 0, e1c = e.size() > 0 ? e[0].first : 0;
        int e2c = e.size() > 1 ? e[1].first : 0;
        int o1 = o.size() > 0 ? o[0].second : 0, o1c = o.size() > 0 ? o[0].first : 0;
        int o2c = o.size() > 1 ? o[1].first : 0;
        if (e1 != o1) return n - e1c - o1c;
        return min(n - e1c - o2c, n - e2c - o1c);
    }
};

Go

func minOperations(nums []int) int {
    n := len(nums)
    even, odd := map[int]int{}, map[int]int{}
    for i, v := range nums {
        if i%2 == 0 {
            even[v]++
        } else {
            odd[v]++
        }
    }
    type pair struct{ cnt, val int }
    e, o := []pair{}, []pair{}
    for k, v := range even { e = append(e, pair{v, k}) }
    for k, v := range odd { o = append(o, pair{v, k}) }
    sort.Slice(e, func(i, j int) bool { return e[i].cnt > e[j].cnt })
    sort.Slice(o, func(i, j int) bool { return o[i].cnt > o[j].cnt })
    e1, e1c := 0, 0; if len(e) > 0 { e1, e1c = e[0].val, e[0].cnt }
    e2c := 0; if len(e) > 1 { e2c = e[1].cnt }
    o1, o1c := 0, 0; if len(o) > 0 { o1, o1c = o[0].val, o[0].cnt }
    o2c := 0; if len(o) > 1 { o2c = o[1].cnt }
    if e1 != o1 {
        return n - e1c - o1c
    }
    a := n - e1c - o2c
    b := n - e2c - o1c
    if a < b { return a } else { return b }
}

Java

class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> even = new HashMap<>(), odd = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) even.put(nums[i], even.getOrDefault(nums[i], 0) + 1);
            else odd.put(nums[i], odd.getOrDefault(nums[i], 0) + 1);
        }
        List<int[]> e = new ArrayList<>(), o = new ArrayList<>();
        for (var p : even.entrySet()) e.add(new int[]{p.getValue(), p.getKey()});
        for (var p : odd.entrySet()) o.add(new int[]{p.getValue(), p.getKey()});
        e.sort((a, b) -> b[0] - a[0]);
        o.sort((a, b) -> b[0] - a[0]);
        int e1 = e.size() > 0 ? e.get(0)[1] : 0, e1c = e.size() > 0 ? e.get(0)[0] : 0;
        int e2c = e.size() > 1 ? e.get(1)[0] : 0;
        int o1 = o.size() > 0 ? o.get(0)[1] : 0, o1c = o.size() > 0 ? o.get(0)[0] : 0;
        int o2c = o.size() > 1 ? o.get(1)[0] : 0;
        if (e1 != o1) return n - e1c - o1c;
        return Math.min(n - e1c - o2c, n - e2c - o1c);
    }
}

Kotlin

class Solution {
    fun minOperations(nums: IntArray): Int {
        val n = nums.size
        val even = mutableMapOf<Int, Int>()
        val odd = mutableMapOf<Int, Int>()
        for (i in nums.indices) {
            if (i % 2 == 0) even[nums[i]] = even.getOrDefault(nums[i], 0) + 1
            else odd[nums[i]] = odd.getOrDefault(nums[i], 0) + 1
        }
        val e = even.map { it.value to it.key }.sortedByDescending { it.first }
        val o = odd.map { it.value to it.key }.sortedByDescending { it.first }
        val e1 = if (e.isNotEmpty()) e[0].second else 0
        val e1c = if (e.isNotEmpty()) e[0].first else 0
        val e2c = if (e.size > 1) e[1].first else 0
        val o1 = if (o.isNotEmpty()) o[0].second else 0
        val o1c = if (o.isNotEmpty()) o[0].first else 0
        val o2c = if (o.size > 1) o[1].first else 0
        return if (e1 != o1) n - e1c - o1c else minOf(n - e1c - o2c, n - e2c - o1c)
    }
}

Python

from collections import Counter
class Solution:
    def minOperations(self, nums: list[int]) -> int:
        n = len(nums)
        even = Counter(nums[::2])
        odd = Counter(nums[1::2])
        e = even.most_common(2)
        o = odd.most_common(2)
        e1, e1c = e[0] if e else (0, 0)
        e2c = e[1][1] if len(e) > 1 else 0
        o1, o1c = o[0] if o else (0, 0)
        o2c = o[1][1] if len(o) > 1 else 0
        if e1 != o1:
            return n - e1c - o1c
        return min(n - e1c - o2c, n - e2c - o1c)

Rust

use std::collections::HashMap;
impl Solution {
    pub fn min_operations(nums: Vec<i32>) -> i32 {
        let n = nums.len() as i32;
        let mut even = HashMap::new();
        let mut odd = HashMap::new();
        for (i, &v) in nums.iter().enumerate() {
            if i % 2 == 0 {
                *even.entry(v).or_insert(0) += 1;
            } else {
                *odd.entry(v).or_insert(0) += 1;
            }
        }
        let mut e: Vec<(i32, i32)> = even.iter().map(|(&k, &v)| (v, k)).collect();
        let mut o: Vec<(i32, i32)> = odd.iter().map(|(&k, &v)| (v, k)).collect();
        e.sort_by(|a, b| b.0.cmp(&a.0));
        o.sort_by(|a, b| b.0.cmp(&a.0));
        let e1 = if !e.is_empty() { e[0].1 } else { 0 };
        let e1c = if !e.is_empty() { e[0].0 } else { 0 };
        let e2c = if e.len() > 1 { e[1].0 } else { 0 };
        let o1 = if !o.is_empty() { o[0].1 } else { 0 };
        let o1c = if !o.is_empty() { o[0].0 } else { 0 };
        let o2c = if o.len() > 1 { o[1].0 } else { 0 };
        if e1 != o1 {
            n - e1c - o1c
        } else {
            (n - e1c - o2c).min(n - e2c - o1c)
        }
    }
}

TypeScript

class Solution {
    minOperations(nums: number[]): number {
        const n = nums.length;
        const even = new Map<number, number>(), odd = new Map<number, number>();
        for (let i = 0; i < n; i++) {
            if (i % 2 === 0) even.set(nums[i], (even.get(nums[i]) ?? 0) + 1);
            else odd.set(nums[i], (odd.get(nums[i]) ?? 0) + 1);
        }
        const e = Array.from(even.entries()).map(([val, cnt]) => [cnt, val]).sort((a, b) => b[0] - a[0]);
        const o = Array.from(odd.entries()).map(([val, cnt]) => [cnt, val]).sort((a, b) => b[0] - a[0]);
        const e1 = e.length > 0 ? e[0][1] : 0, e1c = e.length > 0 ? e[0][0] : 0;
        const e2c = e.length > 1 ? e[1][0] : 0;
        const o1 = o.length > 0 ? o[0][1] : 0, o1c = o.length > 0 ? o[0][0] : 0;
        const o2c = o.length > 1 ? o[1][0] : 0;
        if (e1 !== o1) return n - e1c - o1c;
        return Math.min(n - e1c - o2c, n - e2c - o1c);
    }
}

Complexity

• ⏰ Time complexity: O(n) — We scan the array and count frequencies, then sort at most two small lists.
• 🧺 Space complexity: O(n) — We use extra space for the frequency maps.