Delete Columns to make Sorted in Java
The Delete Columns to Make Sorted problem is a computational challenge that involves processing a two-dimensional array of strings to determine the minimum number of columns needed to make the grid lexicographically sorted. The input consists of an array of strings representing a row in a grid. The goal is to identify non-sorted columns and determine the minimum count of deletions.
Example 1:
Input: strs = ["cba", "daf", "ghi"]
Output: 1
Explanation:
The grid looks like:
cba
daf
ghi
We only need to remove one column because columns 0 and 2 are sorted while column 1 is not.
Example 2:
Input: strs = ["a", "b"]
Output: 0
Explanation:
The grid looks like:
a
b
Column 0 is the only column, and it is sorted in the manner "ab." Thus, there's no need to remove any columns.
Using Naive Approach
The naive approach is a method to find the minimum number of deletions needed to make a grid lexicographically sorted. It involves initializing `rows` and `columns` to the number of rows and columns and initializing `deletedColumns` to 0. The program then iterates through each column and row, comparing adjacent characters in the same column. If a non-sorted column is found, the counter is incremented, and the loop for that column is exited. The final result is the total number of deleted columns needed to achieve a sorted grid.
Here's an implementation of deleting columns to make it sorted using a naive approach:
FileName: NaiveApproach.java
public class NaiveApproach
{
// Method to calculate the minimum number of deletions
public static int minDeletionSize(String[] strs) {
int rows = strs.length; // Number of rows in the grid
int columns = strs[0].length();
int deletedColumns = 0;
for (int col = 0; col < columns; col++) {
for (int row = 1; row < rows; row++) {
// Check if the character in the current column is less than the character in the previous row's same column
if (strs[row].charAt(col) < strs[row - 1].charAt(col)) {
deletedColumns++; // Increment the counter if the column is not sorted
break; // Move to the next column once a non-sorted column is found in any row
}
}
}
return deletedColumns; }
public static void main(String[] args) {
// Example input
String[] strs = {"cba", "daf", "ghi"};
System.out.println(minDeletionSize(strs));
}
}
Output:
1
Complexity analysis: The Naive Approach has a time complexity of O(rows * columns) due to two nested loops and a space complexity of O(1) due to constant space usage. The time complexity is dominated by nested loops iterating through each grid element, while the space complexity remains constant.
Using Optimized Approach
The optimized approach aims to determine the minimum number of deletions needed to sort columns in a grid lexicographically. It involves initializing `rows` and `columns` to the number of rows and columns and initializing `deletedColumns` to 0. The program then iterates through each column and row, comparing adjacent characters in the same column. If a non-sorted column is found, the counter is incremented, and the loop for that column is exited. The final result is the total number of deleted columns needed to achieve a sorted grid.
Here's an implementation of deleting columns to make them sorted using an optimized approach:
FileName: OptimizedApproach.java
public class OptimizedApproach {
// Method to calculate the minimum number of deletions
public static int minDeletionSize(String[] strs) {
int rows = strs.length;
int columns = strs[0].length();
int deletedColumns = 0;
for (int col = 0; col < columns; col++) {
for (int row = 1; row < rows; row++) {
// Check if the character in the current column is less than the character in the previous row's same column
if (strs[row].charAt(col) < strs[row - 1].charAt(col)) {
deletedColumns++; // Increment the counter if the column is not sorted
break; // Move to the next column once a non-sorted column is found in any row
}
}
}
return deletedColumns; // Return the total number of deleted columns
}
public static void main(String[] args) {
String[] strs = {"cba", "daf", "ghi"};
System.out.println(minDeletionSize(strs));
}
}
Output:
1
Complexity analysis: The optimized approach has a time complexity of O(rows * columns) due to two nested loops iterating through each row and column. The space complexity is O(1), as the approach uses a constant amount of space irrespective of the input size, as only a few variables are used. Which means nested loops dominate the time complexity while the space complexity remains constant.