944. Delete Columns to Make Sorted LeetCode Solution

In this guide, you will get 944. Delete Columns to Make Sorted LeetCode Solution with the best time and space complexity. The solution to Delete Columns to Make Sorted problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Delete Columns to Make Sorted solution in C++
  4. Delete Columns to Make Sorted solution in Java
  5. Delete Columns to Make Sorted solution in Python
  6. Additional Resources
944. Delete Columns to Make Sorted LeetCode Solution image

Problem Statement of Delete Columns to Make Sorted

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.

See also  501. Find Mode in Binary Search Tree LeetCode Solution

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.

Complexity Analysis

  • Time Complexity: O(|\texttt{strs[0]}| \cdot n)
  • Space Complexity: O(1)

944. Delete Columns to Make Sorted LeetCode Solution in C++

class Solution {
 public:
  int minDeletionSize(vector<string>& strs) {
    int ans = 0;

    for (int j = 0; j < strs[0].length(); ++j)
      for (int i = 0; i + 1 < strs.size(); ++i)
        if (strs[i][j] > strs[i + 1][j]) {
          ++ans;
          break;
        }

    return ans;
  }
};
/* code provided by PROGIEZ */

944. Delete Columns to Make Sorted LeetCode Solution in Java

class Solution {
  public int minDeletionSize(String[] strs) {
    int ans = 0;

    for (int j = 0; j < strs[0].length(); ++j)
      for (int i = 0; i + 1 < strs.length; ++i)
        if (strs[i].charAt(j) > strs[i + 1].charAt(j)) {
          ++ans;
          break;
        }

    return ans;
  }
}
// code provided by PROGIEZ

944. Delete Columns to Make Sorted LeetCode Solution in Python

class Solution:
  def minDeletionSize(self, strs: list[str]) -> int:
    ans = 0

    for j in range(len(strs[0])):
      for i in range(len(strs) - 1):
        if strs[i][j] > strs[i + 1][j]:
          ans += 1
          break

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: