Solve Skyline Problem by Swift - Leetcode 218

Detail of this problem can be found here.

https://leetcode.com/problems/the-skyline-problem/

We will be given a list of buildings.
A building can be represented by a triplet of integers [Li, Ri, Hi], equivalent to 4 points in XY coordinate: (0, Li), (0, Ri), (Hi, Li), (Hi, Ri).

Then we need to return list of points (x, y) that could make a skyline view below:

You can watch the video below, Tushar Roy explained so clearly.
https://www.youtube.com/watch?v=GSBLe8cKu0s

I summarize those key steps:

• Separate a building to 2 lines : (x1, y1, start), (x2, y1, end)

• Sort all lines of all buildings by x, if x is same, we need a tiebreaker rule
  Tie-breaker rule contains 3 conditions: all starts (higher y comes first), all ends (lower y comes first), one start + one end (start comes first). Explaination could be found in the video.

• Iterate through list of lines, then put/remove a line to Priority Queue with y is priority factor.

  • When meet a start line, put it to PriorityQueue, if max of the queue is changed, mark (x,y) of the line as an output point.
  • When meet a end line, remove the start line in PriorityQueue, if max of the queue is changed, mark (x,y) of the line as an output point.

Let start to implement:
We define a data structure for line first.

struct Skyline {
    var point: (x: Int, height: Int)
    var isStart: Bool
    
    static func getSkylines(from building: (L: Int, R: Int, H: Int)) -> [Skyline] {
        return [
            Skyline(point: (x: building.L, height: building.H), isStart: true),
            Skyline(point: (x: building.R, height: building.H), isStart: false)
        ]
    }
    
    static func getSkylines(from building: [Int]) -> [Skyline] {
        return self.getSkylines(from: (L: building[0], R: building[1], H: building[2]))
    }
}

extension Skyline : Comparable {
    static func == (lhs: Skyline, rhs: Skyline) -> Bool {
        return lhs.point.x == rhs.point.x && lhs.point.height == rhs.point.height && lhs.isStart == rhs.isStart
    }
    
    static func < (lhs: Skyline, rhs: Skyline) -> Bool {
        
        //normal case
        guard lhs.point.x == rhs.point.x else {
            return lhs.point.x < rhs.point.x
        }
        
        //same type
        guard lhs.isStart == rhs.isStart else {
            return lhs.isStart
        }
        
        //different type
        if lhs.isStart {
            return lhs.point.height > rhs.point.height
        } else {
            return lhs.point.height < rhs.point.height
        }
    }
}

Next priority queue and priority elements

struct PriorityQueue<Element: Equatable> {
    var heap: Heap<Element>
    
    var isEmpty: Bool {
        return heap.isEmpty
    }
    
    init(elements: [Element], priorityFunction: @escaping (Element, Element) -> Bool) {
        heap = Heap(elements: elements, priorityFunction: priorityFunction)
    }
    
    mutating func enqueue(_ item: Element) {
        heap.enqueue(item)
    }
    
    mutating func dequeue() -> Element? {
        return heap.dequeue()
    }
    
    mutating func peek() -> Element? {
        return heap.peek()
    }
    
    mutating func remove(_ element: Element) {
        return heap.remove(element)
    }
}

struct Heap<Element: Equatable> {
    var elements: [Element]
    let priorityFunction: (Element, Element) -> Bool
    
    init(elements: [Element], priorityFunction: @escaping (Element, Element) -> Bool) {
        self.elements = elements
        self.priorityFunction = priorityFunction
        buildHeap()
    }
    
    var isEmpty: Bool {
        return elements.count == 0
    }
    var count: Int {
        return elements.count
    }
    
