3122. Minimum Number of Operations to Satisfy Conditions
Description
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:
All the cells in the matrix already satisfy the properties.
Example 2:
Input: grid = [[1,1,1],[0,0,0]]
Output: 3
Explanation:
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:
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
Solutions
Solution 1: Dynamic Programming
We notice that the values in the cells of the matrix only have 10 possibilities. The problem requires us to find the minimum number of operations for each column to have the same number, and the numbers in adjacent columns are different. Therefore, we only need to consider the case of modifying the number to 0 to 9.
We define the state $f[i][j]$ to represent the minimum number of operations for the numbers in the first $[0,..i]$ columns, and the number in the $i$-th column is $j$. Then we can get the state transition equation:
$$ f[i][j] = \min_{k \neq j} (f[i-1][k] + m - \textit{cnt}[j]) $$
Where $\textit{cnt}[j]$ represents the number of cells in the $i$-th column that are $j$.
Finally, we only need to find the minimum value of $f[n-1][j]$.
The time complexity is $O(n \times (m + C^2))$, and the space complexity is $O(n \times C)$. Where $m$ and $n$ represent the number of rows and columns in the matrix respectively; and $C$ represents the number of types of numbers, here $C = 10$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
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 |
|
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 |
|