Problem

You are given a m x n matrix grid consisting of non-negative integers.

In one operation, you can increment the value of any grid[i][j] by 1.

Return the minimum number of operations needed to make all columns of grid strictly increasing.

Example 1

1
2
3
4
5
6

Input: grid = [[3,2],[1,3],[3,4],[0,1]]
Output: 15
Explanation:
* To make the `0th` column strictly increasing, we can apply 3 operations on `grid[1][0]`, 2 operations on `grid[2][0]`, and 6 operations on `grid[3][0]`.
* To make the `1st` column strictly increasing, we can apply 4 operations on `grid[3][1]`.
![](https://assets.leetcode.com/uploads/2024/11/10/firstexample.png)

Example 2

1
2
3
4
5
6
7

Input: grid = [[3,2,1],[2,1,0],[1,2,3]]
Output: 12
Explanation:
* To make the `0th` column strictly increasing, we can apply 2 operations on `grid[1][0]`, and 4 operations on `grid[2][0]`.
* To make the `1st` column strictly increasing, we can apply 2 operations on `grid[1][1]`, and 2 operations on `grid[2][1]`.
* To make the `2nd` column strictly increasing, we can apply 2 operations on `grid[1][2]`.
![](https://assets.leetcode.com/uploads/2024/11/10/secondexample.png)

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 0 <= grid[i][j] < 2500

Examples

Solution

Method 1 – Greedy Column-wise Increment

Intuition

To make each column strictly increasing, for every cell below the first row, if its value is not greater than the cell above, increment it enough to be one more than the cell above. Sum all such increments for all columns.

Approach

  1. For each column, iterate from the second row to the last.
  2. If grid[i][j] <= grid[i-1][j], increment grid[i][j] by (grid[i-1][j] - grid[i][j] + 1) and add to the answer.
  3. Continue for all columns and rows.
  4. Edge case: If all columns are already strictly increasing, answer is 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int minOperations(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size(), ans = 0;
        for (int j = 0; j < n; ++j) {
            for (int i = 1; i < m; ++i) {
                if (grid[i][j] <= grid[i-1][j]) {
                    ans += grid[i-1][j] - grid[i][j] + 1;
                    grid[i][j] = grid[i-1][j] + 1;
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func minOperations(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    ans := 0
    for j := 0; j < n; j++ {
        for i := 1; i < m; i++ {
            if grid[i][j] <= grid[i-1][j] {
                ans += grid[i-1][j] - grid[i][j] + 1
                grid[i][j] = grid[i-1][j] + 1
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int minOperations(int[][] grid) {
        int m = grid.length, n = grid[0].length, ans = 0;
        for (int j = 0; j < n; j++) {
            for (int i = 1; i < m; i++) {
                if (grid[i][j] <= grid[i-1][j]) {
                    ans += grid[i-1][j] - grid[i][j] + 1;
                    grid[i][j] = grid[i-1][j] + 1;
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun minOperations(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid[0].size
        var ans = 0
        for (j in 0 until n) {
            for (i in 1 until m) {
                if (grid[i][j] <= grid[i-1][j]) {
                    ans += grid[i-1][j] - grid[i][j] + 1
                    grid[i][j] = grid[i-1][j] + 1
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def minOperations(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = 0
        for j in range(n):
            for i in range(1, m):
                if grid[i][j] <= grid[i-1][j]:
                    ans += grid[i-1][j] - grid[i][j] + 1
                    grid[i][j] = grid[i-1][j] + 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn min_operations(mut grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut ans = 0;
        for j in 0..n {
            for i in 1..m {
                if grid[i][j] <= grid[i-1][j] {
                    ans += grid[i-1][j] - grid[i][j] + 1;
                    grid[i][j] = grid[i-1][j] + 1;
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    minOperations(grid: number[][]): number {
        const m = grid.length, n = grid[0].length;
        let ans = 0;
        for (let j = 0; j < n; j++) {
            for (let i = 1; i < m; i++) {
                if (grid[i][j] <= grid[i-1][j]) {
                    ans += grid[i-1][j] - grid[i][j] + 1;
                    grid[i][j] = grid[i-1][j] + 1;
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(m * n) — We scan every cell once.
  • 🧺 Space complexity: O(1) — Only a few variables are used, no extra space proportional to input size.