Problem

You are given an N by M 2D matrix of lowercase letters. Determine the minimum number of columns that can be removed to ensure that each row is ordered from top to bottom lexicographically. That is, the letter at each column is lexicographically later as you go down each row. It does not matter whether each row itself is ordered lexicographically.

For example, given the following table:

1
2
3

cba
daf
ghi

This is not ordered because of the a in the center. We can remove the second column to make it ordered:

1
2
3

ca
df
gi

So your function should return 1, since we only needed to remove 1 column.

As another example, given the following table:

1

abcdef

Your function should return 0, since the rows are already ordered (there’s only one row).

As another example, given the following table:

1
2
3

zyx
wvu
tsr

Your function should return 3, since we would need to remove all the columns to order it.

Examples

Solution

Method 1 - Iteration

Plan

  1. We will iterate through each column of the matrix.
  2. For each column, we will check if the column is sorted lexicographically.
  3. If a column is not sorted, we will mark it for removal.
  4. At the end, we will return the number of columns marked for removal.

Implementation

  1. Initialization:
    • We will initialize a counter count to keep track of the number of columns to be removed.
  2. Iterate through each column:
    • For each column, starting from the top row, check if the current element is lexicographically greater than or equal to the element in the previous row.
    • If we find any element which is smaller than the previous row’s element in the same column, we increment our counter and mark this column for removal.
  3. Return the result:
    • Finally, return the count of columns that are not lexicographically sorted.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public class MinimumColumnsToRemove {
    public static int minColumnsToRemove(char[][] matrix) {
        int rows = matrix.length;
        if (rows == 0)
            return 0;
        int cols = matrix[0].length;

        int count = 0;

        // Iterating through each column
        for (int col = 0; col < cols; col++) {
            for (int row = 1; row < rows; row++) {
                // Check if the current element is smaller than the element in
                // the previous row
                if (matrix[row][col] < matrix[row - 1][col]) {
                    count++;
                    break; // No need to check further rows; mark this column
                           // for removal
                }
            }
        }

        return count;
    }

    public static void main(String[] args) {
        char[][] matrix1 = {{'c', 'b', 'a'}, {'d', 'a', 'f'}, {'g', 'h', 'i'}};
        System.out.println(minColumnsToRemove(matrix1)); // Output: 1

        char[][] matrix2 = {{'a', 'b', 'c', 'd', 'e', 'f'}};
        System.out.println(minColumnsToRemove(matrix2)); // Output: 0

        char[][] matrix3 = {{'z', 'y', 'x'}, {'w', 'v', 'u'}, {'t', 's', 'r'}};
        System.out.println(minColumnsToRemove(matrix3)); // Output: 3
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

def min_columns_to_remove(matrix):
    if not matrix:
        return 0

    rows = len(matrix)
    cols = len(matrix[0])

    count = 0

    # Iterate through each column
    for col in range(cols):
        for row in range(1, rows):
            # Check if the current element is smaller than the element in the previous row
            if matrix[row][col] < matrix[row - 1][col]:
                count += 1
                break  # No need to check further rows for this column

    return count


# Example usage
matrix1 =[["c", "b", "a"], ["d", "a", "f"], ["g", "h", "i"]]
print(min_columns_to_remove(matrix1))  # Output: 1

matrix2 =[["a", "b", "c", "d", "e", "f"]]
print(min_columns_to_remove(matrix2))  # Output: 0

matrix3 =[["z", "y", "x"], ["w", "v", "u"], ["t", "s", "r"]]
print(min_columns_to_remove(matrix3))  # Output: 3

Complexity

  • ⏰ Time complexity: O(m*n) where m is number of rows and n is number of columns
  • 🧺 Space complexity: O(1)