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:
grid[i][j] == grid[i + 1][j] (if it exists).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:
grid[1][0] to 1.grid[0][1] to 0.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 <= 10000 <= grid[i][j] <= 9Problem Overview: You are given an m x n grid of digits. The goal is to make every column contain the same value in all rows, while ensuring adjacent columns use different values. Each cell change counts as one operation. The task is to minimize the total operations.
Approach 1: Greedy Matrix Adjustment (O(m * n * 10) time, O(1) space)
This approach treats each column independently at first. For every column, count the frequency of digits 0-9. The minimum cost to convert the column to digit d is m - freq[d]. A greedy strategy picks the digit with the smallest cost for the column. If two adjacent columns end up with the same digit, adjust the later column to its second-best option.
The idea relies on column frequency counting and local optimization. While simple, greedy decisions may force suboptimal changes later because adjacent column constraints create dependencies. It works as a heuristic and helps build intuition about column conversion costs.
Approach 2: Row and Column Pattern Matching with Dynamic Programming (O(m * n * 10 + n * 10 * 10) time, O(10) space)
The optimal strategy models the problem column by column using dynamic programming. First compute the cost of converting each column j to digit d. This uses a frequency count from the matrix: cost[j][d] = m - count_of_d_in_column_j.
Define dp[j][d] as the minimum operations needed to fix columns 0..j where column j ends with digit d. Transition by checking all digits from the previous column except d: dp[j][d] = cost[j][d] + min(dp[j-1][prev]) for prev != d. This enforces the rule that adjacent columns must differ.
Because digits range only from 0-9, each column checks at most 10 previous states. The algorithm scans the grid once to compute frequencies and then runs a small DP per column. This combines counting techniques from array processing with column-based state transitions.
Recommended for interviews: The dynamic programming approach is the expected solution. It clearly models the dependency between adjacent columns and runs in near linear time relative to the grid size. A greedy attempt shows understanding of column conversion costs, but the DP solution demonstrates stronger algorithmic reasoning and handles all edge cases correctly.
To satisfy the conditions, each column can maintain a consistent value, and alternate different values between adjacent columns. The key is to set each column to a distinct value for a valid 'equal' and 'not equal' pattern within rows. This approach involves filling the grid column by column ensuring the row-wise condition is satisfied with minimal changes.
The solution iterates through each column and aligns vertical values to the starting value of each column, while alternating and modifying horizontal values to ensure adjacent column values are different. This ensures the pattern defined by the question with a minimal number of operations required.
Time Complexity: O(m * n) - We iterate through every cell in the matrix.
Space Complexity: O(1) - Modifying the input grid directly, no extra space needed.
This greedy approach focuses on iterating over each cell and immediately correcting any discrepancies such as a mismatch with a below cell or similarity with the right cell. It tries to correct them with the least number of changes as it progresses through the matrix.
This Java implementation iterates through each cell checking the defined conditions. It adjusts the grid by making necessary changes immediately, incrementing the count of operations whenever a change is made. This ensures that by the end of the iteration, the conditions are satisfied.
Java
JavaScript
Time Complexity: O(m * n) - The solution processes every cell systematically.
Space Complexity: O(1) - Modifying the input matrix in place.
We notice that the values in the cells of the matrix only have 10 possibilities. The problem requires us to find the minimum number of operations for each column to have the same number, and the numbers in adjacent columns are different. Therefore, we only need to consider the case of modifying the number to 0 to 9.
We define the state f[i][j] to represent the minimum number of operations for the numbers in the first [0,..i] columns, and the number in the i-th column is j. Then we can get the state transition equation:
$
f[i][j] = min_{k neq j} (f[i-1][k] + m - cnt[j])
Where cnt[j] represents the number of cells in the i-th column that are j.
Finally, we only need to find the minimum value of f[n-1][j].
The time complexity is O(n times (m + C^2)), and the space complexity is O(n times C). Where m and n represent the number of rows and columns in the matrix respectively; and C represents the number of types of numbers, here C = 10$.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Row and Column Pattern Matching | Time Complexity: O(m * n) - We iterate through every cell in the matrix. |
| Greedy Matrix Adjustment | Time Complexity: O(m * n) - The solution processes every cell systematically. |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Matrix Adjustment | O(m * n * 10) | O(1) | Quick heuristic when approximating minimal column conversions |
| Row and Column Pattern Matching (Dynamic Programming) | O(m * n * 10 + n * 10 * 10) | O(10) | General optimal solution ensuring adjacent columns differ |
3122. Minimum Number of Operations to Satisfy Conditions | DP & Not Greedy • Aryan Mittal • 5,983 views views
Watch 7 more video solutions →Practice Minimum Number of Operations to Satisfy Conditions with our built-in code editor and test cases.
Practice on FleetCode