944. Delete Columns to Make Sorted

EasyArrayString

Problem Description

The problem presents us with an array strs that contains n strings, and all strings have the same length. We can think of these strings as rows in a grid where each column is made up of characters from the same position in each string.

For example:

abc
bce
cae

If we visualize the strings in this way, our task is to find and remove the columns that are not sorted in ascending lexicographical order. A column is considered sorted if each character is the same or comes before the character in the row below it.

In the given example, the second column contains "b", "c", and "a". Because "b" does not come before "a", this column is not sorted, so it needs to be deleted. The problem asks us to return the count of such columns that need to be removed.

Intuition

The intuition behind the solution is to simulate the column-wise traversal mentioned in the problem description. We need to iterate over each column and check if its elements are in lexicographical order. This can be done by comparing each character in the column with the character above it, starting with the second row and continuing until the bottom of the column.

If, at any point, we find a character that is less than the character in the row above, we can conclude that this column is not sorted. Each such instance implies that we must delete the column to meet the requirement of having all columns sorted.

The challenge is to count the number of columns that violate this sorted order. We use a variable ans to keep track of this count. By iterating through each element in the grid column by column, and checking the required condition with the elements in the rows, we can increment the ans variable when an unsorted instance is detected. Finally, returning ans gives us the total number of columns that would be deleted.

Solution Approach

The implementation of the solution follows a straightforward approach that aligns closely with the intuition previously described. The main algorithmic pattern used here is a nested loop to iterate through the grid columns and rows.

Here's a step-by-step breakdown of the code:

First, determine the dimensions of the grid. The variable m is set to the length of each string, which represents the number of columns. The variable n is the number of strings, which corresponds to the number of rows.
Initialize a counter ans to zero. This counter will keep track of the number of columns to delete.
Set up a loop to iterate column by column over the grid. The outer loop variable j goes from 0 to m-1, representing the index of the current column.
For each column, use another loop to compare each character with the character above it (row by row). The inner loop variable i goes from 1 to n-1, as we start from the second string and compare it with the first one above.
Within the inner loop, compare the character in the current row and column (strs[i][j]) with the character in the previous row and same column (strs[i - 1][j]). If strs[i][j] is found to be smaller, it means the column is not in lexicographical order.
In case an unsorted column is detected, increment the ans by one. Since the column is not sorted, it's marked for deletion, and there's no need to check other characters in the same column. Hence, a break statement terminates the inner loop early.
After both loops complete, return ans, which now contains the count of columns to be deleted.

It's worth noting that no additional data structures are required for this solution, and it operates in-place, using the given strs array as the basis for the comparison. The complexity of this solution is O(m*n), where m is the number of columns, and n is the number of rows since every character in the grid is visited only once during these nested iterations.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use the example given in the problem description to illustrate each step of the solution approach:

Given the strings in array strs:

abc
bce
cae

We analyze the columns to find the ones that are not sorted lexicographically.

We initialize m = 3 (since each string has 3 characters, indicating 3 columns) and n = 3 (since there are 3 strings, indicating 3 rows).
We set ans = 0 as our counter for unsorted columns.
We start the outer loop with j = 0, to begin evaluating the first column ("abb").
The inner loop starts with i = 1, comparing the first character of the second string 'b' with the first character of the first string 'a'. Since 'b' comes after 'a', we continue to i = 2, the third string.
We compare the first character of the third string 'c' with the first character of the second string 'b'. Still in correct order, we complete the inner loop without incrementing ans.
We move to the second column with j = 1. We now check the characters "b", "c", and "a".
Comparing 'c' (second string) with 'b' (first string) is fine. However, when comparing 'a' (third string) with 'c' (second string), we find 'a' comes before 'c' lexicographically, which is not sorted.
As this column is unsorted, we increment ans to 1 and break the inner loop early since there's no need to check further.
We then move to the third column with j = 2, where we have the characters "c","e","e".
As we progress through the column, we find that each character is in the correct order or the same as the one above it ("c" < "e", "e" = "e").
With no increase in ans, we've completed the checks for all columns.

After finishing the loop for all columns, we find that only one column was unsorted. Hence, ans = 1.

Returning ans gives us the total number of columns that would be deleted: 1.

Solution Implementation

