Delete Columns to Make Sorted – Java Solution

Problem Description

So, you’ve got a list of strings, and you want to make sure that when you look at them column by column, they’re all sorted in non-decreasing order. Sounds simple, right? Well, it’s like trying to organize your sock drawer—sure, you can just throw everything in there, but then you’ll have a mess on your hands!

Imagine you’re at a party, and everyone is dancing. You want to make sure that the people in the front row are taller than those behind them. If someone in the front row is shorter, you have to kick them out (or in this case, delete that column).

In LeetCode terms, the problem is called “Delete Columns to Make Sorted.” You need to figure out how many columns you need to delete to achieve that sweet, sweet order.

Code Solution


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;
  }
}

Approach

The approach here is straightforward: we loop through each column of the strings and check if the characters in that column are sorted. If we find a character that breaks the order, we increment our deletion count and move on to the next column. It’s like checking each sock for holes—if you find one, toss it and keep going!

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N * M), where N is the number of strings and M is the length of the strings.
Space Complexity	O(1), since we are using a constant amount of space for our answer.

Real-World Example

Think of it like organizing a bookshelf. You want all the books sorted by height. If you find a tall book in the middle of a row of short books, you have to either move it or remove it to maintain that order. Similarly, in our problem, we’re removing columns that disrupt the sorted order of our strings.