DEV Community

Cover image for 3122. Minimum Number of Operations to Satisfy Conditions
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on • Edited on

3122. Minimum Number of Operations to Satisfy Conditions

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:

    examplechanged

All the cells in the matrix already satisfy the properties.

Example 2:

  • Input: grid = [[1,1,1],[0,0,0]]
  • Output: 3
  • Explanation:

example21

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:

changed

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]);
    }
}
Enter fullscreen mode Exit fullscreen mode

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!

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (0)

Billboard image

Create up to 10 Postgres Databases on Neon's free plan.

If you're starting a new project, Neon has got your databases covered. No credit cards. No trials. No getting in your way.

Try Neon for Free →