1# This class contains a method to find the minimum number of columns that need to be deleted
2# to ensure that each remaining column is in non-decreasing sorted order.
3class Solution:
4    def minDeletionSize(self, strs: List[str]) -> int:
5        # Get the dimensions of the list of strings,
6        # `m` represents the length of the string (number of columns),
7        # `n` represents the number of strings (number of rows).
8        num_columns = len(strs[0])
9        num_rows = len(strs)
10      
11        # Initialize a counter for the number of columns to delete.
12        deletions = 0
13      
14        # Iterate over each column.
15        for col in range(num_columns):
16            # Iterate over each row starting from the second one,
17            # to compare with the previous row.
18            for row in range(1, num_rows):
19                # If the current element is smaller than the previous element in the same column,
20                # this column is not sorted and needs to be deleted.
21                if strs[row][col] < strs[row - 1][col]:
22                    # Increment the deletion counter and exit the inner loop
23                    # as we don't need to check further in this column.
24                    deletions += 1
25                    break
26        # Return the total number of columns that need to be deleted.
27        return deletions
28
29# Note: The placeholder `List` needs to be imported from the typing module for type annotations,
30# if it's not already present at the beginning of the code.
31# Add this line at the beginning of the code if it's missing:
32# from typing import List
33

1class Solution {
2    // Method to find the minimum number of columns to be deleted so that each row is in non-decreasing order
3    public int minDeletionSize(String[] strs) {
4        // m represents the length of the first string, assuming all strings are the same length.
5        int columnLength = strs[0].length();
6        // n represents the number of strings in the array.
7        int rowLength = strs.length;
8        // Initialize the counter for the minimum number of columns to delete.
9        int minDeletions = 0;
10
11        // Iterate over each column
12        for (int columnIndex = 0; columnIndex < columnLength; ++columnIndex) {
13            // Check each row in the current column, starting from the second row
14            for (int rowIndex = 1; rowIndex < rowLength; ++rowIndex) {
15                // Compare the current character with the one in the previous row.
16                if (strs[rowIndex].charAt(columnIndex) < strs[rowIndex - 1].charAt(columnIndex)) {
17                    // If the current character is smaller, increment the count of columns to delete
18                    ++minDeletions;
19                    // No need to check further in this column; break out of the inner loop.
20                    break;
21                }
22            }
23        }
24
25        // Return the count of columns to delete so that all rows are sorted non-decreasingly
26        return minDeletions;
27    }
28}
29

1class Solution {
2public:
3    // Function to find minimum number of columns to delete to make each row lexicographically ordered
4    int minDeletionSize(vector<string>& strs) {
5        int rowCount = strs.size();          // num of rows in the input vector
6        int colCount = strs[0].size();       // num of columns (length of first string)
7        int deleteCount = 0;                 // counter for the number of columns to delete
8
9        // Loop through each column
10        for (int col = 0; col < colCount; ++col) {
11            // Compare elements in the same column of adjacent rows
12            for (int row = 0; row < rowCount - 1; ++row) {
13                // If the current character is greater than the one in the next row, column is unsorted
14                if (strs[row][col] > strs[row + 1][col]) {
15                    deleteCount++;          // Increment the delete counter as this column needs to be deleted
16                    break;                  // No need to check further in this column, move to the next one
17                }
18            }
19        }
20        // Return the number of columns that needs to be deleted
21        return deleteCount;
22    }
23};
24

1// Define the type to represent an array of strings
2type StringsArray = string[];
3
4// Function to find the minimum number of columns to delete to make each row lexicographically ordered
5function minDeletionSize(strs: StringsArray): number {
6    const rowCount: number = strs.length;       // Number of rows in the input array
7    const colCount: number = strs[0].length;    // Number of columns (length of the first string)
8    let deleteCount: number = 0;                // Counter for the number of columns to delete
9
10    // Loop through each column
11    for (let col = 0; col < colCount; ++col) {
12        // Compare elements in the same column of adjacent rows
13        for (let row = 0; row < rowCount - 1; ++row) {
14            // If the current character is greater than the one in the next row, the column is unsorted
15            if (strs[row].charAt(col) > strs[row + 1].charAt(col)) {
16                deleteCount++;                // Increment the delete counter as this column needs to be deleted
17                break;                        // No need to check further in this column, move to the next one
18            }
19        }
20    }
21    // Return the number of columns that need to be deleted
22    return deleteCount;
23}
24

Time and Space Complexity

The given Python code takes in a list of strings (strs) and determines the minimum number of columns that must be deleted such that each remaining column is in non-decreasing sorted order.

Time Complexity

The time complexity of the code is calculated by analyzing the nested loops. The outer loop iterates over each column, of which there are m, where m is the length of each string (the number of columns). The inner loop iterates over the rows for each column, of which there are n-1 comparisons to make (since there are n strings), where n is the number of strings (the number of rows).

Therefore, in the worst case, the code will make m * (n - 1) comparisons, which simplifies to O(m * n). This is the worst-case scenario because the inner loop may terminate early if the current column does not need to be deleted (i.e., it is already sorted).

Space Complexity

The space complexity of the code is O(1) because the algorithm uses a constant amount of extra space. The variables ans, m, and n are simple integer counters regardless of the input size. There is no additional data structure that grows with the input size, meaning that the space needed does not scale with the size of the input (strs).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don't know