Minimum operations to make the array alternating

Array Hash Table Greedy Counting

35.4% acceptance

Feb 25, 2026

614

344

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] and nums[i-1] != nums[i]. In one operation, choose an index i and change nums[i] into any positive integer. Return the minimum number of operations required to make the array alternating.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_operations(nums: Vec<i32>) -> i32 {
    use std::collections::HashMap;
    let n = nums.len();
    let mut even_cnt: HashMap<i32, i32> = HashMap::new();
    let mut odd_cnt: HashMap<i32, i32> = HashMap::new();
    for (i, &v) in nums.iter().enumerate() {
      if i % 2 == 0 {
        *even_cnt.entry(v).or_insert(0) += 1;
      } else {
        *odd_cnt.entry(v).or_insert(0) += 1;
      }
    }

    // Get top 2 by count: returns [(val, cnt); 1..=2]
    let top2 = |map: &HashMap<i32, i32>| -> [(i32, i32); 2] {
      let mut v: Vec<(i32, i32)> = map.iter().map(|(&k, &c)| (c, k)).collect();
      v.sort_unstable_by(|a, b| b.cmp(a));
      [
        if !v.is_empty() { (v[0].1, v[0].0) } else { (0, 0) },
        if v.len() > 1 { (v[1].1, v[1].0) } else { (0, 0) },
      ]
    };

    let ev = top2(&even_cnt); // ev[0]=(val, cnt), ev[1]=(val2, cnt2)
    let od = top2(&odd_cnt);

    if ev[0].0 != od[0].0 {
      n as i32 - ev[0].1 - od[0].1
    } else {
      // Must use second best for one side
      (n as i32 - ev[0].1 - od[1].1).min(n as i32 - ev[1].1 - od[0].1)
    }
  }
}