960. Delete Columns to Make Sorted III LeetCode Solution

Last updated: February 21, 2025

In this guide, you will get 960. Delete Columns to Make Sorted III LeetCode Solution with the best time and space complexity. The solution to Delete Columns to Make Sorted III 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.

Problem Statement
Complexity Analysis
Delete Columns to Make Sorted III solution in C++
Delete Columns to Make Sorted III solution in Java
Delete Columns to Make Sorted III solution in Python
Additional Resources

960. Delete Columns to Make Sorted III LeetCode Solution image

Problem Statement of Delete Columns to Make Sorted III

You are given an array of n strings strs, all of the same length.
We may choose any deletion indices, and we delete all the characters in those indices for each string.
For example, if we have strs = [“abcdef”,”uvwxyz”] and deletion indices {0, 2, 3}, then the final array after deletions is [“bef”, “vyz”].
Suppose we chose a set of deletion indices answer such that after deletions, the final array has every string (row) in lexicographic order. (i.e., (strs[0][0] <= strs[0][1] <= … <= strs[0][strs[0].length – 1]), and (strs[1][0] <= strs[1][1] <= … <= strs[1][strs[1].length – 1]), and so on). Return the minimum possible value of answer.length.

Example 1:

Input: strs = [“babca”,”bbazb”]
Output: 3
Explanation: After deleting columns 0, 1, and 4, the final array is strs = [“bc”, “az”].
Both these rows are individually in lexicographic order (ie. strs[0][0] <= strs[0][1] and strs[1][0] strs[1] – the array strs is not necessarily in lexicographic order.
Example 2:

Input: strs = [“edcba”]
Output: 4
Explanation: If we delete less than 4 columns, the only row will not be lexicographically sorted.

Example 3:

Input: strs = [“ghi”,”def”,”abc”]
Output: 0
Explanation: All rows are already lexicographically sorted.

Constraints:

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

Complexity Analysis

Time Complexity: O(k^2 \cdot n), where k = |\texttt{A[0]}|
Space Complexity: O(k)

960. Delete Columns to Make Sorted III LeetCode Solution in C++

class Solution {
 public:
  int minDeletionSize(vector<string>& strs) {
    const int k = strs[0].length();
    // dp[i] the length of LIS ending in strs[*][i]
    vector<int> dp(k, 1);

    for (int i = 1; i < k; ++i)
      for (int j = 0; j < i; ++j)
        if (ranges::all_of(strs, [&](const string& s) { return s[j] <= s[i]; }))
          dp[i] = max(dp[i], dp[j] + 1);

    return k - ranges::max(dp);
  }
};
/* code provided by PROGIEZ */

960. Delete Columns to Make Sorted III LeetCode Solution in Java

class Solution {
  public int minDeletionSize(String[] strs) {
    final int k = strs[0].length();
    // dp[i] the length of LIS ending in strs[*][i]
    int[] dp = new int[k];
    Arrays.fill(dp, 1);

    for (int i = 1; i < k; ++i)
      for (int j = 0; j < i; ++j)
        if (isSorted(strs, j, i))
          dp[i] = Math.max(dp[i], dp[j] + 1);

    return k - Arrays.stream(dp).max().getAsInt();
  }

  private boolean isSorted(String[] strs, int j, int i) {
    for (final String s : strs)
      if (s.charAt(j) > s.charAt(i))
        return false;
    return true;
  }
}
// code provided by PROGIEZ

960. Delete Columns to Make Sorted III LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

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

Table of Contents