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