# 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.