Minimum Operations to Make the Array Alternating — Solution
Minimum Operations to Make the Array Alternating solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Operations to Make the Array Alternating is a medium coding problem on arrays, hash table and greedy, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Greedy, Counting
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of n positive integers.
The array is alternating when:
nums[i - 2] == nums[i]for every2 <= i < n, andnums[i - 1] != nums[i]for every1 <= i < n.
In one operation you may change any element to any positive integer. Return the minimum number of operations needed to make the array alternating.
Example 1
Input: nums = [5,9,5,9,5,2]
Output: 1
Explanation: Change the last element to 9, giving `[5,9,5,9,5,9]`.
Example 2
Input: nums = [7,7,7,7]
Output: 2
Explanation: The even positions can stay 7, but the odd positions must differ from them: change both to, say, 1.
Example 3
Input: nums = [4]
Output: 0
Explanation: A single element is already alternating.
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^5
Hints for Minimum Operations to Make the Array Alternating
Hint 1
An alternating array is fully described by two values:
aon the even indices andbon the odd indices, witha != b.Hint 2
For a chosen
(a, b), the cost is the number of even positions not equal toaplus odd positions not equal tob— so pick the most frequent value on each side.Hint 3
If both sides' most frequent values coincide, one side has to settle for its second most frequent value (or a value that is not there at all). Keep the top two of each side.
How to solve Minimum Operations to Make the Array Alternating
Keeping as many elements as possible means choosing the most common value among even indices and among odd indices. The only conflict is when those two values are equal; then the better of the two "second choices" decides.
Approach
- Count values at even indices and at odd indices separately.
- Find the top two (value, count) pairs on each side, using count 0 for a missing second choice.
- If the two top values differ, keep both: answer
n - e1 - o1. - Otherwise answer
n - max(e1 + o2, e2 + o1).
Why it works
The kept elements are exactly the even positions equal to a plus the odd positions equal to b, and those two counts are independent except for the constraint a != b. Without a clash, each side's maximum is optimal. With a clash, at least one side must give up its top value, and the best it can then keep is its second-best count (a value absent from that side keeps 0, which the 0 default covers).
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Only the top value per side is not enough — the clash case needs the runner-up.
- With a single element there are no odd positions; the answer is 0.
- The two sides may be forced to different values even if neither side has a second value: changing every odd element to a fresh value costs all of them.
Reference solution
Python
from typing import List
from collections import Counter
def minimumOperations(nums: List[int]) -> int:
n = len(nums)
def top2(vals):
best = Counter(vals).most_common(2)
while len(best) < 2:
best.append((0, 0))
return best
(ev, e1), (_, e2) = top2(nums[0::2])
(ov, o1), (_, o2) = top2(nums[1::2])
if ev != ov:
return n - e1 - o1
return n - max(e1 + o2, e2 + o1)Java
public static int minimumOperations(int[] nums) {
int n = nums.length;
int[] e = top2(nums, 0), o = top2(nums, 1);
if (e[0] != o[0]) return n - e[1] - o[1];
return n - Math.max(e[1] + o[2], e[2] + o[1]);
}
private static int[] top2(int[] nums, int start) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int i = start; i < nums.length; i += 2) cnt.merge(nums[i], 1, Integer::sum);
int v1 = 0, c1 = 0, c2 = 0;
for (Map.Entry<Integer, Integer> en : cnt.entrySet()) {
int c = en.getValue();
if (c > c1) { c2 = c1; c1 = c; v1 = en.getKey(); }
else if (c > c2) c2 = c;
}
return new int[] { v1, c1, c2 };
}C++
static array<int, 3> top2(const vector<int>& nums, int start) {
unordered_map<int, int> cnt;
for (size_t i = start; i < nums.size(); i += 2) cnt[nums[i]]++;
int v1 = 0, c1 = 0, c2 = 0;
for (auto& e : cnt) {
if (e.second > c1) { c2 = c1; c1 = e.second; v1 = e.first; }
else if (e.second > c2) c2 = e.second;
}
return {v1, c1, c2};
}
int minimumOperations(vector<int>& nums) {
int n = nums.size();
auto e = top2(nums, 0), o = top2(nums, 1);
if (e[0] != o[0]) return n - e[1] - o[1];
return n - max(e[1] + o[2], e[2] + o[1]);
}JavaScript
var minimumOperations = function(nums) {
var n = nums.length;
var top2 = function(start) {
var cnt = new Map();
for (var i = start; i < n; i += 2) cnt.set(nums[i], (cnt.get(nums[i]) || 0) + 1);
var v1 = 0, c1 = 0, c2 = 0;
cnt.forEach(function(c, v) {
if (c > c1) { c2 = c1; c1 = c; v1 = v; }
else if (c > c2) c2 = c;
});
return [v1, c1, c2];
};
var e = top2(0), o = top2(1);
if (e[0] !== o[0]) return n - e[1] - o[1];
return n - Math.max(e[1] + o[2], e[2] + o[1]);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets