problemeasyalgorithmsleetcode-3402leetcode 3402leetcode3402

Minimum Operations to Make Columns Strictly Increasing

EasyUpdated: Aug 2, 2025
Practice on:
LeetCode

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.

Examples

Example 1

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

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

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

C++
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;
    }
};
Go
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
}
Java
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;
    }
}
Kotlin
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
    }
}
Python
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
Rust
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
    }
}
TypeScript
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.

Comments