Abstract / Summary

Remove the fewest columns so the remaining rows are in non-decreasing order.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 73% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of determining the minimum number of columns that must be removed from a list of equal-length strings so that the remaining columns are sorted lexicographically row-wise. It does this by finding the length of the longest sequence of columns that already satisfy the sorted condition and then subtracting that length from the total number of columns.

Key Steps

Determine the number of columns

The algorithm begins by measuring the length of the first string, which represents the total column count for all strings.

size = len(strs[0])

This step assumes that the input list is non-empty and that every string shares the same length, which aligns with the problem constraints.

Initialise dynamic-programming table

A one-dimensional table named good is created, with each entry initially set to 1. The entry at index i will eventually hold the length of the longest increasing subsequence (LIS) that ends at column i.

good = [1] * size

Build the LIS over columns

Two nested loops iterate over pairs of columns, where end is the later column and start is any earlier column. For each pair, the algorithm checks whether every string has a non-decreasing character relationship from start to end. The check uses Python’s all built-in to verify the condition across all strings in a single expression.

for end in range(1, size):
    for start in range(end):
        if all(word[start] <= word[end] for word in strs):
            good[end] = max(good[end], good[start] + 1)

If the condition holds, the LIS length ending at end can be extended by the LIS length ending at start. The max call ensures that the longest possible subsequence length is retained.

Compute the answer

After the DP table is populated, the maximum value in good corresponds to the length of the longest set of columns that already satisfy the sorted order. The required deletions are the total columns minus this length.

return size - max(good)

Edge Cases Handled

When every column already respects the sorted order across all rows, the inner all condition is true for every pair of columns, allowing the DP to grow the LIS to the full size. Consequently, max(good) equals size and the function returns 0, indicating no deletions are needed.

If no two columns can be placed together while preserving the sorted property, the DP never updates any entry beyond its initial value of 1. In that scenario max(good) is 1, and the function returns size - 1, meaning all but one column must be removed.

The use of all(word[start] <= word[end] for word in strs) gracefully handles the situation where the list contains a single string. The generator yields a single comparison per column pair, and the condition trivially holds, resulting in the LIS covering all columns and a return value of 0.

Because the algorithm accesses strs[0] only to obtain size, it implicitly requires at least one string in the input. This matches the problem’s guarantee that the input list is non-empty, so the function does not need additional guards for an empty list.

Performance Optimizations

The implementation leverages a compact DP array rather than a two-dimensional matrix, reducing memory overhead. By storing only the best LIS length ending at each column, the algorithm avoids recomputing intermediate results.

The inner condition uses a generator expression inside all, which short-circuits as soon as a violating pair of characters is found. This early exit prevents unnecessary comparisons for columns that already fail the sorted requirement, saving time especially when the strings are long and the violation occurs early in the list.

The max(good[start] + 1, good[end]) update is performed only when the column pair passes the all test, ensuring that the DP table is updated minimally. This selective update avoids redundant work for column pairs that cannot contribute to a longer subsequence.

Overall, the combination of a one-dimensional DP structure, short-circuiting checks, and conditional updates yields an implementation that is both memory-efficient and responsive to the actual ordering of characters in the input strings.

Imagine a line of words standing next to each other like children in a parade. Each word has a trail of letters following it. To play this game, we want to look at the letters in a specific column and make sure they are in order from smallest to biggest, like the letters A, B, and C.

First, the code looks at how many columns of letters there are. It starts by assuming that every single column is its own little parade of one.

Then, it starts comparing the columns. It looks at a column on the left and a column on the right. It checks every word to see if the letter in the left column is smaller than or the same as the letter in the right column. If it finds this is true for every word in the list, it means those two columns are a good pair.

As it goes through the columns, it keeps track of how many cool, ordered columns it can link together in a row. It is like trying to build the longest train track possible where every piece fits perfectly. It remembers the longest chain of columns it finds during this hunt.

Finally, it looks at the total number of columns that started the parade and takes away the number of columns that belong to the longest chain. Everything that was left over is what needs to be taken out to keep the parade tidy.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java			Python		TS
	WalkCCC	C++		Java
	leetcode.ca	C++		Java		Go	Python	Rust	TS
	LeetcodeHelp	C++		Java			Python
	Progiez	C++		Java			Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	gouthampradhan			Java
	JoshCrozier		JS
	suxrobGM				C#
	wisdompeak	C++
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
gouthampradhan	Java
JoshCrozier	JavaScript
suxrobGM	C#
wisdompeak	C++
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality