# Minimum Operations to Make Columns Strictly Increasing
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-operations-to-make-columns-strictly-increasing)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-make-columns-strictly-increasing
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Matrix
---
## 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:**

**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.glich.co/dsa/minimum-operations-to-make-columns-strictly-increasing/image0.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.glich.co/dsa/minimum-operations-to-make-columns-strictly-increasing/image1.png)

**Constraints:**

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

# Approaches
## Dynamic Programming per Column
This approach solves the problem for each column independently using dynamic programming. For each column, we build a DP table to find the minimum operations. The state `dp[i][v]` represents the minimum cost to make the prefix of the column of length `i+1` strictly increasing, with the `i`-th element's new value being `v`. This is a valid but less efficient method compared to a simpler greedy strategy.
**Time:** O(n * m * V_max), where `n` is the number of columns, `m` is the number of rows, and `V_max` is the upper bound on element values. For each of the `n` columns, we iterate `m-1` times. In each iteration, we compute a DP row of size `V_max`, which takes `O(V_max)` time. · **Space:** O(V_max), where `V_max` is a calculated upper bound for element values (e.g., `max_initial_val + m`). This is because we use two arrays of size `V_max` to store DP states for the current and previous rows for each column.
**Pros:** It is a systematic approach that correctly finds the optimal solution.; Demonstrates the application of dynamic programming to solve this type of optimization problem.
**Cons:** Significantly more complex to understand and implement compared to the greedy approach.; Worse time complexity `O(n * m * V_max)`.; Worse space complexity `O(V_max)`.; Requires determining a safe upper bound `V_max` for the element values, which adds a layer of analysis.
### Explanation
The problem can be broken down by columns, as the modifications in one column do not affect any other. The total minimum operations is the sum of minimum operations required for each individual column.

For a single column, we can formulate a dynamic programming solution. Let `dp[i][v]` be the minimum number of operations to make the first `i+1` elements (from row 0 to `i`) of the column strictly increasing, with the element at row `i` having the final value `v`.

The state transition is derived as follows: to have the element at row `i` become `v`, we need `v - grid[i][j]` operations (assuming `v >= grid[i][j]`). The element at row `i-1` must have a final value `u` that is strictly less than `v`. To minimize the total cost, we should choose the `u` that resulted in the minimum operations for the prefix up to `i-1`. Thus, the recurrence relation is:
`dp[i][v] = (v - grid[i][j]) + min_{u < v} {dp[i-1][u]}`.

The base case is for the first row (`i=0`): `dp[0][v] = v - grid[0][j]` for `v >= grid[0][j]`.

The range for `v` needs to be determined. A safe upper bound is the maximum possible initial value in the grid plus the number of rows `m`, as in the worst case, we might need to increment by 1 for each subsequent row. Let's call this `V_max`.

A naive implementation of the transition would be slow. We can optimize the calculation of `min_{u < v} {dp[i-1][u]}`. For each row `i`, we can compute a running minimum of the `dp[i-1]` values. This allows us to find the minimum cost for the previous state in `O(1)` time.

We can also optimize space from `O(m * V_max)` to `O(V_max)` by only storing the DP results for the previous and current rows.

```java
import java.util.Arrays;

class Solution {
    public int minOperations(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        long totalOperations = 0;

        int maxInitialVal = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxInitialVal = Math.max(maxInitialVal, grid[i][j]);
            }
        }
        
        int V_MAX = maxInitialVal + m;

        for (int j = 0; j < n; j++) {
            long[] prevDp = new long[V_MAX];
            Arrays.fill(prevDp, Long.MAX_VALUE);

            // Base case: i = 0
            for (int v = grid[0][j]; v < V_MAX; v++) {
                prevDp[v] = v - grid[0][j];
            }

            // Iterate through rows i = 1 to m-1
            for (int i = 1; i < m; i++) {
                long[] currentDp = new long[V_MAX];
                Arrays.fill(currentDp, Long.MAX_VALUE);
                
                long minPrevCost = Long.MAX_VALUE;
                for (int v = 1; v < V_MAX; v++) {
                    minPrevCost = Math.min(minPrevCost, prevDp[v - 1]);
                    if (v >= grid[i][j] && minPrevCost != Long.MAX_VALUE) {
                        currentDp[v] = (long)(v - grid[i][j]) + minPrevCost;
                    }
                }
                prevDp = currentDp;
            }

            long minColOps = Long.MAX_VALUE;
            for (long ops : prevDp) {
                minColOps = Math.min(minColOps, ops);
            }
            if (minColOps != Long.MAX_VALUE) {
                totalOperations += minColOps;
            }
        }

        return (int)totalOperations;
    }
}
```
### Algorithm
- The core idea is that operations on one column are independent of others. We can calculate the minimum operations for each column and sum them up.
- For a single column, we can use dynamic programming. Let `dp[i][v]` be the minimum cost to make the prefix of the column of length `i+1` (i.e., `col[0...i]`) strictly increasing, with the final value of `col[i]` being `v`.
- The state transition is: `dp[i][v] = (v - col[i]) + min_{u < v} {dp[i-1][u]}`. This means the cost is the operations to change `col[i]` to `v`, plus the minimum cost for the previous `i-1` elements to be strictly increasing, ending in a value `u` that is less than `v`.
- The base case for `i=0` is `dp[0][v] = v - col[0]` for all `v >= col[0]`.
- To make the computation efficient, we can optimize finding `min_{u < v} {dp[i-1][u]}`. For each row `i`, we can pre-calculate a running minimum of the `dp[i-1]` row. This reduces the complexity of calculating each `dp[i][v]` from `O(V_max)` to `O(1)`.
- The final answer for a column is the minimum value in the last row of the DP table, `min(dp[m-1])`.
- We can optimize space by only keeping track of the previous and current rows of the DP table.

