Delete Columns to Make Sorted II - Video Solutions

Problem Overview: You are given an array of equal-length strings. You may delete any column. The goal is to remove the minimum number of columns so the rows remain lexicographically sorted from top to bottom.

Approach 1: Greedy Column Validation (O(m*n) time, O(m) space)

This approach scans columns from left to right and greedily decides whether a column must be deleted. Maintain an array sorted where sorted[i] indicates whether row i is already confirmed to be lexicographically smaller than row i+1. For each column, check every unresolved adjacent pair. If a column causes strs[i][col] > strs[i+1][col], the column must be deleted. Otherwise, update pairs that become strictly ordered. The key insight: once a pair is confirmed sorted, future columns cannot invalidate it. This prevents unnecessary comparisons and ensures each column is processed once.

The greedy rule works because lexicographic order is determined by the first differing character. If a column breaks order for an unresolved pair, keeping it would permanently violate sorting. This makes deletion the only safe choice. The algorithm iterates through array columns and performs character comparisons across rows, making it efficient even when string length grows.

Approach 2: Dynamic Programming on Columns (O(n^2 * m) time, O(n) space)

The dynamic programming view treats each column as a potential element in a valid subsequence of columns that preserves lexicographic order. Define dp[c] as the maximum number of columns that can end with column c. For every earlier column p, check whether keeping both columns maintains non-decreasing characters for every row: strs[r][p] <= strs[r][c]. If valid, update dp[c] = max(dp[c], dp[p] + 1). The longest valid column subsequence determines how many columns you can keep, and the rest must be deleted.

This approach resembles a longest increasing subsequence over columns but validated across all rows simultaneously. It relies heavily on repeated comparisons across rows of the string matrix. While conceptually clean, the quadratic column comparisons make it slower than the greedy strategy for large inputs.

Recommended for interviews: The greedy approach is the expected solution. It uses a simple observation about lexicographic ordering and avoids unnecessary checks once row pairs become fixed. The DP approach demonstrates deeper reasoning about column subsequences, but its O(n^2 * m) complexity is rarely preferred when the greedy greedy solution achieves optimal performance.