Scale Engineer

Delete Columns to Make Sorted

Easy
#0898Time: O(m * n log n), where `n` is the number of strings and `m` is the length of each string. For each of the `m` columns, we create an array of size `n` and sort it, which takes O(n log n) time.Space: O(n). For each column, we create a temporary character array of size `n` to hold the column's characters.1 company
Data structures
ArrayString
Companies
Garmin

Prompt

You are given an array of n strings strs, all of the same length.

The strings can be arranged such that there is one on each line, making a grid.

  • For example, strs = ["abc", "bce", "cae"] can be arranged as follows:
abc
bce
cae

You want to delete the columns that are not sorted lexicographically. In the above example (0-indexed), columns 0 ('a', 'b', 'c') and 2 ('c', 'e', 'e') are sorted, while column 1 ('b', 'c', 'a') is not, so you would delete column 1.

Return the number of columns that you will delete.

 

Example 1:

Input: strs = ["cba","daf","ghi"]
Output: 1
Explanation: The grid looks as follows:
  cba
  daf
  ghi
Columns 0 and 2 are sorted, but column 1 is not, so you only need to delete 1 column.

Example 2:

Input: strs = ["a","b"]
Output: 0
Explanation: The grid looks as follows:
  a
  b
Column 0 is the only column and is sorted, so you will not delete any columns.

Example 3:

Input: strs = ["zyx","wvu","tsr"]
Output: 3
Explanation: The grid looks as follows:
  zyx
  wvu
  tsr
All 3 columns are not sorted, so you will delete all 3.

 

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through each column of the grid. For each column, we extract all its characters into a separate array. Then, we create a sorted version of this character array. By comparing the original character array with its sorted version, we can determine if the column was already sorted. If not, we increment a counter for the columns to be deleted.

Algorithm

  • Get the number of rows n = strs.length and columns m = strs[0].length.
  • Initialize a counter deleteCount = 0.
  • Loop through each column index j from 0 to m-1.
  • For each column j, create a temporary character array columnChars of size n.
  • Populate columnChars by iterating from i = 0 to n-1 and setting columnChars[i] = strs[i].charAt(j).
  • Create a copy of columnChars, let's call it sortedColumnChars.
  • Sort sortedColumnChars lexicographically.
  • Compare columnChars and sortedColumnChars. If they are not identical, it means the original column was not sorted.
  • If the column was not sorted, increment deleteCount.
  • After checking all columns, return deleteCount.

Walkthrough

This method checks each column for sorted order by explicitly creating and sorting a representation of that column.

  • Get the number of rows n = strs.length and columns m = strs[0].length.
  • Initialize a counter deleteCount = 0.
  • Loop through each column index j from 0 to m-1.
  • For each column j, create a temporary character array columnChars of size n.
  • Populate columnChars by iterating from i = 0 to n-1 and setting columnChars[i] = strs[i].charAt(j).
  • Create a copy of columnChars, let's call it sortedColumnChars.
  • Sort sortedColumnChars lexicographically.
  • Compare columnChars and sortedColumnChars. If they are not identical, it means the original column was not sorted.
  • If the column was not sorted, increment deleteCount.
  • After checking all columns, return deleteCount.
import java.util.Arrays; class Solution {    public int minDeletionSize(String[] strs) {        if (strs == null || strs.length == 0) {            return 0;        }        int numRows = strs.length;        int numCols = strs[0].length();        int deleteCount = 0;         for (int j = 0; j < numCols; j++) {            char[] columnChars = new char[numRows];            for (int i = 0; i < numRows; i++) {                columnChars[i] = strs[i].charAt(j);            }             char[] sortedColumnChars = Arrays.copyOf(columnChars, numRows);            Arrays.sort(sortedColumnChars);             if (!Arrays.equals(columnChars, sortedColumnChars)) {                deleteCount++;            }        }        return deleteCount;    }}

Complexity

Time

O(m * n log n), where `n` is the number of strings and `m` is the length of each string. For each of the `m` columns, we create an array of size `n` and sort it, which takes O(n log n) time.

Space

O(n). For each column, we create a temporary character array of size `n` to hold the column's characters.

Trade-offs

Pros

  • Conceptually simple and easy to understand.

  • Clearly separates the logic for checking each column.

Cons

  • Less efficient in terms of both time and space compared to the optimal approach.

  • The sorting step for each column is computationally more expensive than a simple linear scan.

Solutions

class Solution {public  int minDeletionSize(String[] strs) {    int m = strs[0].length(), n = strs.length;    int ans = 0;    for (int j = 0; j < m; ++j) {      for (int i = 1; i < n; ++i) {        if (strs[i].charAt(j) < strs[i - 1].charAt(j)) {          ++ans;          break;        }      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem