Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1000. Delete Columns to Make Sorted III

My accepted Python solution to LeetCode problem 1000, Delete Columns to Make Sorted III, running in 57ms.

  • Difficulty: Hard
  • Python
  • Runtime 57ms
  • Memory 17.6MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 57ms, memory 17.6MB, accepted 2025-12-30.

python
class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        n = len(strs)
        m = len(strs[0])
        
        # dp[j] = length of longest valid subsequence ending at column j
        dp = [1] * m
        
        for j in range(m):
            for i in range(j):
                # Check if column i can come before column j
                # For all rows, strs[row][i] <= strs[row][j]
                valid = True
                for row in range(n):
                    if strs[row][i] > strs[row][j]:
                        valid = False
                        break
                if valid:
                    dp[j] = max(dp[j], dp[i] + 1)
        
        # Answer is total columns minus longest valid subsequence
        return m - max(dp)

Source