Skip to content

3402. Minimum Operations to Make Columns Strictly Increasing

Description

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:

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].

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].

 

Constraints:

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

 

 

Solutions

Solution 1: Column-wise Calculation

Thinking

We may only increase cells, and columns are independent. Searching over every feasible final value in a column is unnecessary: a single pass over the grid already fits the size.

Strict increase raises the lower bound for later cells. Once a cell is forced up, every subsequent cell in that column inherits a higher floor.

We therefore scan each column from top to bottom, keeping the previous final value \(\textit{pre}\). If the current value already exceeds \(\textit{pre}\), we keep it; otherwise we raise it to \(\textit{pre}+1\) and add the gap to the answer. This assigns the minimum increment per column independently.

We can traverse the matrix column by column. For each column, we calculate the minimum number of operations required to make it strictly increasing. Specifically, for each column, we maintain a variable \(\textit{pre}\) to represent the value of the previous element in the current column. Then, we traverse the current column from top to bottom. For the current element \(\textit{cur}\), if \(\textit{pre} < \textit{cur}\), it means the current element is already greater than the previous element, so we only need to update \(\textit{pre} = \textit{cur}\). Otherwise, we need to increase the current element to \(\textit{pre} + 1\) and add the number of increases to the answer.

The time complexity is \(O(m \times n)\), where \(m\) and \(n\) are the number of rows and columns of the matrix \(\textit{grid}\), respectively. The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def minimumOperations(self, grid: List[List[int]]) -> int:
        ans = 0
        for col in zip(*grid):
            pre = -1
            for cur in col:
                if pre < cur:
                    pre = cur
                else:
                    pre += 1
                    ans += pre - cur
        return ans

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minimumOperations(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = 0;
        for (int j = 0; j < n; ++j) {
            int pre = -1;
            for (int i = 0; i < m; ++i) {
                int cur = grid[i][j];
                if (pre < cur) {
                    pre = cur;
                } else {
                    ++pre;
                    ans += pre - cur;
                }
            }
        }
        return ans;
    }
};

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function minimumOperations(grid: number[][]): number {
    const [m, n] = [grid.length, grid[0].length];
    let ans: number = 0;
    for (let j = 0; j < n; ++j) {
        let pre: number = -1;
        for (let i = 0; i < m; ++i) {
            const cur = grid[i][j];
            if (pre < cur) {
                pre = cur;
            } else {
                ++pre;
                ans += pre - cur;
            }
        }
    }
    return ans;
}

Comments