Minimum Operations to Make Columns Strictly Increasing
Source: leetcode
Difficulty: Easy
Tags: array, greedy, matrix

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


![](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`


 





```


 
```





C++ solution:
class Solution {
public:
    int minimumOperations(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        long long total = 0;
        for (int j = 0; j < n; j++) {
            int cur = grid[0][j];
            for (int i = 1; i < m; i++) {
                int req = cur + 1;
                if (grid[i][j] < req) {
                    total += req - grid[i][j];
                    cur = req;
                } else {
                    cur = grid[i][j];
                }
            }
        }
        return (int)total;
    }
};

Go solution:
func minimumOperations(grid [][]int) int {
	m := len(grid)
	if m == 0 {
		return 0
	}
	n := len(grid[0])
	ops := 0
	for j := 0; j < n; j++ {
		prev := grid[0][j]
		for i := 1; i < m; i++ {
			required := prev + 1
			if grid[i][j] < required {
				ops += required - grid[i][j]
				prev = required
			} else {
				prev = grid[i][j]
			}
		}
	}
	return ops
}

Java solution:
class Solution {
    public int minimumOperations(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int operations = 0;
        for (int col = 0; col < n; col++) {
            int current = grid[0][col];
            for (int row = 1; row < m; row++) {
                int needed = current + 1;
                if (grid[row][col] < needed) {
                    operations += (needed - grid[row][col]);
                    current = needed;
                } else {
                    current = grid[row][col];
                }
            }
        }
        return operations;
    }
}

JavaScript solution:
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minimumOperations = function(grid) {
    let m = grid.length, n = grid[0].length, totalOps = 0;
    for (let j = 0; j < n; j++) {
        let prev = grid[0][j];
        for (let i = 1; i < m; i++) {
            let required = prev + 1;
            if (grid[i][j] < required) {
                totalOps += required - grid[i][j];
                prev = required;
            } else {
                prev = grid[i][j];
            }
        }
    }
    return totalOps;
};

Python solution:
class Solution:
    def minimumOperations(self, grid: list[list[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        operations = 0
        for j in range(n):
            prev = grid[0][j]
            for i in range(1, m):
                expected = prev + 1
                if grid[i][j] < expected:
                    operations += expected - grid[i][j]
                    prev = expected
                else:
                    prev = grid[i][j]
        return operations

Ruby solution:
def minimum_operations(grid)
  m = grid.size
  n = grid[0].size
  total_ops = 0
  (0...n).each do |col|
    current = grid[0][col]
    (1...m).each do |row|
      if grid[row][col] <= current
        diff = current + 1 - grid[row][col]
        total_ops += diff
        current += 1
      else
        current = grid[row][col]
      end
    end
  end
  total_ops
end