Solution


Approach 1: Greedy

Intuition

If a column isn't sorted, it can't be part of the final answer.

Algorithm

For each column, check if its sorted. If it isn't, it must be deleted, so we add 1 to the final answer.

Complexity Analysis

  • Time Complexity: , where is the total content of A.

  • Space Complexity: .


Analysis written by: @awice.