Minimum Operations to Make Columns Strictly Increasing

Difficulty: Easy | Acceptance: 72.70% | Paid: No Topics: Array, Greedy, Matrix

You are given a 0-indexed m x n integer matrix grid.

In one operation, you can choose any cell (i, j) and increment the value of grid[i][j] by 1.

You want to make every column strictly increasing. That is, for every column, every row’s value must be strictly greater than the row above it.

Return the minimum number of operations needed to make every column strictly increasing.

• Examples
• Constraints
• Greedy Column Traversal

Examples

Example 1:

Input: grid = [[3,2],[1,2]]
Output: 4
Explanation:
- Column 0: [3, 1] -> [3, 2] -> [3, 3] -> [3, 4] (3 operations)
- Column 1: [2, 2] -> [2, 3] (1 operation)
Total operations: 3 + 1 = 4.

Example 2:

Input: grid = [[1,2],[2,1]]
Output: 2
Explanation:
- Column 0: [1, 2] is already strictly increasing (0 operations)
- Column 1: [2, 1] -> [2, 2] -> [2, 3] (2 operations)
Total operations: 0 + 2 = 2.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 1000

Greedy Column Traversal

Intuition Since operations on one column do not affect other columns, we can process each column independently. For each column, we iterate from top to bottom. If the current element is greater than the previous one, no operation is needed. If it is less than or equal to the previous one, we must increment it to previous + 1 to maintain the strictly increasing property with minimum cost.

Steps

• Initialize operations to 0.
• Iterate through each column j from 0 to n - 1.
• For each column, initialize previous with the value of the first row grid[0][j].
• Iterate through rows i from 1 to m - 1.
• Let current be grid[i][j].
• If current > previous, update previous to current.
• Otherwise, calculate the required increment diff = previous + 1 - current. Add diff to operations. Update previous to previous + 1.
• Return the total operations.

from typing import List

class Solution:
    def minimumOperations(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        ops = 0
        
        for c in range(n):
            prev = grid[0][c]
            for r in range(1, m):
                curr = grid[r][c]
                if curr <= prev:
                    ops += (prev + 1 - curr)
                    prev = prev + 1
                else:
                    prev = curr
                    
        return ops

Complexity

• Time: O(m × n)
• Space: O(1)
• Notes: We iterate through every element in the matrix exactly once. We only use a constant amount of extra space for variables.