Skip to main content
Talentd

Minimum Number of Operations to Satisfy Conditions - Solution & Explanation

MediumArrayDynamic ProgrammingMatrix14 min readAsked at: Turing
Practice this problem

Problem Statement

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

Approach Overview

Problem 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.

Approach 1: Row and Column Pattern Matching

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Greedy Matrix Adjustment

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(m * n) - The solution processes every cell systematically.
Space Complexity: O(1) - Modifying the input matrix in place.

Try this approach in the editor →

Approach 3: Dynamic Programming

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$.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Row and Column Pattern Matching

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.

Greedy Matrix Adjustment

Time Complexity: O(m * n) - The solution processes every cell systematically.
Space Complexity: O(1) - Modifying the input matrix in place.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Matrix AdjustmentO(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

Video Solution

3122. Minimum Number of Operations to Satisfy Conditions | DP & Not Greedy • Aryan Mittal • 6,281 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Number of Operations to Satisfy Conditions easy or hard?
The problem is rated Medium because the grid manipulation itself is simple, but recognizing the column dependency requires dynamic programming. Once the state dp[column][digit] is defined, the transitions and implementation are straightforward.
Minimum Number of Operations to Satisfy Conditions Python/Java solution
Most implementations compute column frequencies and then apply dynamic programming across columns. Python, Java, and C++ solutions follow the same structure: build a cost matrix for digits 0-9 per column and update dp states while ensuring adjacent digits differ.
How to solve Minimum Number of Operations to Satisfy Conditions in O(n)?
After computing column frequency counts in O(m * n), the dynamic programming stage processes each column with only 10 possible digits. Each state checks the previous 9 alternatives, making the DP step effectively O(n). The constant factor is small because the digit range is fixed (0-9).
What is the best approach for Minimum Number of Operations to Satisfy Conditions?
The best approach uses dynamic programming with column frequency counting. First compute the cost to convert each column into digits 0-9, then run DP where dp[j][d] represents the minimum operations if column j becomes digit d. The transition ensures adjacent columns use different digits. This solution runs in O(m * n * 10 + n * 100) time.
Is Minimum Number of Operations to Satisfy Conditions asked at Google/Amazon/Meta?
Grid transformation and dynamic programming problems like this appear frequently in interviews at companies such as Google, Amazon, and Meta. Variants that enforce constraints between adjacent columns or rows are common because they test DP state design and matrix processing skills.
What data structure is used in Minimum Number of Operations to Satisfy Conditions?
The solution mainly uses arrays for column frequency counting and a small dynamic programming table of size n x 10. Each column stores counts for digits 0-9, and the DP transitions track the minimal cost for each possible column value.
What is the time complexity of Minimum Number of Operations to Satisfy Conditions?
The optimal algorithm runs in O(m * n * 10 + n * 10 * 10) time. Counting digit frequencies for each column takes O(m * n), and the dynamic programming step evaluates at most 100 transitions per column. Space complexity can be reduced to O(10) by keeping only the previous column state.

Ready to solve this problem?

Practice Minimum Number of Operations to Satisfy Conditions with our built-in code editor and test cases.

Practice on FleetCode
Previous

Candy

Next

Distribute Candies