Scale Engineer

Minimum Number of Operations to Satisfy Conditions

Med
#2774Time: 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).1 company
Patterns
Dynamic Programming
Data structures
ArrayMatrix
Companies
Turing

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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

Walkthrough

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;    }}

Complexity

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

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem