Minimum Operations to Make Columns Strictly Increasing

EasyArrayGreedyMatrix

Solution

export function minimumOperations(grid: number[][]): number {
  const [m, n] = [grid.length, grid[0].length];
 
  let answer = 0;
  for (let x = 0; x < n; x++) {
    for (let y = 1; y < m; y++) {
      if (grid[y - 1][x] < grid[y][x]) {
        continue;
      }
      answer += grid[y - 1][x] - grid[y][x] + 1;
      grid[y][x] = grid[y - 1][x] + 1;
    }
  }
  return answer;
}

Complexity

  • Time: O(mn)O(m \cdot n)
  • Space: O(1)O(1)