Delete Columns to Make Sorted

EASY

Description

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

Checkout 2 different approaches to solve Delete Columns to Make Sorted. Click on different approaches to view the approach and algorithm in detail.

Column-by-Column Sorting and Comparison

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.

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 Analysis

Time Complexity: 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 Complexity: O(n). For each column, we create a temporary character array of size `n` to hold the column's characters.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Delete Columns to Make Sorted. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Delete Columns to Make Sorted

Data Structures:

ArrayString

Companies:

Garmin |