Minimum Number of Operations to Satisfy Conditions Solution
Minimum Number of Operations to Satisfy Conditions solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Number of Operations to Satisfy Conditions is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Matrix
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an m x n matrix grid of digits. In one operation you may change any cell to any non-negative integer.
You want every cell to satisfy both conditions:
- it equals the cell below it, if that cell exists (
grid[i][j] == grid[i + 1][j]), and - it differs from the cell to its right, if that cell exists (
grid[i][j] != grid[i][j + 1]).
In other words, each column must be filled with one value, and neighbouring columns must use different values. Return the minimum number of operations needed.
Example 1
Input: grid = [[1,0,2],[1,0,2]]
Output: 0
Explanation: Every column is already uniform and neighbours differ.
Example 2
Input: grid = [[1,1,1],[0,0,0]]
Output: 3
Explanation: Make the columns 1, 0, 1 (or 0, 1, 0): one change in each column.
Example 3
Input: grid = [[1],[2],[3]]
Output: 2
Explanation: A single column: keep one of the values, change the other two.
Constraints
1 <= n, m <= 10000 <= grid[i][j] <= 9
Hints for Minimum Number of Operations to Satisfy Conditions
Hint 1
Each column ends up as a single value, and only neighbouring columns interact.
Hint 2
Choosing a value outside 0–9 never helps: some digit not used by either neighbour is always available and costs no more.
Hint 3
dp[j][v]= cheapest way to fix columns0..jwith columnjset tov= (rows of columnjnot equal tov) + the bestdp[j-1][u]withu ≠ v.
How to solve Minimum Number of Operations to Satisfy Conditions
The conditions say: columns are constant, adjacent columns differ. So the task is to colour a path of n columns with digits, where colouring column j with v costs the number of its cells not already equal to v, and neighbouring colours must differ.
Approach
- For each column
j, count how many cells hold each digit; the cost of colourvism - count[v]. dp[0][v] = cost(0, v).dp[j][v] = cost(j, v) + min over u ≠ v of dp[j-1][u].- Return the minimum of
dp[n-1][v].
Why it works
The cost decomposes over columns and the only constraint links consecutive columns, so a left-to-right DP over the colour of the last column is exact. Restricting colours to 0–9 loses nothing: any optimal colouring that uses another number can swap it for a digit different from both neighbours (ten digits, at most two forbidden), which changes no more cells, since no cell held the outside number to begin with.
Complexity
- Time —
O(m · n + n · 10 · 10) - Space —
O(10)
Pitfalls
- Count per column before the DP — recounting inside the colour loop makes it
O(m · n · 10), still fine but wasteful. - The first column has no left neighbour, so every colour is allowed there.
- A single row still needs adjacent cells to differ.
Reference solution
Python
from typing import List
def minimumOperations(grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
prev = None
for c in range(n):
cnt = [0] * 10
for r in range(m):
cnt[grid[r][c]] += 1
cur = [0] * 10
for v in range(10):
cost = m - cnt[v]
if prev is None:
cur[v] = cost
else:
cur[v] = cost + min(prev[u] for u in range(10) if u != v)
prev = cur
return min(prev)Java
public static int minimumOperations(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] prev = new int[10];
for (int c = 0; c < n; c++) {
int[] cnt = new int[10];
for (int r = 0; r < m; r++) cnt[grid[r][c]]++;
int[] cur = new int[10];
for (int v = 0; v < 10; v++) {
int best = 0;
if (c > 0) {
best = Integer.MAX_VALUE;
for (int u = 0; u < 10; u++) if (u != v) best = Math.min(best, prev[u]);
}
cur[v] = m - cnt[v] + best;
}
prev = cur;
}
int ans = Integer.MAX_VALUE;
for (int v : prev) ans = Math.min(ans, v);
return ans;
}C++
int minimumOperations(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<int> prev(10, 0);
for (int c = 0; c < n; c++) {
int cnt[10] = {0};
for (int r = 0; r < m; r++) cnt[grid[r][c]]++;
vector<int> cur(10, 0);
for (int v = 0; v < 10; v++) {
int best = 0;
if (c > 0) {
best = INT_MAX;
for (int u = 0; u < 10; u++) if (u != v) best = min(best, prev[u]);
}
cur[v] = m - cnt[v] + best;
}
prev = cur;
}
return *min_element(prev.begin(), prev.end());
}JavaScript
var minimumOperations = function(grid) {
var m = grid.length, n = grid[0].length;
var prev = null;
for (var c = 0; c < n; c++) {
var cnt = new Array(10).fill(0);
for (var r = 0; r < m; r++) cnt[grid[r][c]]++;
var cur = new Array(10).fill(0);
for (var v = 0; v < 10; v++) {
var best = 0;
if (prev !== null) {
best = Infinity;
for (var u = 0; u < 10; u++) if (u !== v && prev[u] < best) best = prev[u];
}
cur[v] = m - cnt[v] + best;
}
prev = cur;
}
return Math.min.apply(null, prev);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming