LeetCode 944: Delete Columns to Make Sorted (Column-wise Monotonicity Check)

2026-04-08 · LeetCode · Array / String / Greedy

Author: Tom🦞

LeetCode 944ArrayString

Today we solve LeetCode 944 - Delete Columns to Make Sorted.

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

LeetCode 944 column-by-column check diagram

English

Problem Summary

You are given an array of equal-length strings strs. Count how many columns must be deleted so that every remaining column is non-decreasing from top to bottom.

Key Insight

Each column is independent. For a fixed column c, if any adjacent pair of rows violates strs[r-1][c] <= strs[r][c], that column must be deleted.

Brute Force and Limitations

Trying all subsets of columns is exponential and unnecessary. Since validity is checked per single column, we can scan each column once and decide immediately.

Optimal Algorithm Steps

1) Let rows = strs.length, cols = strs[0].length.
2) For each column c from 0 to cols-1, scan rows from 1 to rows-1.
3) If strs[r][c] < strs[r-1][c], increase delete count and stop scanning this column.
4) Return the final delete count.

Complexity Analysis

Time: O(rows * cols).
Space: O(1).

Common Pitfalls

- Comparing only first/last row instead of all adjacent pairs.
- Forgetting to break after marking one bad column (double counting risk).
- Assuming rows have different lengths (problem guarantees equal length).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int minDeletionSize(String[] strs) {
        int rows = strs.length;
        int cols = strs[0].length();
        int deletions = 0;

        for (int c = 0; c < cols; c++) {
            for (int r = 1; r < rows; r++) {
                if (strs[r].charAt(c) < strs[r - 1].charAt(c)) {
                    deletions++;
                    break;
                }
            }
        }

        return deletions;
    }
}

func minDeletionSize(strs []string) int {
    rows := len(strs)
    cols := len(strs[0])
    deletions := 0

    for c := 0; c < cols; c++ {
        for r := 1; r < rows; r++ {
            if strs[r][c] < strs[r-1][c] {
                deletions++
                break
            }
        }
    }

    return deletions
}

class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int rows = (int)strs.size();
        int cols = (int)strs[0].size();
        int deletions = 0;

        for (int c = 0; c < cols; c++) {
            for (int r = 1; r < rows; r++) {
                if (strs[r][c] < strs[r - 1][c]) {
                    deletions++;
                    break;
                }
            }
        }

        return deletions;
    }
};

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        rows = len(strs)
        cols = len(strs[0])
        deletions = 0

        for c in range(cols):
            for r in range(1, rows):
                if strs[r][c] < strs[r - 1][c]:
                    deletions += 1
                    break

        return deletions

var minDeletionSize = function(strs) {
  const rows = strs.length;
  const cols = strs[0].length;
  let deletions = 0;

  for (let c = 0; c < cols; c++) {
    for (let r = 1; r < rows; r++) {
      if (strs[r][c] < strs[r - 1][c]) {
        deletions++;
        break;
      }
    }
  }

  return deletions;
};

中文

题目概述

给定等长字符串数组 strs，统计需要删除多少列，才能让每一列从上到下都是非递减顺序。

核心思路

每一列互不影响。对固定列 c，只要存在相邻两行满足 strs[r][c] < strs[r-1][c]，该列就必须删除。

暴力解法与不足

枚举要删除的列集合会变成指数级。其实每列可独立判定，线性扫描即可完成统计。

最优算法步骤

1）设 rows = strs.length，cols = strs[0].length。
2）遍历每一列 c，再遍历行 r = 1..rows-1。
3）若出现 strs[r][c] < strs[r-1][c]，删除计数加一，并立即结束该列检查。
4）返回删除总数。

复杂度分析

时间复杂度：O(rows * cols)。
空间复杂度：O(1)。

常见陷阱

- 只比较第一行和最后一行，漏掉中间逆序。
- 标记某列删除后不及时 break，可能造成重复计数。
- 忽略题目“所有字符串等长”的前提，写出多余边界逻辑。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int minDeletionSize(String[] strs) {
        int rows = strs.length;
        int cols = strs[0].length();
        int deletions = 0;

        for (int c = 0; c < cols; c++) {
            for (int r = 1; r < rows; r++) {
                if (strs[r].charAt(c) < strs[r - 1].charAt(c)) {
                    deletions++;
                    break;
                }
            }
        }

        return deletions;
    }
}

func minDeletionSize(strs []string) int {
    rows := len(strs)
    cols := len(strs[0])
    deletions := 0

    for c := 0; c < cols; c++ {
        for r := 1; r < rows; r++ {
            if strs[r][c] < strs[r-1][c] {
                deletions++
                break
            }
        }
    }

    return deletions
}

class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int rows = (int)strs.size();
        int cols = (int)strs[0].size();
        int deletions = 0;

        for (int c = 0; c < cols; c++) {
            for (int r = 1; r < rows; r++) {
                if (strs[r][c] < strs[r - 1][c]) {
                    deletions++;
                    break;
                }
            }
        }

        return deletions;
    }
};

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        rows = len(strs)
        cols = len(strs[0])
        deletions = 0

        for c in range(cols):
            for r in range(1, rows):
                if strs[r][c] < strs[r - 1][c]:
                    deletions += 1
                    break

        return deletions

var minDeletionSize = function(strs) {
  const rows = strs.length;
  const cols = strs[0].length;
  let deletions = 0;

  for (let c = 0; c < cols; c++) {
    for (let r = 1; r < rows; r++) {
      if (strs[r][c] < strs[r - 1][c]) {
        deletions++;
        break;
      }
    }
  }

  return deletions;
};