Minimum Number of Operations to Satisfy Conditions
Source: leetcode
Difficulty: Medium
Tags: array, dynamic-programming, matrix

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.


 


**Example 1:**



**Input:** grid \= \[\[1,0,2],\[1,0,2]]


**Output:** 0


**Explanation:**


**![](https://assets.leetcode.com/uploads/2024/04/15/examplechanged.png)**


All the cells in the matrix already satisfy the properties.



**Example 2:**



**Input:** grid \= \[\[1,1,1],\[0,0,0]]


**Output:** 3


**Explanation:**


**![](https://assets.leetcode.com/uploads/2024/03/27/example21.png)**


The matrix becomes `[[1,0,1],[1,0,1]]` which satisfies the properties, by doing these 3 operations:


- Change `grid[1][0]` to 1\.
- Change `grid[0][1]` to 0\.
- Change `grid[1][2]` to 1\.



**Example 3:**



**Input:** grid \= \[\[1],\[2],\[3]]


**Output:** 2


**Explanation:**


![](https://assets.leetcode.com/uploads/2024/03/31/changed.png)


There is a single column. We can change the value to 1 in each cell using 2 operations.



 


**Constraints:**


- `1 <= n, m <= 1000`
- `0 <= grid[i][j] <= 9`




C++ solution:
//O(m*n + 10*n) dp
#define max_val 9
static auto _ = [](){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    int m, n;
    vector<vector<int>> col2val2cnt;

    const int notyet = (-1);
    vector<vector<int>> memo;

    int enum_col_val(int col, int val){
        if(col == n-1) return m - col2val2cnt[col][val];

        if(memo[col][val] != notyet) return memo[col][val];

        int ret = INT_MAX;
        //enum next col's val
        for(int next_val=0;next_val<=max_val;next_val++)if(next_val != val){
            ret = min(
                ret,
                enum_col_val(col+1, next_val)
            );
        }

        return memo[col][val] = (m - col2val2cnt[col][val] ) + ret;
    }

    int minimumOperations(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid.back().size();
        col2val2cnt.resize(n, vector<int>(max_val + 1, 0));

        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                col2val2cnt[j][ grid[i][j] ]++;
        
        memo.resize(n, vector<int>(max_val + 1, notyet));
        int ans = INT_MAX;
        for(int val0=0;val0<=max_val;val0++){
            ans = min(
                ans,
                enum_col_val(0, val0)
            );
        }
        return ans;
    }
};

Go solution:
func calc(num, col int, grid [][]int) int {
	ans := 0
	for I := range len(grid) {
		if grid[I][col] != num {
			ans++
		}
	}
	return ans
}

func solve(i, prev, n int, grid [][]int, dp *[][]int) int {
	if i >= n {
		return 0
	}
	if (*dp)[i][prev+1] != -1 {
		return (*dp)[i][prev+1]
	}
	ans := math.MaxInt32
	for I := range 10 {
		if I != prev {
			ans = min(ans, calc(I, i, grid)+solve(i+1, I, n, grid, dp))
		}
	}
	(*dp)[i][prev+1] = ans
	return ans
}

func Init2d[T any](n, m int, val T) [][]T {
	arr := make([][]T, n)
	for i := range n {
		arr[i] = make([]T, m)
	}
	for i := range n {
		for j := range m {
			arr[i][j] = val
		}
	}
	return arr
}

func minimumOperations(grid [][]int) int {
	dp := Init2d(1005, 15, -1)
	return solve(0, -1, len(grid[0]), grid, &dp)
}

Java solution:
class Solution {
    private PriorityQueue<List<Integer>> dfs(int[][] grid, int j) {
        if(j == grid[0].length-1) {
            PriorityQueue<List<Integer>> queue = new PriorityQueue<>((a,b) -> Integer.compare(a.get(0), b.get(0)));
            for(int value = 0 ; value <= 9 ; value++) {
                int count = 0;
                for(int i = 0 ; i < grid.length ; i++) {
                    if(grid[i][j] != value) count++;
                }
                queue.add(new ArrayList<>(Arrays.asList(count, value)));
            }
            return queue;
        }
        PriorityQueue<List<Integer>> next = dfs(grid, j+1);
        PriorityQueue<List<Integer>> queue = new PriorityQueue<>((a,b) -> Integer.compare(a.get(0), b.get(0)));
        for(int value = 0 ; value <= 9 ; value++) {
            int count = 0;
            for(int i = 0 ; i < grid.length ; i++) {
                if(grid[i][j] != value) count++;
            }
            List<Integer> arr = next.poll();
            if(arr.get(1) == value) {
                count += next.peek().get(0);
            } else {
                count += arr.get(0);
            }
            next.add(arr);
            queue.add(new ArrayList<>(Arrays.asList(count, value)));
        }
        return queue;
    }
    public int minimumOperations(int[][] grid) {
        PriorityQueue<List<Integer>> queue = dfs(grid, 0);
        return queue.peek().get(0);
    }
}

JavaScript solution:
var minimumOperations = function (grid) {
  let m = grid.length
  let n = grid[0].length

  let cnts = new Array(n).fill().map((_, j) => {
    let counter = {}
    for (let i = 0; i < m; i++) {
      counter[grid[i][j]] = (counter[grid[i][j]] || 0) + 1
    }
    return counter
  })

  let dp = new Array(n).fill().map(() => Array(10).fill(Infinity))

  for (let j = 0; j < 10; j++) {
    dp[0][j] = m - (cnts[0][j] || 0)
  }

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < 10; j++) {
      for (let k = 0; k < 10; k++) {
        if (j !== k) {
          const count = m - (cnts[i][j] || 0)
          dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + count)
        }
      }
    }
  }
  return Math.min(...dp[n - 1])
}

Python solution:
class Solution:
    def minimumOperations(self, grid: List[List[int]]) -> int:
        transpose = list(zip(*grid))
        num_rows = len(grid)
        num_cols = len(grid[0])
        num_values = 10
        best_key = 0
        best_val = 0
        next_val = 0
        for j in range(num_cols):
            options = []
            counts = collections.Counter(transpose[j])
            total = sum(counts.values())
            for k in range(num_values):
                changes = total - counts[k]
                best_compatible = best_val if k != best_key else next_val
                options.append(changes + best_compatible)
            (best_val, best_key), (next_val, _), *_ = sorted((v, j) for j, v in enumerate(options))
        return best_val

Ruby solution:
def minimum_operations(grid)
  return 0 if grid.empty? || grid[0].empty?

  columns = grid.transpose
  return 0 if columns.empty?

  costs = columns.map do |col|
    freq = Hash.new(0)
    col.each { |val| freq[val] += 1 }
    m = col.size
    (0..9).map { |v| m - freq[v] }
  end

  prev_dp = costs[0].dup

  costs[1..-1].each do |current_cost|
    sorted_prev = prev_dp.each_with_index.sort_by { |val, _| val }
    min1_val, min1_idx = sorted_prev[0]
    min2_val, min2_idx = sorted_prev[1]

    current_dp = Array.new(10)
    (0..9).each do |v|
      current_dp[v] = current_cost[v] + (v != min1_idx ? min1_val : min2_val)
    end

    prev_dp = current_dp
  end

  prev_dp.min
end