944. Delete Columns to Make Sorted

EasyView on LeetCode

Array String Greedy

Time: O(n·m)

Space: O(1)

Problem Overview

Each column must be non-decreasing top to bottom (lexicographically sorted as strings).

Intuition

Each column must be non-decreasing top to bottom (lexicographically sorted as strings). If any column has a character above a smaller character in the next row, delete that entire column. Count how many columns fail this check.

Algorithm

1For each column index j from 0 to max width - 1:
2Scan rows i from 0 to n-2: if strs[i][j] > strs[i+1][j], increment delete count and break inner loop.
3Return total columns marked for deletion.

Example Walkthrough

Input: strs = ["cba","daf","ghi"]

1.Column 0: c>d — delete. Column 1: a<a? a<f OK. Column 2: b<i OK.
2.Only column 0 is unsorted.

Output: 1

Common Pitfalls

•Delete whole columns, not individual cells.
•Rows may differ in length — problem usually pads or uses same width.
•O(n * m) scan is sufficient.

944.cs

// Approach: Count columns where any adjacent row pair is out of lexicographic order.
// Time: O(n·m) Space: O(1)

public class Solution
{
    public int MinDeletionSize(string[] strs)
    {
        int columnCount = strs[0].Length;
        int rowCount = strs.Length;
        int deletionCount = 0;

        for (int columnIndex = 0; columnIndex < columnCount; columnIndex++)
        {
            for (int rowIndex = 1; rowIndex < rowCount; rowIndex++)
            {
                if (strs[rowIndex][columnIndex] < strs[rowIndex - 1][columnIndex])
                {
                    deletionCount++;
                    break;
                }
            }
        }

        return deletionCount;
    }
}

Was this solution helpful?