3122. Minimum Number of Operations to Satisfy Conditions LeetCode Solution

In this guide, you will get 3122. Minimum Number of Operations to Satisfy Conditions LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Operations to Satisfy Conditions problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Number of Operations to Satisfy Conditions solution in C++
Minimum Number of Operations to Satisfy Conditions solution in Java
Minimum Number of Operations to Satisfy Conditions solution in Python
Additional Resources

3122. Minimum Number of Operations to Satisfy Conditions LeetCode Solution image

Problem Statement of Minimum Number of Operations to Satisfy Conditions

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

Complexity Analysis

Time Complexity: O(mn)
Space Complexity: O(10n) = O(n)

3122. Minimum Number of Operations to Satisfy Conditions LeetCode Solution in C++

class Solution {
 public:
  int minimumOperations(vector<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    vector<vector<int>> count(n, vector<int>(10));

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        ++count[j][grid[i][j]];

    vector<vector<int>> mem(n, vector<int>(10, -1));
    return minimumOperations(count, 0, 0, m, mem);
  }

 private:
  // Returns the number of minimum operations needed to make grid[:][j..n)
  // satisfy the conditions, where the (j - 1)-th column is filled with `prev`.
  int minimumOperations(const vector<vector<int>>& count, int j, int prev,
                        int m, vector<vector<int>>& mem) {
    if (j == count.size())
      return 0;
    if (mem[j][prev] != -1)
      return mem[j][prev];

    int res = INT_MAX;

    for (int num = 0; num < 10; ++num)
      if (j == 0 || num != prev)
        res = min(res, m - count[j][num] +
                           minimumOperations(count, j + 1, num, m, mem));

    return mem[j][prev] = res;
  }
};
/* code provided by PROGIEZ */

3122. Minimum Number of Operations to Satisfy Conditions LeetCode Solution in Java

class Solution {
  public int minimumOperations(int[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    int[][] count = new int[n][10];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        ++count[j][grid[i][j]];

    Integer[][] mem = new Integer[n][10];
    return minimumOperations(count, 0, 0, m, mem);
  }

  // Returns the number of minimum operations needed to make grid[:][j..n)
  // satisfy the conditions, where the (j - 1)-th column is filled with `prev`.
  private int minimumOperations(int[][] count, int j, int prev, int m, Integer[][] mem) {
    if (j == count.length)
      return 0;
    if (mem[j][prev] != null)
      return mem[j][prev];

    int res = Integer.MAX_VALUE;

    for (int num = 0; num < 10; ++num)
      if (j == 0 || num != prev)
        res = Math.min(res, m - count[j][num] + minimumOperations(count, j + 1, num, m, mem));

    return mem[j][prev] = res;
  }
}
// code provided by PROGIEZ

3122. Minimum Number of Operations to Satisfy Conditions LeetCode Solution in Python

class Solution:
  def minimumOperations(self, grid: list[list[int]]) -> int:
    m = len(grid)
    n = len(grid[0])
    count = [[0] * 10 for _ in range(n)]

    for row in grid:
      for j, num in enumerate(row):
        count[j][num] += 1

    @functools.lru_cache(None)
    def dp(i: int, prev: int) -> int:
      """
      Returns the number of minimum operations needed to make grid[:][j..n)
      satisfy the conditions, where the (j - 1)-th column is filled with `prev`.
      """
      if i == n:
        return 0

      res = math.inf

      for num in range(10):
        if i == 0 or num != prev:
          res = min(res, m - count[i][num] + dp(i + 1, num))

      return res

    return dp(0, 0)
 # code by PROGIEZ