    //Helper
    func isRoot(_ index: Int) -> Bool {
        return index == 0
    }
    func getLeftChildIndex(of index: Int) -> Int {
        return (2 * index) + 1
    }
    func getRightChildIndex(of index: Int) -> Int {
        return (2 * index) + 2
    }
    func getParentIndex(of index: Int) -> Int {
        return (index - 1) / 2
    }
    func getElement(at index: Int) -> Element? {
        guard index < elements.count else {
            return nil
        }
        return elements[index]
    }
    func isHigherPriority(at index: Int, than secondIndex: Int) -> Bool {
        let el1 = getElement(at: index)
        let el2 = getElement(at: secondIndex)
        if el1 == nil && el2 != nil {
            return false
        }
        if el2 == nil && el1 != nil {
            return true
        }
        if el2 == nil && el1 == nil {
            return false
        }
        return priorityFunction(el1!, el2!)
    }
    
    func getFamilyHighest(at index: Int) -> Int {
        let children1 = getLeftChildIndex(of: index)
        let children2 = getRightChildIndex(of: index)
        let maxChild = isHigherPriority(at: children1, than: children2) ? children1 : children2
        return isHigherPriority(at: index, than: maxChild) ? index : maxChild
    }
    
    mutating func swap(at index: Int, with secondIndex: Int) {
        guard index != secondIndex else {
            return
        }
        elements.swapAt(index, secondIndex)
    }
    
    
    //Heap sift function
    mutating func siftUp(at index: Int) {
        guard !isRoot(index) else { return }
        
        let parent = getParentIndex(of: index)
        if !isHigherPriority(at: index, than: parent) {
            return
        }
        
        swap(at: index, with: parent)
        siftUp(at: parent)
    }
    mutating func siftDown(at index: Int) {
        let highestIndex = getFamilyHighest(at: index)
        if index == highestIndex {
            return
        }
        swap(at: index, with: highestIndex)
        siftDown(at: highestIndex)
    }
    mutating func buildHeap() {
        for index in (0 ..< count / 2).reversed() {
            siftDown(at: index)
        }
    }
    
    //Queue function
    mutating func enqueue(_ element: Element) {
        elements.append(element)
        siftUp(at: count - 1)
    }
    
    mutating func dequeue() -> Element? {
        guard !isEmpty else { return nil }
        swap(at: 0, with: count - 1)
        let ele = elements.removeLast()
        if !isEmpty{
            siftDown(at: 0)
        }
        return ele
    }
    
    mutating func peek() -> Element? {
        return elements.first
    }
    
    //temporary
    mutating func remove(_ element: Element) {
        if let index = elements.firstIndex(where: { $0 == element}) {
            elements.remove(at: index)
            buildHeap()
        }
    }
 }

struct QueueElement {
    var height: Int
    var point: (x: Int, y: Int)
    
    init() {
        height = 0
        point = (x: 0, y: 0)
    }
    
    init(_ skyline: Skyline) {
        height = skyline.point.height
        point = (x: skyline.point.x, y: skyline.point.height)
    }
}

extension QueueElement : Comparable {
    static func == (lhs: QueueElement, rhs: QueueElement) -> Bool {
        return lhs.height == rhs.height
    }
    static func < (lhs: QueueElement, rhs: QueueElement) -> Bool {
        return lhs.height < rhs.height
    }
}

Because this Priority Queue doesn't support removing a specific element, I tried to add a remove(_:) function with removeElement and buildHeap as part.
But it takes O(n) time.

Below are solution function

func getSkyline(_ buildings: [[Int]]) -> [[Int]] {
    var result: [[Int]] = []
    var skylines: [Skyline] = []

    for building in buildings {
        skylines.append(contentsOf: Skyline.getSkylines(from: building))
    }

    skylines.sort()

    var queue = PriorityQueue<QueueElement>(elements: [QueueElement()], priorityFunction: { $0 > $1})

    for skyline in skylines {
        let currentMax = queue.peek()!
        if skyline.isStart {
            queue.enqueue(QueueElement(skyline))
        }else{
            queue.remove(QueueElement(skyline))
        }

        let newMax = queue.peek()!
        if currentMax != newMax {
            if skyline.isStart {
                result.append([skyline.point.x, skyline.point.height])
            }else{
                result.append([skyline.point.x, newMax.height])
            }
        }

    }

    return result
}

PriorityQueue does not support remove element with LogN time. To totally resolve this problem, there must be a replacement.

I will update later.
Thanks for reading.