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!

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay