Vultr DocsLatest Content

Delete Columns to Make Sorted

Updated on 19 May, 2025
Delete Columns to Make Sorted header image

Problem Statement

In this programming challenge, you are given an array strs containing n strings. All strings in this array have the same length, thereby allowing them to be arranged vertically to form a grid. Each string represents a row in the grid, and each character position across the strings represents a column.

The objective is to identify columns that are not sorted in lexicographical order and count how many such columns exist. A column is considered sorted if the characters from the top to the bottom follow the dictionary order. Your task is to return the number of columns that will be deleted because they are not sorted.

For instance, given strs = ["abc", "bce", "cae"], you would analyze it as follows:

abc
bce
cae

Here, only the middle column is out of order ('b' appears before 'a'). Thus, this column would be identified for deletion, and the return value would be 1.

Examples

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.

Approach and Intuition

To solve this problem efficiently, you can apply the following approach:

  1. Determine the number of rows n and the length of each string (number of columns).
  2. Traversing each column, you start from the top row and compare each character with the one directly below it.
  3. If, at any point, a character is found that is greater than the one below it, this indicates that the column is not sorted lexicographically.
  4. A collection or indicator can be maintained to keep track of whether each column is sorted or not.
  5. After evaluating each column, count and return how many columns were marked as not sorted.

Here’s a closer look at how to interpret the provided examples under the constraints of the problem:

  • Example 1:

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

    Forming the grid:

    cba
daf
ghi

    Analysis shows only column 1 is unsorted ('b', 'a', 'h'), so the function returns 1.

  • Example 2:

    strs = ["a","b"]

    Forming the grid:

    a
b

    The single column is already sorted, hence the function returns 0.

  • Example 3:

    strs = ["zyx","wvu","tsr"]

    Forming the grid:

    zyx
wvu
tsr

    All columns are unsorted, thus the function returns 3.

Through this method, you ensure that each column is processed once, making the approach efficient and straightforward, keeping in line with the provided constraints.

Solutions

  • C++
  • Java
cpp 
class Solution {
public:
    int minimumDeletions(vector<string>& arr) {
        int strLen = arr[0].size();  // length of the strings
        int numToDelete = 0;         // number of columns to delete

        // Loop through each column
        for (int i = 0; i < strLen; i++) {
            // Check the order of characters in the current column
            for (int j = 1; j < arr.size(); j++) {
                // If the characters are not in non-decreasing order, count the column for deletion
                if (arr[j][i] < arr[j - 1][i]) {
                    numToDelete++;
                    break;
                }
            }
        }
        
        return numToDelete;  // Return the count of columns that need to be deleted
    }
};

The provided C++ code defines a solution to find the minimum number of columns that must be deleted from a 2D grid of characters to ensure that each column is sorted in non-decreasing order. This solution is encapsulated in a class named Solution with a method minimumDeletions.

  • The method takes a single parameter, arr, which is a vector of strings, where each string represents a row in the grid, and each character in the string represents an element in the column.

  • The function initializes two variables:

    • strLen to store the length of the strings (assuming uniform length across all strings)
    • numToDelete to count the number of columns that need deletion to maintain the sorting order.

  • The outer loop iterates over each column index from 0 to strLen-1.

  • Within this loop, another loop checks each row from the second one onwards, comparing the character at the current column (i) of the current row (j) with the character of the same column in the previous row (j-1).

  • If a character in the current row is found to be smaller than the character in the previous row, this indicates that the column is not sorted. Consequently, this column is marked for deletion by incrementing numToDelete and breaking out of the inner loop to avoid unnecessary comparisons.

  • Ultimately, the method returns numToDelete, which provides the total number of columns required to be deleted to ensure that all columns are sorted in non-decreasing order.

This solution efficiently addresses the problem by checking each column individually and using a breaking condition to minimize comparisons once an unsorted column is identified, resulting in a potentially faster execution for large datasets.

java 
class Solution {
    public int countDeletionColumns(String[] array) {
        int lengthOfStr = array[0].length();
        int deletionsNeeded = 0;
        for (int index = 0; index < lengthOfStr; index++) {
            for (int i = 1; i < array.length; i++) {
                if (array[i].charAt(index) < array[i - 1].charAt(index)) {
                    deletionsNeeded++;
                    break;
                }
            }
        }
        return deletionsNeeded;
    }
}

This solution addresses the problem of deleting columns from an array of strings in order to make the rows sorted in lexicographical order, implemented in Java.

The method countDeletionColumns(String[] array) calculates the minimum number of columns that need to be deleted. It starts by determining the length of the strings (assuming uniform length across all strings). It initializes a counter deletionsNeeded to keep track of the number of columns that must be deleted.

The solution employs two nested loops:

  • The outer loop iterates over each column index of the strings.
  • The inner loop compares characters at the current column index for each consecutive pair of strings in the array.

If a character in a string is found to be less than the character in the same column but in the preceding string, it indicates the column is not sorted. This triggers an increment in deletionsNeeded, and the inner loop breaks to check the next column.

After examining all columns, the function returns the count of deletions needed to make each row lexicographically sorted by columns. This method offers a straightforward approach to identifying non-sorted columns in a two-dimensional array representation of strings.

Comments

No comments yet.