Minimum number of operations to satisfy conditions

Array Dynamic Programming Matrix

41.7% acceptance

Feb 23, 2026

284

You are given a 2D matrix grid of size m x n. In one operation, you can change the value of any cell to any non-negative number. You need to perform some operations such that each cell grid[i][j] is: Equal to the cell below it, i.e. grid[i][j] == grid[i + 1][j] (if it exists). Different from the cell to its right, i.e. grid[i][j] != grid[i][j + 1] (if it exists). Return the minimum number of operations needed.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_operations(grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();

    // For column j, cost[j][v] = number of cells in column j that are NOT v
    // (i.e., number of changes needed to make all cells = v)
    // We pick a value 0..=9 for each column, adjacent columns must differ.
    // min total cost = DP over columns.

    // count[j][v] = number of cells in column j equal to v
    let mut count = vec![[0i32; 10]; n];
    for row in &grid {
      for (j, &val) in row.iter().enumerate() {
        count[j][val as usize] += 1;
      }
    }

    // dp[v] = min cost when column j has value v
    let m_i32 = m as i32;
    let cost = |j: usize, v: usize| m_i32 - count[j][v];

    // Initialize for column 0
    let mut dp = [0i32; 10];
    for v in 0..10 {
      dp[v] = cost(0, v);
    }

    // Process remaining columns
    for j in 1..n {
      // Find min and second min of dp
      let mut min1 = i32::MAX;
      let mut min1_idx = 0;
      let mut min2 = i32::MAX;
      for v in 0..10 {
        if dp[v] < min1 {
          min2 = min1;
          min1 = dp[v];
          min1_idx = v;
        } else if dp[v] < min2 {
          min2 = dp[v];
        }
      }

      let mut new_dp = [0i32; 10];
      for v in 0..10 {
        let prev_min = if v != min1_idx { min1 } else { min2 };
        new_dp[v] = cost(j, v) + prev_min;
      }
      dp = new_dp;
    }

    *dp.iter().min().unwrap()
  }
}