Minimum Number of Operations to Satisfy Conditions

Medium
1653.

Minimum Number of Operations to Satisfy Conditions

Minimum Number of Operations to Satisfy Conditions is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon interviews.

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 <= 1000
  • 0 <= grid[i][j] <= 9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minimumOperations = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 1000
  • 0 <= grid[i][j] <= 9

Hints for Minimum Number of Operations to Satisfy Conditions

  1. Hint 1

    Each column ends up as a single value, and only neighbouring columns interact.

  2. Hint 2

    Choosing a value outside 0–9 never helps: some digit not used by either neighbour is always available and costs no more.

  3. Hint 3

    dp[j][v] = cheapest way to fix columns 0..j with column j set to v = (rows of column j not equal to v) + the best dp[j-1][u] with u ≠ 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

  1. For each column j, count how many cells hold each digit; the cost of colour v is m - count[v].
  2. dp[0][v] = cost(0, v).
  3. dp[j][v] = cost(j, v) + min over u ≠ v of dp[j-1][u].
  4. 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