Skip to main content
Talentd

Minimum Operations to Make Columns Strictly Increasing - Solution & Explanation

EasyArrayGreedyMatrix8 min readAsked at: IBM
Practice this problem

Problem Statement

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

 


 

Approach Overview

Problem Overview: You are given an m x n grid of integers. You can increment any cell by 1 in a single operation. The goal is to make every column strictly increasing from top to bottom while performing the minimum number of operations.

Approach 1: Increment Simulation (Brute Force) (Time: O(m * n * k), Space: O(1))

The straightforward idea is to process each column and repeatedly increment elements until the column becomes strictly increasing. For every cell grid[r][c], compare it with the element above it. If it is not greater, keep incrementing the current cell until it becomes prev + 1. Each increment is counted as a separate operation. This approach works but can perform many unnecessary repeated increments when the difference between values is large.

Because increments are simulated one-by-one, the effective complexity becomes O(m * n * k), where k represents the number of increments applied. While simple to reason about, it is inefficient for large values and mainly useful as a conceptual starting point.

Approach 2: Column-wise Greedy Calculation (Time: O(m * n), Space: O(1))

A more efficient strategy is to compute the required increments directly instead of simulating them. Iterate column by column. For each column, keep track of the previous value (the value in the row above after adjustments). If the current cell is already greater than the previous value, move on. Otherwise, calculate how much it must increase to become prev + 1.

Add the difference (prev + 1 - current) to the operation count and treat the cell's adjusted value as prev + 1. This greedy rule ensures the smallest possible increment that maintains the strictly increasing property. Each cell is processed once, making the algorithm linear in the number of elements.

This approach works because increasing a value more than necessary would only increase future constraints in the column. The optimal move is always the minimal increment that satisfies the order requirement.

Recommended for interviews: The greedy column-wise scan is the expected solution. It demonstrates understanding of arrays, matrix traversal, and a simple greedy optimization. Explaining the brute force idea first and then optimizing it to a direct calculation shows strong problem-solving progression.

Solution

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 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 cur, if pre < cur, it means the current element is already greater than the previous element, so we only need to update pre = cur. Otherwise, we need to increase the current element to 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 grid, respectively. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Increment Simulation (Brute Force)O(m * n * k)O(1)Conceptual baseline when first reasoning about the problem
Column-wise Greedy CalculationO(m * n)O(1)Optimal solution for interviews and production code

Video Solution

3402. Minimum Operations to Make Columns Strictly Increasing (Leetcode Easy) • Programming Live with Larry • 260 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Minimum Operations to Make Columns Strictly Increasing easy or hard?
The problem is classified as Easy. It mainly tests matrix traversal and a simple greedy observation: always increase a value to the smallest number that maintains strict ordering with the element above it.
Minimum Operations to Make Columns Strictly Increasing Python/Java solution
The typical implementation iterates through each column, keeps track of the previous adjusted value, and increases the current element if necessary. The same greedy logic works across Python, Java, C++, Go, and TypeScript with identical O(m * n) time complexity and O(1) extra space.
How to solve Minimum Operations to Make Columns Strictly Increasing in O(n)?
Treat each column independently and scan from the first row to the last. Maintain the previous value in the column. If the current value is less than or equal to the previous one, compute the required increment to make it prev + 1 and add that difference to the operation total. This avoids repeated increments and yields O(m * n) time complexity.
What is the best approach for Minimum Operations to Make Columns Strictly Increasing?
The optimal approach is a greedy column-wise traversal. Iterate through each column from top to bottom and ensure every value is greater than the previous one. If not, increase it to prev + 1 and add the required difference to the operation count. This method processes each cell once and runs in O(m * n) time with O(1) extra space.
Is Minimum Operations to Make Columns Strictly Increasing asked at Google/Amazon/Meta?
Problems involving greedy adjustments and matrix traversal frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that require enforcing ordering constraints with minimal operations are especially common in coding interviews.
What data structure is used in Minimum Operations to Make Columns Strictly Increasing?
The problem primarily uses a 2D array (matrix). No additional complex data structures are required. The solution relies on simple iteration and greedy value adjustments while traversing each column.
What is the time complexity of Minimum Operations to Make Columns Strictly Increasing?
The optimal greedy solution runs in O(m * n) time where m is the number of rows and n is the number of columns. Each cell is visited exactly once during the column scan. The space complexity is O(1) since only a few variables are used to track the previous value and operation count.

Ready to solve this problem?

Practice Minimum Operations to Make Columns Strictly Increasing with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Operations to Make the Array Increasing