3122. Minimum Number of Operations to Satisfy Conditions

Medium

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

Solution:

class Solution {

    /**
     * @param Integer[][] $grid
     * @return Integer
     */
    function minimumOperations($grid) {
        $m = count($grid);
        $n = count($grid[0]);
        $f = array_fill(0, $n, array_fill(0, 10, INF));

        for ($i = 0; $i < $n; ++$i) {
            $cnt = array_fill(0, 10, 0);
            for ($j = 0; $j < $m; ++$j) {
                $cnt[$grid[$j][$i]]++;
            }
            if ($i == 0) {
                for ($j = 0; $j < 10; ++$j) {
                    $f[$i][$j] = $m - $cnt[$j];
                }
            } else {
                for ($j = 0; $j < 10; ++$j) {
                    for ($k = 0; $k < 10; ++$k) {
                        if ($k != $j) {
                            $f[$i][$j] = min($f[$i][$j], $f[$i - 1][$k] + $m - $cnt[$j]);
                        }
                    }
                }
            }
        }
        return min($f[$n - 1]);
    }
}

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

LinkedIn
GitHub