Delete Columns to Make Sorted — Easy Problem & Solution

Problem statement

You are given n strings strs, all of the same length. Stack them as the rows of a grid, so column j reads strs[0][j], strs[1][j], …, strs[n-1][j] from top to bottom.

A column is fine when its letters are in non-decreasing alphabetical order from top to bottom. Return the number of columns that are not fine — the columns you would have to delete.

Example 1

Input: strs = ["cba","daf","ghi"]
Output: 1
Explanation: Column 1 reads `b, a, h`, which is out of order; columns 0 and 2 are fine.

Example 2

Input: strs = ["code"]
Output: 0
Explanation: A single row is always sorted.

Example 3

Input: strs = ["zyx","wvu","tsr"]
Output: 3

Constraints

• n == strs.length
• 1 <= n <= 100
• 1 <= strs[i].length <= 1000
• strs[i] consists of lowercase English letters

How to solve Delete Columns to Make Sorted

Columns are independent: a column must be deleted exactly when some adjacent pair in it is out of order.

Approach

1. For each column j, scan rows i = 0 .. n - 2.
2. If strs[i][j] > strs[i + 1][j] for any i, count the column and move on.
3. Return the count.

Why it works

A sequence is non-decreasing exactly when every adjacent pair is, so checking neighbours decides each column, and deleting a column never affects whether another column is sorted.

Complexity

• Time — O(n · m)
• Space — O(1)

Pitfalls

• Equal letters are allowed — only a strict decrease breaks a column.
• Stop scanning a column at its first violation so it is counted once.
• Loop over columns in the outer loop; the strings are rows.

Reference solution

Python

from typing import List

def minDeletionSize(strs: List[str]) -> int:
    count = 0
    for j in range(len(strs[0])):
        for i in range(len(strs) - 1):
            if strs[i][j] > strs[i + 1][j]:
                count += 1
                break
    return count

JavaScript

var minDeletionSize = function(strs) {
    var count = 0;
    for (var j = 0; j < strs[0].length; j++) {
        for (var i = 0; i + 1 < strs.length; i++) {
            if (strs[i][j] > strs[i + 1][j]) { count++; break; }
        }
    }
    return count;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Available Captures for Rook Easy
• Maximize Sum Of Array After K Negations Easy
• Nearest Smaller Element Easy
• Minimum Positive Sum Subarray Easy
• Find X-Sum of All K-Long Subarrays I Easy
• Valid Boomerang Easy