# Minimum Number of Operations to Satisfy Conditions
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-operations-to-satisfy-conditions)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-operations-to-satisfy-conditions
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
**Companies:** [Turing](https://scaleengineer.com/companies/turing)
---
## Problem
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:**

**![](https://assets.glich.co/dsa/minimum-number-of-operations-to-satisfy-conditions/image0.png)**

All the cells in the matrix already satisfy the properties.

**Example 2:**

**Input:** grid = \[\[1,1,1\],\[0,0,0\]\]

**Output:** 3

**Explanation:**

**![](https://assets.glich.co/dsa/minimum-number-of-operations-to-satisfy-conditions/image1.png)**

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:**

![](https://assets.glich.co/dsa/minimum-number-of-operations-to-satisfy-conditions/image2.png)

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`

# Approaches
## Brute Force Recursion
The problem can be framed as finding an optimal sequence of values `v_0, v_1, ..., v_{n-1}` for each column, where `v_j` is the value assigned to all cells in column `j`. The constraints are that `v_j` must be different from `v_{j+1}`. The cost for assigning `v_j` to column `j` is `m - (number of cells in column j already equal to v_j)`.

A brute-force approach explores every possible valid sequence of values for the columns. We can define a recursive function, say `findMinOps(colIndex, prevVal)`, which calculates the minimum operations needed for columns from `colIndex` to `n-1`, given that the previous column (`colIndex - 1`) was assigned the value `prevVal`.

In this function, we iterate through all possible values (0-9) for the current column `colIndex`. If a value `currVal` is different from `prevVal`, we calculate the cost for changing column `colIndex` to `currVal` and recursively call the function for the next column: `findMinOps(colIndex + 1, currVal)`. The total cost for this choice is the sum of the current column's cost and the result of the recursive call. We take the minimum over all valid choices for `currVal`.
**Time:** O(m*n + 10 * 9^(n-1)). The pre-computation is `O(m*n)`. The recursion tree has a depth of `n`. The root has 10 children, and each subsequent node has 9 children. This leads to `10 * 9^(n-1)` paths. This is exponential and too slow for the given constraints. · **Space:** O(n) for the recursion stack depth, plus O(n) for the `counts` array. Total O(n).
**Pros:** Simple to understand and implement the logic directly from the problem definition.
**Cons:** Highly inefficient due to re-computing results for the same subproblems (e.g., `solve(col, val)` is called many times with the same arguments).; Leads to Time Limit Exceeded for the given constraints.
### Explanation
```java
class Solution {
    private int m, n;
    private int[][] counts;

    public int minimumOperations(int[][] grid) {
        this.m = grid.length;
        this.n = grid[0].length;
        this.counts = new int[n][10];

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

        return solve(0, -1);
    }

    private int solve(int col, int prevVal) {
        if (col == n) {
            return 0;
        }

        int minOps = Integer.MAX_VALUE;
        for (int val = 0; val <= 9; val++) {
            if (val != prevVal) {
                int currentCost = m - counts[col][val];
                int futureCost = solve(col + 1, val);
                if (futureCost != Integer.MAX_VALUE) {
                    minOps = Math.min(minOps, currentCost + futureCost);
                }
            }
        }
        return minOps;
    }
}
```
### Algorithm
*   Pre-calculate the frequency of each number (0-9) for each column. Store this in a `counts[n][10]` array. This takes `O(m*n)`.
*   Define a recursive function `solve(col, prev_val)`:
    *   Base Case: If `col == n` (all columns processed), return 0.
    *   Initialize `min_ops = infinity`.
    *   Iterate `val` from 0 to 9:
        *   If `val != prev_val`:
            *   Calculate cost for the current column `col` to be `val`: `cost = m - counts[col][val]`.
            *   Recursively find the cost for the rest of the columns: `future_cost = solve(col + 1, val)`.
            *   Update `min_ops = min(min_ops, cost + future_cost)`.
    *   Return `min_ops`.
*   The initial call is `solve(0, -1)` (using -1 to signify no previous column).

## Dynamic Programming
The brute-force recursive approach suffers from re-calculating the same subproblems repeatedly. We can observe that the optimal cost for the first `j` columns, with column `j` having value `x`, only depends on the optimal costs for the first `j-1` columns. This is a classic dynamic programming problem.

We can build a `dp` table of size `n x 10`, where `dp[j][x]` represents the minimum number of operations to satisfy the conditions for columns 0 through `j`, with column `j` being assigned the value `x`. The base case is column 0, where `dp[0][x]` is simply the cost to make the entire column `x`. For subsequent columns `j`, `dp[j][x]` is calculated by adding the cost for column `j` to the minimum possible cost from column `j-1`, ensuring the value chosen for column `j-1` was not `x`.
**Time:** O(m * n). The pre-computation of `counts` takes `O(m * n)`. The DP calculation is `O(n * 10) = O(n)`. The total time is dominated by the pre-computation. · **Space:** O(n). We use O(n * 10) for the `counts` array and O(n * 10) for the `dp` table.
**Pros:** Much more efficient than brute force.; Guaranteed to find the optimal solution in polynomial time.
**Cons:** Uses extra space proportional to the number of columns `n`.
### Explanation
```java
class Solution {
    public int minimumOperations(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] counts = new int[n][10];

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

        int[][] dp = new int[n][10];

        // Base case: column 0
        for (int val = 0; val <= 9; val++) {
            dp[0][val] = m - counts[0][val];
        }

        // Fill DP table for columns 1 to n-1
        for (int j = 1; j < n; j++) {
            // Find two smallest costs from previous column
            int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
            int val1 = -1;
            for (int prevVal = 0; prevVal <= 9; prevVal++) {
                if (dp[j - 1][prevVal] < min1) {
                    min2 = min1;
                    min1 = dp[j - 1][prevVal];
                    val1 = prevVal;
                } else if (dp[j - 1][prevVal] < min2) {
                    min2 = dp[j - 1][prevVal];
                }
            }

            for (int val = 0; val <= 9; val++) {
                int cost = m - counts[j][val];
                if (val != val1) {
                    dp[j][val] = cost + min1;
                } else {
                    dp[j][val] = cost + min2;
                }
            }
        }

        // Find the minimum operations for the entire grid
        int minOps = Integer.MAX_VALUE;
        for (int val = 0; val <= 9; val++) {
            minOps = Math.min(minOps, dp[n - 1][val]);
        }

        return minOps;
    }
}
```
### Algorithm
*   Pre-calculate the frequency of each number (0-9) for each column in a `counts[n][10]` array.
*   Create a DP table `dp[n][10]`. `dp[j][x]` will store the minimum cost for the first `j+1` columns (0 to `j`), with column `j` having value `x`.
*   **Base Case (j=0):** For each value `x` from 0 to 9, `dp[0][x] = m - counts[0][x]`.
*   **Transitions (j=1 to n-1):** For each column `j`:
    *   To optimize, first find the two smallest costs from the previous column's DP states (`dp[j-1]`), let's call them `min1` and `min2`, and the value `val1` that produced `min1`.
    *   For each possible value `x` for column `j` (0-9):
        *   `cost_j_x = m - counts[j][x]`.
        *   If `x != val1`, `dp[j][x] = cost_j_x + min1`.
        *   If `x == val1`, `dp[j][x] = cost_j_x + min2`.
*   **Result:** The minimum value in the last row of the DP table: `min(dp[n-1][x])` for `x` from 0 to 9.

## Space-Optimized Dynamic Programming
The dynamic programming solution is efficient in time, but its space complexity can be improved. When calculating the DP values for column `j`, we only need the results from the immediate previous column, `j-1`. We don't need the results from columns `j-2`, `j-3`, etc.

This observation allows us to optimize the space complexity. Instead of storing the entire `dp[n][10]` table, we only need to maintain two arrays of size 10: one for the DP values of the previous column (`prev_dp`) and one for the current column (`curr_dp`).

Furthermore, we can also optimize the space used for storing the frequency counts. Instead of pre-calculating and storing counts for all columns at once, we can calculate the counts for one column at a time as we iterate through them. This reduces the space for counts from `O(n)` to `O(1)`.
**Time:** O(m * n). We iterate through each column `j` from 0 to `n-1`. For each column, we iterate through its `m` rows to calculate frequencies (`O(m)`). Then we perform constant time work (`O(10)`) for the DP state updates. The total time is `O(n * (m + 10)) = O(m * n)`. · **Space:** O(1). We use a few arrays of size 10 (`prev_dp`, `curr_dp`, `counts`), which is constant space. We are not storing information that scales with `m` or `n`.
**Pros:** Most efficient approach in both time and space.; Solves the problem with optimal time complexity while using only constant extra space.
**Cons:** The logic is slightly more complex to follow than the standard DP approach due to the space optimization.
### Explanation
```java
import java.util.Arrays;

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

        int[] prevDp = new int[10];

        // Process column 0
        int[] counts = new int[10];
        for (int i = 0; i < m; i++) {
            counts[grid[i][0]]++;
        }
        for (int val = 0; val <= 9; val++) {
            prevDp[val] = m - counts[val];
        }

        // Process columns 1 to n-1
        for (int j = 1; j < n; j++) {
            int[] currDp = new int[10];
            
            // Find two smallest costs from previous column's DP results
            int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
            int val1 = -1;
            for (int prevVal = 0; prevVal <= 9; prevVal++) {
                if (prevDp[prevVal] < min1) {
                    min2 = min1;
                    min1 = prevDp[prevVal];
                    val1 = prevVal;
                } else if (prevDp[prevVal] < min2) {
                    min2 = prevDp[prevVal];
                }
            }

            // Calculate counts for the current column
            Arrays.fill(counts, 0);
            for (int i = 0; i < m; i++) {
                counts[grid[i][j]]++;
            }

            // Calculate current column's DP results
            for (int val = 0; val <= 9; val++) {
                int cost = m - counts[val];
                if (val != val1) {
                    currDp[val] = cost + min1;
                } else {
                    currDp[val] = cost + min2;
                }
            }
            prevDp = currDp;
        }

        // Find the minimum operations for the entire grid
        int minOps = Integer.MAX_VALUE;
        for (int val = 0; val <= 9; val++) {
            minOps = Math.min(minOps, prevDp[val]);
        }

        return minOps;
    }
}
```
### Algorithm
*   Initialize a `prev_dp` array of size 10. This will store the minimum operations for the grid up to the previous column.
*   **Column 0:**
    *   Calculate the frequencies of numbers 0-9 for column 0.
    *   For each value `x` from 0 to 9, initialize `prev_dp[x] = m - counts_for_col_0[x]`.
*   **Columns 1 to n-1:**
    *   Initialize a `curr_dp` array of size 10.
    *   In a loop for `j` from 1 to `n-1`:
        *   Calculate the frequencies of numbers 0-9 for the current column `j`.
        *   Find the two smallest values (`min1`, `min2`) and the value corresponding to `min1` (`val1`) in the `prev_dp` array.
        *   For each value `x` from 0 to 9:
            *   Calculate the cost to change column `j` to `x`: `cost = m - counts_for_col_j[x]`.
            *   If `x != val1`, `curr_dp[x] = cost + min1`.
            *   Otherwise (`x == val1`), `curr_dp[x] = cost + min2`.
        *   After computing `curr_dp`, update `prev_dp = curr_dp` for the next iteration.
*   **Result:** After the loop finishes, the `prev_dp` array holds the DP values for the last column. The minimum value in this array is the final answer.

# Solutions
### Java

```java
class Solution {
public
  int minimumOperations(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] f = new int[n][10];
    final int inf = 1 << 29;
    for (var g : f) {
      Arrays.fill(g, inf);
    }
    for (int i = 0; i < n; ++i) {
      int[] cnt = new int[10];
      for (int j = 0; j < m; ++j) {
        ++cnt[grid[j][i]];
      }
      if (i == 0) {
        for (int j = 0; j < 10; ++j) {
          f[i][j] = m - cnt[j];
        }
      } else {
        for (int j = 0; j < 10; ++j) {
          for (int k = 0; k < 10; ++k) {
            if (k != j) {
              f[i][j] = Math.min(f[i][j], f[i - 1][k] + m - cnt[j]);
            }
          }
        }
      }
    }
    int ans = inf;
    for (int j = 0; j < 10; ++j) {
      ans = Math.min(ans, f[n - 1][j]);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumOperations(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    int f[n][10];
    memset(f, 0x3f, sizeof(f));
    for (int i = 0; i < n; ++i) {
      int cnt[10]{};
      for (int j = 0; j < m; ++j) {
        ++cnt[grid[j][i]];
      }
      if (i == 0) {
        for (int j = 0; j < 10; ++j) {
          f[i][j] = m - cnt[j];
        }
      } else {
        for (int j = 0; j < 10; ++j) {
          for (int k = 0; k < 10; ++k) {
            if (k != j) {
              f[i][j] = min(f[i][j], f[i - 1][k] + m - cnt[j]);
            }
          }
        }
      }
    }
    return *min_element(f[n - 1], f[n - 1] + 10);
  }
};

```

### Python

```python
class Solution:
    def minimumOperations(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) f = [[inf] * 10 for _ in range(n)] for i in range(n): cnt = [0] * 10 for j in range(m): cnt[grid[j][i]] += 1 if i == 0: for j in range(10): f[i][j] = m - cnt[j] else: for j in range(10): for k in range(10): if k != j: f[i][j] = min(f[i][j], f[i - 1][k] + m - cnt[j]) return min(f[- 1])

```