Leetcode – Delete Columns to Make Sorted Solution in Python

Spread the love

In this detailed article, we’ll dismantle the Delete Columns to Make Sorted problem, explore the approach, and finalize with a Python solution.

Problem Statement

Given an array A of N lowercase letter strings, all of the same length, you need to delete the minimum number of columns to make A sorted. Return the number of columns that you will delete.

Note: A column is sorted if the sequence of letters in that column is sorted in ascending order (from top to bottom).

Problem Breakdown

We can envision this problem by picturing each string in the array A as a row and each character position as a column. The task is to ensure that every column is sorted. If a column isn’t sorted, it should be deleted. The challenge is to determine how many such columns exist.

Key Insight

The problem becomes simpler when you realize that you don’t need to actually delete the columns. Instead, you only need to count how many columns are not in ascending order.

Algorithm to Solve the Problem

  1. Set a counter deleteCount to zero.
  2. For each position j from 0 to the length of a string in A:
    • For each string i from 1 to the length of A:
      • If A[i][j] is smaller than A[i-1][j], then:
        • The column isn’t sorted.
        • Increment deleteCount.
        • Break out of the loop for that column and move to the next column.
  3. Return deleteCount.

Python Code Solution

Here’s how you can implement the solution in Python:

def minDeletionSize(A):
    deleteCount = 0
    for j in range(len(A[0])):
        for i in range(1, len(A)):
            if A[i][j] < A[i-1][j]:
                deleteCount += 1
                break
    return deleteCount

Complexity Analysis

  • Time Complexity: O(M x N) – Where M is the length of a string in A and N is the number of strings in A. This is because, for each column (M times), we might have to traverse through all rows (N times).
  • Space Complexity: O(1) – The solution doesn’t use any additional space that scales with the input.

Testing the Solution

Testing is essential to ensure that the solution works for all edge cases:

print(minDeletionSize(["cba", "daf", "ghi"]))  # Expected output: 1 (because column 1 ['b', 'a', 'h'] is not sorted)
print(minDeletionSize(["a", "b"]))            # Expected output: 0 (Single character strings are already sorted)
print(minDeletionSize(["zyx", "wvu", "tsr"])) # Expected output: 3 (All columns are not sorted)

Conclusion

The “Delete Columns to Make Sorted” problem exemplifies how a seemingly intricate task can boil down to a basic traversal and comparison operation. Many problems on platforms like Leetcode are structured to encourage thinking from different angles and to break a problem down to its core elements. The underlying lesson here is the importance of visualization and the understanding that sometimes direct manipulation (like actually deleting columns) isn’t necessary. Instead, a concise and efficient evaluation (like counting unsorted columns) suffices.

Leave a Reply