.jpg)
Minimum Operations to Make an Array Alternating
Problem Statement
You are given an integer array nums.
An array is called alternating if:
- For all even indices i, nums[i] are equal
- For all odd indices i, nums[i] are equal
- Value at even indices ≠ value at odd indices
In one operation, you can change any element to any value.
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
- Even indices → [3,3,4]
- Odd indices → [1,2,3]
- Best choice:
- Even → 3
- Odd → 1
- Changes needed = 3
Example 2
Input
nums = [1,2,2,2,2]
Output
2
Why This Problem Is Important
- Tests frequency counting
- Greedy decision making
- Edge case handling (same dominant values)
- Common interview problem (Google, Amazon)
Key Observation
- Even indices and odd indices are independent
- Count frequencies separately for:
- Even positions
- Odd positions
- Choose most frequent values
- If top values clash, use second best
Approach 1: Frequency Count + Greedy (Optimal)
Idea
- Count frequency of numbers at even indices
- Count frequency of numbers at odd indices
- Pick the most frequent value for each
- If both values are different → optimal
- If same → try second best option
Time and Space Complexity
- Time: O(n)
- Space: O(n)
Python Implementation
from collections import Counter
def minimumOperations(nums):
n = len(nums)
if n <= 1:
return 0
even = Counter()
odd = Counter()
for i in range(n):
if i % 2 == 0:
even[nums[i]] += 1
else:
odd[nums[i]] += 1
even_common = even.most_common()
odd_common = odd.most_common()
even_val, even_freq = even_common[0]
odd_val, odd_freq = odd_common[0]
if even_val != odd_val:
return n - (even_freq + odd_freq)
even_second = even_common[1][1] if len(even_common) > 1 else 0
odd_second = odd_common[1][1] if len(odd_common) > 1 else 0
return min(
n - (even_freq + odd_second),
n - (odd_freq + even_second)
)
C++ Implementation
#include
using namespace std;
int minimumOperations(vector& nums) {
int n = nums.size();
if (n <= 1) return 0;
unordered_map even, odd;
for (int i = 0; i < n; i++) {
if (i % 2 == 0) even[nums[i]]++;
else odd[nums[i]]++;
}
vector> e(even.begin(), even.end());
vector> o(odd.begin(), odd.end());
sort(e.begin(), e.end(), [](auto &a, auto &b){ return a.second > b.second; });
sort(o.begin(), o.end(), [](auto &a, auto &b){ return a.second > b.second; });
if (e[0].first != o[0].first)
return n - (e[0].second + o[0].second);
int e2 = e.size() > 1 ? e[1].second : 0;
int o2 = o.size() > 1 ? o[1].second : 0;
return min(
n - (e[0].second + o2),
n - (o[0].second + e2)
);
}
Java Implementation
import java.util.*;
class Solution {
public int minimumOperations(int[] nums) {
int n = nums.length;
if (n <= 1) return 0;
Map even = new HashMap<>();
Map 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> e =
new ArrayList<>(even.entrySet());
List> o =
new ArrayList<>(odd.entrySet());
e.sort((a,b) -> b.getValue() - a.getValue());
o.sort((a,b) -> b.getValue() - a.getValue());
if (!e.get(0).getKey().equals(o.get(0).getKey()))
return n - (e.get(0).getValue() + o.get(0).getValue());
int e2 = e.size() > 1 ? e.get(1).getValue() : 0;
int o2 = o.size() > 1 ? o.get(1).getValue() : 0;
return Math.min(
n - (e.get(0).getValue() + o2),
n - (o.get(0).getValue() + e2)
);
}
}
JavaScript Implementation
function minimumOperations(nums) {
if (nums.length <= 1) return 0;
const even = new Map();
const odd = new Map();
nums.forEach((val, i) => {
const map = i % 2 === 0 ? even : odd;
map.set(val, (map.get(val) || 0) + 1);
});
const e = [...even.entries()].sort((a,b)=>b[1]-a[1]);
const o = [...odd.entries()].sort((a,b)=>b[1]-a[1]);
if (e[0][0] !== o[0][0])
return nums.length - (e[0][1] + o[0][1]);
const e2 = e[1]?.[1] || 0;
const o2 = o[1]?.[1] || 0;
return Math.min(
nums.length - (e[0][1] + o2),
nums.length - (o[0][1] + e2)
);
}
C# Implementation
using System;
using System.Collections.Generic;
using System.Linq;
class Solution {
public int MinimumOperations(int[] nums) {
int n = nums.Length;
if (n <= 1) return 0;
var even = new Dictionary();
var odd = new Dictionary();
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
if (!even.ContainsKey(nums[i])) even[nums[i]] = 0;
even[nums[i]]++;
} else {
if (!odd.ContainsKey(nums[i])) odd[nums[i]] = 0;
odd[nums[i]]++;
}
}
var e = even.OrderByDescending(x => x.Value).ToList();
var o = odd.OrderByDescending(x => x.Value).ToList();
if (e[0].Key != o[0].Key)
return n - (e[0].Value + o[0].Value);
int e2 = e.Count > 1 ? e[1].Value : 0;
int o2 = o.Count > 1 ? o[1].Value : 0;
return Math.Min(
n - (e[0].Value + o2),
n - (o[0].Value + e2)
);
}
}
Final Summary
- Separate even and odd positions
- Pick most frequent values greedily
- Handle conflict using second best choice
- Optimal and interview-friendly solution
Next Problem in the Series
Maximum Sum of Non-Adjacent Elements (Circular)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.png)
