arcbjorn

thoughtbook

RSS Feed

Tuesday, December 27, 2022

Delete columns to make sorted

Leetcode 944 problem.

A function to delete the columns that are not sorted lexicographically in a grid of words with n length.

Go

  • Time complexity: O(nw)O(n*w) - n is a number of letter columns, w is a number of words
  • Auxiliary space: O(1)O(1) - constant amount of space
func minDeletionSize(strs []string) int {
    if len(strs) <= 1 {
        return 0
    }

    var deletedCols int
    for i := range strs[0] {
        fmt.Println(i)
        for wordsIdx := 0; wordsIdx < len(strs)-1; wordsIdx++ {
            if strs[wordsIdx][i] > strs[wordsIdx+1][i] {
                deletedCols++
                break
            }
        }
    }

    return deletedCols
}
Creative Commons Licence