Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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

Solution

Method 1 – DP with Coloring (2-Coloring Columns)

Intuition

Each column must be uniform (all cells equal), and adjacent columns must differ. This is a coloring problem: assign each column one value, ensuring adjacent columns differ, and minimize changes.

Approach

  1. For each column, count how many cells are each value (0-9).
  2. For each column, try all possible values (0-9) and use DP to track the minimum changes, ensuring adjacent columns differ.
  3. For column j and value v, dp[j][v] = min over all u != v of dp[j-1][u] + (cells in column j not equal to v).
  4. The answer is min(dp[last column][v]) over all v.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int minimumOperations(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> cnt(n, vector<int>(10, 0));
        for (int j = 0; j < n; ++j)
            for (int i = 0; i < m; ++i)
                cnt[j][grid[i][j]]++;
        vector<vector<int>> dp(n, vector<int>(10, 1e9));
        for (int v = 0; v < 10; ++v)
            dp[0][v] = m - cnt[0][v];
        for (int j = 1; j < n; ++j) {
            for (int v = 0; v < 10; ++v) {
                for (int u = 0; u < 10; ++u) {
                    if (u == v) continue;
                    dp[j][v] = min(dp[j][v], dp[j-1][u] + m - cnt[j][v]);
                }
            }
        }
        return *min_element(dp[n-1].begin(), dp[n-1].end());
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

func minimumOperations(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    cnt := make([][]int, n)
    for j := range cnt {
        cnt[j] = make([]int, 10)
        for i := 0; i < m; i++ {
            cnt[j][grid[i][j]]++
        }
    }
    dp := make([][]int, n)
    for j := range dp {
        dp[j] = make([]int, 10)
        for v := 0; v < 10; v++ {
            dp[j][v] = 1 << 30
        }
    }
    for v := 0; v < 10; v++ {
        dp[0][v] = m - cnt[0][v]
    }
    for j := 1; j < n; j++ {
        for v := 0; v < 10; v++ {
            for u := 0; u < 10; u++ {
                if u == v {
                    continue
                }
                if dp[j][v] > dp[j-1][u]+m-cnt[j][v] {
                    dp[j][v] = dp[j-1][u]+m-cnt[j][v]
                }
            }
        }
    }
    res := 1 << 30
    for v := 0; v < 10; v++ {
        if dp[n-1][v] < res {
            res = dp[n-1][v]
        }
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import java.util.*;
class Solution {
    public int minimumOperations(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] cnt = new int[n][10];
        for (int j = 0; j < n; ++j)
            for (int i = 0; i < m; ++i)
                cnt[j][grid[i][j]]++;
        int[][] dp = new int[n][10];
        for (int[] d : dp) Arrays.fill(d, Integer.MAX_VALUE);
        for (int v = 0; v < 10; ++v)
            dp[0][v] = m - cnt[0][v];
        for (int j = 1; j < n; ++j) {
            for (int v = 0; v < 10; ++v) {
                for (int u = 0; u < 10; ++u) {
                    if (u == v) continue;
                    dp[j][v] = Math.min(dp[j][v], dp[j-1][u] + m - cnt[j][v]);
                }
            }
        }
        int res = Integer.MAX_VALUE;
        for (int v = 0; v < 10; ++v)
            res = Math.min(res, dp[n-1][v]);
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun minimumOperations(grid: Array<IntArray>): Int {
        val m = grid.size; val n = grid[0].size
        val cnt = Array(n) { IntArray(10) }
        for (j in 0 until n) for (i in 0 until m) cnt[j][grid[i][j]]++
        val dp = Array(n) { IntArray(10) { Int.MAX_VALUE } }
        for (v in 0..9) dp[0][v] = m - cnt[0][v]
        for (j in 1 until n) {
            for (v in 0..9) {
                for (u in 0..9) {
                    if (u == v) continue
                    dp[j][v] = minOf(dp[j][v], dp[j-1][u] + m - cnt[j][v])
                }
            }
        }
        return dp[n-1].minOrNull()!!
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def minimumOperations(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        cnt = [[0]*10 for _ in range(n)]
        for j in range(n):
            for i in range(m):
                cnt[j][grid[i][j]] += 1
        dp = [[float('inf')]*10 for _ in range(n)]
        for v in range(10):
            dp[0][v] = m - cnt[0][v]
        for j in range(1, n):
            for v in range(10):
                for u in range(10):
                    if u == v: continue
                    dp[j][v] = min(dp[j][v], dp[j-1][u] + m - cnt[j][v])
        return min(dp[n-1])
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

impl Solution {
    pub fn minimum_operations(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut cnt = vec![vec![0; 10]; n];
        for j in 0..n {
            for i in 0..m {
                cnt[j][grid[i][j] as usize] += 1;
            }
        }
        let mut dp = vec![vec![i32::MAX; 10]; n];
        for v in 0..10 {
            dp[0][v] = m as i32 - cnt[0][v];
        }
        for j in 1..n {
            for v in 0..10 {
                for u in 0..10 {
                    if u == v { continue; }
                    dp[j][v] = dp[j][v].min(dp[j-1][u] + m as i32 - cnt[j][v]);
                }
            }
        }
        *dp[n-1].iter().min().unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    minimumOperations(grid: number[][]): number {
        const m = grid.length, n = grid[0].length;
        const cnt = Array.from({length: n}, () => Array(10).fill(0));
        for (let j = 0; j < n; ++j)
            for (let i = 0; i < m; ++i)
                cnt[j][grid[i][j]]++;
        const dp = Array.from({length: n}, () => Array(10).fill(Infinity));
        for (let v = 0; v < 10; ++v)
            dp[0][v] = m - cnt[0][v];
        for (let j = 1; j < n; ++j) {
            for (let v = 0; v < 10; ++v) {
                for (let u = 0; u < 10; ++u) {
                    if (u === v) continue;
                    dp[j][v] = Math.min(dp[j][v], dp[j-1][u] + m - cnt[j][v]);
                }
            }
        }
        return Math.min(...dp[n-1]);
    }
}

Complexity

  • ⏰ Time complexity: O(n * m * 10^2) — n = columns, m = rows, 10 values per column.
  • 🧺 Space complexity: O(n * 10) — DP table.