Golang O(n log n) without HashMap


  • 0
    L
    func leastBricks(wall [][]int) int {
        if wall == nil || len(wall) == 0 {
            return 0
        }
        
        // freeAt is a set of x-cordinate where we could break through
        freeAt, n, height := make([]int, 20000), 0, len(wall)
        
        var width, j int
        for _, v := range wall {
            for width, j = 0, 0; j + 1 < len(v); j++ {
                if width += v[j]; v[j] > 0 {
                    freeAt[n] = width
                    n++
                }
            }
        }
        
        // if n <= 0 -> we have to break all bricks
        if n <= 0 {
            return height
        }
        
        // sort it
        freeAt = freeAt[:n]
        sort.Ints(freeAt)
        
        // count max number of duplication
        max, old, counter := 0, freeAt[0]-1, 0
        for _, v := range freeAt {
            if old != v {
                old, counter = v, 0
            }
            
            if counter++; counter > max {
                max = counter
            }
        }
        
        return height - max
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.