Minimum Operations to Make the Array Alternating

Medium
1790.

Minimum Operations to Make the Array Alternating

Minimum Operations to Make the Array Alternating is a medium coding problem on arrays, hash table and greedy, asked in Amazon interviews.

You are given an array nums of n positive integers.

The array is alternating when:

  • nums[i - 2] == nums[i] for every 2 <= i < n, and
  • nums[i - 1] != nums[i] for every 1 <= 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^5
  • 1 <= nums[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumOperations = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 every 2 <= i < n, and
  • nums[i - 1] != nums[i] for every 1 <= 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^5
  • 1 <= nums[i] <= 10^5

Hints for Minimum Operations to Make the Array Alternating

  1. Hint 1

    An alternating array is fully described by two values: a on the even indices and b on the odd indices, with a != b.

  2. Hint 2

    For a chosen (a, b), the cost is the number of even positions not equal to a plus odd positions not equal to b — so pick the most frequent value on each side.

  3. 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

  1. Count values at even indices and at odd indices separately.
  2. Find the top two (value, count) pairs on each side, using count 0 for a missing second choice.
  3. If the two top values differ, keep both: answer n - e1 - o1.
  4. 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