## Greedy Approach per Column
This optimal approach processes each column independently using a greedy strategy. For each column, we iterate from top to bottom (row 0 to m-1), ensuring that each element is strictly greater than the one above it. At each step, we perform the minimum number of increments necessary to satisfy this condition. This greedy choice at each step leads to the global minimum because making an element's value any larger than minimally required would only impose a stricter (and thus more costly) constraint on the elements below it.
**Time:** O(m * n), where `m` is the number of rows and `n` is the number of columns. We visit each cell of the grid exactly once. · **Space:** O(1). We only use a few variables to store the running total of operations and the previous element's modified value for each column.
**Pros:** Extremely efficient with a linear time complexity.; Uses constant extra space.; The logic is simple, intuitive, and easy to implement.
**Cons:** The correctness of the greedy strategy is not as formally proven as a DP solution, though it is correct for this problem.
### Explanation
The most efficient way to solve this problem is to recognize that the operations for each column are completely independent. Therefore, we can calculate the minimum operations for each column separately and sum them up to get the final answer.

For a single column, we can apply a greedy algorithm. We want to make the column `c_0, c_1, ..., c_{m-1}` strictly increasing, i.e., `c'_0 < c'_1 < ... < c'_{m-1}`, where `c'_i` is the value of `c_i` after operations. To minimize the total operations `sum(c'_i - c_i)`, we should aim to make each `c'_i` as small as possible.

Let's iterate through the column from top to bottom (row `i=0` to `m-1`).
- For the first element `grid[0][j]`, we don't need to change its value, as there is no element before it. Let's keep track of the value of the element in the previous row after modification, let's call it `prevModifiedVal`. We initialize `prevModifiedVal = grid[0][j]`.
- For the next element `grid[1][j]`, its new value must be strictly greater than `prevModifiedVal`. The smallest integer value it can take is `prevModifiedVal + 1`. Since we cannot decrease values, the new value must also be at least `grid[1][j]`. Therefore, the optimal new value for this cell is `max(grid[1][j], prevModifiedVal + 1)`.
- This logic extends to all rows. For any element `grid[i][j]`, its new value will be `max(grid[i][j], prevModifiedVal + 1)`. The number of operations for this cell is this new value minus its original value. We then update `prevModifiedVal` to this new value for the next row's calculation.

This simple, one-pass approach for each column guarantees the minimum number of operations.

```java
class Solution {
    public int minOperations(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int totalOperations = 0;

        // Process each column independently
        for (int j = 0; j < n; j++) {
            // The value of the element in the previous row after modification.
            // For the first row, it's just its original value.
            int prevModifiedVal = grid[0][j];

            // Iterate from the second row to the end
            for (int i = 1; i < m; i++) {
                int currentVal = grid[i][j];
                // The target value must be at least one greater than the previous modified value.
                int targetVal = prevModifiedVal + 1;
                
                if (currentVal < targetVal) {
                    // If the current value is too small, we must increment it.
                    // The number of operations is the difference.
                    totalOperations += targetVal - currentVal;
                    // The new value for this position becomes the target value.
                    prevModifiedVal = targetVal;
                } else {
                    // If the current value is large enough, no operations are needed.
                    // The new value is its original value.
                    prevModifiedVal = currentVal;
                }
            }
        }
        return totalOperations;
    }
}
```
### Algorithm
- The problem can be solved by processing each column independently since operations in one column do not affect others.
- For each column, we use a greedy approach. We iterate down the column from the top (row 0) to the bottom (row `m-1`).
- We maintain a variable, `prev_val`, which holds the required value of the element in the previous row after modification.
- For the first row (`i=0`), no operations are needed relative to a prior element. We initialize `prev_val` with `grid[0][j]`.
- For each subsequent row `i` (from 1 to `m-1`):
  - The current element `grid[i][j]` must be made strictly greater than `prev_val`. The minimum target value is `prev_val + 1`.
  - If `grid[i][j]` is already greater than `prev_val`, no operations are needed for this cell to satisfy the condition with respect to the previous one. We update `prev_val` to `grid[i][j]` for the next iteration.
  - If `grid[i][j]` is less than or equal to `prev_val`, we must increment it. The number of operations is `(prev_val + 1) - grid[i][j]`. We add this to our total and update `prev_val` to `prev_val + 1`.
- Summing the operations for all cells in all columns gives the total minimum operations.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```