LeetCode: Delete Columns to Make Sorted II

Posted on June 18, 2019July 26, 2020 by braindenny

Delete Columns to Make Sorted II

Similar Problems:

We are given an array A of N lowercase letter strings, all of the same length.

Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.

For example, if we have an array A = [“abcdef”,”uvwxyz”] and deletion indices {0, 2, 3}, then the final array after deletions is [“bef”,”vyz”].

Suppose we chose a set of deletion indices D such that after deletions, the final array has its elements in lexicographic order (A[0] <= A[1] <= A[2] … <= A[A.length – 1]).

Return the minimum possible value of D.length.

Example 1:

Input: ["ca","bb","ac"]
Output: 1
Explanation: 
After deleting the first column, A = ["a", "b", "c"].
Now A is in lexicographic order (ie. A[0] <= A[1] <= A[2]).
We require at least 1 deletion since initially A was not in lexicographic order, so the answer is 1.

Example 2:

Input: ["xc","yb","za"]
Output: 0
Explanation: 
A is already in lexicographic order, so we don't need to delete anything.
Note that the rows of A are not necessarily in lexicographic order:
ie. it is NOT necessarily true that (A[0][0] <= A[0][1] <= ...)

Example 3:

Input: ["zyx","wvu","tsr"]
Output: 3
Explanation: 
We have to delete every column.

Note:

1 <= A.length <= 100
1 <= A[i].length <= 100

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

// https://code.dennyzhang.com/delete-columns-to-make-sorted-ii
// Basic Ideas: greedy
//
//   From left column to the right, decide column by column
//   Interesting test case: ["xga","xfb","yfa"]
//
// Complexity: Time O(n*m), Space O(n)
func minDeletionSize(A []string) int {
    res := 0
    resolved := make([]bool, len(A))
    for i:=0; i<len(A[0]); i++ {
        j:=0;
        for ; j+1<len(A); j++ {
            // skip compare A[j] with A[j+1] for current digit
            if resolved[j] {
                continue
            }
            if A[j][i] > A[j+1][i] {
                break
            }
        }
        // need to delete this column
        if j+1 != len(A) {
            res++
        } else {
           // collect sorted columned
            for j:=0; j+1<len(A); j++ {
                if A[j][i] != A[j+1][i] {
                    resolved[j] = true
                }
            }
        }
    }
    return res
}

Solution:

// https://code.dennyzhang.com/delete-columns-to-make-sorted-ii
// Basic Ideas: greedy
//
//   From left column to the right, decide column by column
//   Interesting test case: ["xga","xfb","yfa"]
//
// Complexity: Time O(n*m), Space O(n)
func minDeletionSize(A []string) int {
    res := 0
    resolved := make([]bool, len(A))
    for i:=0; i<len(A[0]); i++ {
        j:=0;
        hasEqual := false
        l := []int{}
        for ; j+1<len(A); j++ {
            // skip compare A[j] with A[j+1] for current digit
            if resolved[j] {
                continue
            }
            if A[j][i] > A[j+1][i] {
                break
            }
            if A[j][i] == A[j+1][i] {
                hasEqual = true
            } else {
                l = append(l, j)
            }
        }
        // need to delete this column
        if j+1 != len(A) {
            res++
        } else {
           if !hasEqual {
                return res
            }
            for _, index := range l {
                resolved[index] = true
            }
        }
    }
    return res
}

Post Views: 0