Problem statement

https://leetcode.com/problems/delete-columns-to-make-sorted-ii/

Solution

Let us work in greedy strategy: go from the first element and check if we have some break of order. We keep unsorted set is the set of indexes x, such that we do not have row x smaller than row x + 1 yet.

  1. If we have some break of order, we need to remove this column and add it to answer.
  2. If we do not have break of order, we have two options: A[i][j] = A[i + 1][j] or A[i][j] < A[i + 1][j]. In the first case we do not have sorted yet. In the second we now know that this pair is sorted, so we remove it from set.

Complexity

It is O(mn) for time and O(n) for space.

Code

class Solution:
    def minDeletionSize(self, A):
        res, n, m = 0, len(A), len(A[0])
        unsorted = set(range(n - 1))
        for j in range(m):
            if any(A[i][j] > A[i + 1][j] for i in unsorted):
                res += 1
            else:
                unsorted -= {i for i in unsorted if A[i][j] < A[i + 1][j]}
        return res