Columns Going Up

Easy

You are given a table table of non-negative integers. One step adds 1 to any single cell. Every column must be **strictly increasing** from top to bottom. What is the minimum number of steps required?

Example 1

table=[[4, 1], [2, 1], [5, 0]] → 8

First column: 2 → 5 (3 steps), 5 → 6 (1 step). Second column: 1 → 2 (1 step), 0 → 3 (3 steps). 8 in total.

Example 2

table=[[0, 7, 3], [1, 8, 9]] → 0

Every column already grows strictly from top to bottom.

Example 3

table=[[2], [2], [2], [2]] → 6

Constraints

1 ≤ len(table), len(table[0]) ≤ 500
All rows have the same length
0 ≤ table[i][j] < 2500

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Matrix

Similar problems

Raise Towers, Keep the Skyline Medium Best Binary Rows After Flips Medium Two Rows of Lamps Medium Rows Under the Diagonal Medium A Table From Its Totals Medium

Input

table=[[4, 1], [2, 1], [5, 0]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 87 tests on the server, hidden ones included.