Minimum Number of Operations to Satisfy Conditions

Minimum Number of Operations to Satisfy Conditions - 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.

Input & Output

Example 1 — Basic 3x3 Grid

$ Input: grid = [[1,1,1],[0,0,0],[1,0,1]]

› Output: 3

💡 Note: Make column 0 all 1s (cost 0), column 1 all 0s (cost 1), column 2 all 1s (cost 2). Total: 3 operations.

Example 2 — Already Valid

$ Input: grid = [[1,0,2],[1,0,2]]

› Output: 0

💡 Note: Each column has uniform values and adjacent columns differ. No operations needed.

Example 3 — Single Row

$ Input: grid = [[1,2,3,4]]

› Output: 4

💡 Note: Change to [0,1,0,1] - each column uniform, adjacent differ. Cost: 1+1+1+1 = 4.

Constraints

1 ≤ m, n ≤ 1000
0 ≤ grid[i][j] ≤ 9

Visualization

Tap to expand

Understanding the Visualization

Input Grid

3x3 grid with mixed values [[1,1,1],[0,0,0],[1,0,1]]

Column Analysis

Count frequencies and determine optimal values per column

Output

Minimum operations needed: 3

Key Takeaway

🎯 Key Insight: Transform into column-wise optimization where each column must be uniform and adjacent columns must have different values. Use DP with frequency counting for optimal solution.

Asked in

G Google 42 f Meta 35 a Amazon 28

The key insight is that each column must have uniform values and adjacent columns must differ. We can limit values to {0,1,2} and use dynamic programming with frequency counting. Count frequency of each value per column, then use DP where dp[col][val] represents minimum operations for columns 0 to col with column col having value val. Best approach: DP with frequency optimization. Time: O(m×n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Frequency Count	O(m × n)	O(n)	Use DP with frequency counting to find optimal column assignments
Brute Force with Recursion	O(3^n)	O(n)	Try all possible values (0-2) for each column recursively

Dynamic Programming with Frequency Count — Algorithm Steps

Count frequency of values 0, 1, 2 in each column
Use DP: dp[col][val] = min operations for columns 0 to col with col=val
Transition: dp[col][val] = cost[col][val] + min(dp[col-1][other_val])
Return minimum across all values for last column

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count 0s, 1s, 2s in each column

DP Transition

dp[col][val] = cost + min(dp[col-1][other])

Result

Minimum across all values for last column

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int** grid, int m, int n) {
    if (m == 0 || n == 0) return 0;
    
    // Count frequency of each value in each column
    int freq[n][3];
    memset(freq, 0, sizeof(freq));
    
    for (int col = 0; col < n; col++) {
        for (int row = 0; row < m; row++) {
            if (grid[row][col] >= 0 && grid[row][col] <= 2) {
                freq[col][grid[row][col]]++;
            }
        }
    }
    
    // DP: prevDp represents min operations for previous column with each value
    int prevDp[3] = {m - freq[0][0], m - freq[0][1], m - freq[0][2]};
    
    for (int col = 1; col < n; col++) {
        int currDp[3] = {INT_MAX, INT_MAX, INT_MAX};
        for (int val = 0; val < 3; val++) {
            int cost = m - freq[col][val];
            for (int prevVal = 0; prevVal < 3; prevVal++) {
                if (prevVal != val) {
                    if (prevDp[prevVal] + cost < currDp[val]) {
                        currDp[val] = prevDp[prevVal] + cost;
                    }
                }
            }
        }
        memcpy(prevDp, currDp, sizeof(prevDp));
    }
    
    int minOps = prevDp[0];
    if (prevDp[1] < minOps) minOps = prevDp[1];
    if (prevDp[2] < minOps) minOps = prevDp[2];
    
    return minOps;
}

int main() {
    // Simplified parsing for basic test
    int m = 3, n = 3;
    int** grid = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        grid[i] = (int*)malloc(n * sizeof(int));
    }
    
    // Example grid [[1,1,1],[0,0,0],[1,0,1]]
    int data[3][3] = {{1,1,1}, {0,0,0}, {1,0,1}};
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            grid[i][j] = data[i][j];
        }
    }
    
    printf("%d\n", solution(grid, m, n));
    
    for (int i = 0; i < m; i++) {
        free(grid[i]);
    }
    free(grid);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n)

We iterate through m rows and n columns to count frequencies, then O(n) for DP

✓ Linear Growth

Space Complexity

O(n)

DP table stores 3 values for each of n columns

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Frequency Count — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler