Minimum operations to make array parity alternating

Array Greedy

16.3% acceptance

Mar 16, 2026

You are given an integer array nums. An array is called parity alternating if for every index i where 0 <= i < n - 1, nums[i] and nums[i + 1] have different parity. In one operation, you may choose any index i and either increase nums[i] by 1 or decrease nums[i] by 1. Return an integer array answer of length 2 where: answer[0] is the minimum number of operations required to make the array parity alternating. answer[1] is the minimum possible value of max(nums) - min(nums) taken over all arrays that are parity alternating and can be obtained by performing exactly answer[0] operations.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn make_parity_alternating(nums: Vec<i32>) -> Vec<i32> {
    let n = nums.len();
    if n == 1 {
      return vec![0, 0];
    }

    // Two patterns:
    // Pattern 0: even indices are even, odd indices are odd
    // Pattern 1: even indices are odd, odd indices are even
    let mut ops = [0i32; 2];
    for i in 0..n {
      let parity = ((nums[i] % 2) + 2) % 2;
      if parity != (i % 2) as i32 { ops[0] += 1; }
      if parity != ((i + 1) % 2) as i32 { ops[1] += 1; }
    }

    let min_ops = ops[0].min(ops[1]);
    let mut best_range = i64::MAX;

    for pat in 0..2 {
      if ops[pat] != min_ops { continue; }

      // For each element: (lo, hi) where lo <= hi
      // Fixed parity: lo = hi = v. Wrong parity: lo = v-1, hi = v+1.
      let mut elements: Vec<(i64, i64)> = Vec::with_capacity(n);
      for i in 0..n {
        let parity = ((nums[i] % 2) + 2) % 2;
        let target = if pat == 0 { (i % 2) as i32 } else { ((i + 1) % 2) as i32 };
        let v = nums[i] as i64;
        if parity == target {
          elements.push((v, v));
        } else {
          elements.push((v - 1, v + 1));
        }
      }

      // Sort elements by lo
      let mut sorted_elems = elements.clone();
      sorted_elems.sort_unstable_by_key(|&(lo, _)| lo);

      // Precompute suffix max of lo
      let mut suffix_max_lo = vec![i64::MIN; n + 1];
      for i in (0..n).rev() {
        suffix_max_lo[i] = suffix_max_lo[i + 1].max(sorted_elems[i].0);
      }

      // Process candidates in increasing order of threshold
      // As threshold C increases, elements with lo < C switch to picking hi.
      // Use a pointer to track boundary.
      // Candidates are all unique lo and hi values.
      let mut candidates: Vec<i64> = Vec::with_capacity(2 * n);
      for &(lo, hi) in &sorted_elems {
        candidates.push(lo);
        candidates.push(hi);
      }
      candidates.sort_unstable();
      candidates.dedup();

      let mut ptr = 0usize; // first element in sorted_elems with lo >= C
      let mut max_hi_in_group = i64::MIN; // max hi among elements with lo < C
      let mut min_hi_in_group = i64::MAX; // min hi among elements with lo < C (for feasibility)

      for &cand in &candidates {
        // Advance ptr: elements with lo < cand go to "pick hi" group
        while ptr < n && sorted_elems[ptr].0 < cand {
          let hi = sorted_elems[ptr].1;
          max_hi_in_group = max_hi_in_group.max(hi);
          min_hi_in_group = min_hi_in_group.min(hi);
          ptr += 1;
        }

        // Feasibility: all "pick hi" elements must have hi >= cand
        if min_hi_in_group < cand { continue; }

        // Max chosen = max(max of lo in "pick lo" group, max of hi in "pick hi" group)
        let max_lo = suffix_max_lo[ptr]; // max lo among elements with lo >= cand
        let mut max_chosen = max_hi_in_group;
        if ptr < n { max_chosen = max_chosen.max(max_lo); }

        // Min chosen: the candidate is the threshold. Min chosen >= cand.
        // Actual min chosen is min of {lo for pick-lo group (>= cand), hi for pick-hi group (>= cand)}
        // We want range = max_chosen - min_chosen.
        // min chosen from pick-lo group: the smallest lo >= cand (which is sorted_elems[ptr].0)
        // min chosen from pick-hi group: cand itself if any hi == cand, else min_hi in group
        let mut min_chosen = i64::MAX;
        if ptr < n { min_chosen = min_chosen.min(sorted_elems[ptr].0); }
        if ptr > 0 {
          // min of hi values in pick-hi group that are >= cand
          // Since min_hi_in_group >= cand (checked above), the min hi in group works
          min_chosen = min_chosen.min(min_hi_in_group);
        }

        if max_chosen >= min_chosen {
          best_range = best_range.min(max_chosen - min_chosen);
        }
      }
    }

    vec![min_ops, best_range as i32]
  }
}