Swift solutions are too slow?


  • 0
    S

    Hi, I tried to implement couple of a different solutions in Swift and they all run out of time (at the test case with hundreds of 1-node lists). Does anybody has a Swift solution that can make it in time?

    First I implemented a solution by sorting the input lists, then taking always the first element and adding it's child to the list by binary halving:

    class Solution {
        func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
            let dummyHead = ListNode(0)
            var tail = dummyHead
            var lists = lists.filter({ $0 != nil }).map({ $0! }).sorted(by: { $0.val < $1.val })
            
            while let first = lists.first {
                lists.remove(at: 0)
                tail.next = first
                tail = first
                if let next = first.next {
                    addList(list: next, toSortedArray:&lists)
                }
            }
            
            return dummyHead.next
        }
        
        // add the child list by binary search to the right position
        private func addList(list: ListNode, toSortedArray array: inout [ListNode]) {
            
            var mini = 0
            var maxi = array.count - 1
            var pos = mini
            
            while mini <= maxi {
                let i = (maxi + mini) / 2
                if list.val < array[i].val {
                    maxi = i - 1
                    pos = i
                } else if list.val > array[i].val {
                    mini = i + 1
                    pos = mini
                } else {
                    array.insert(list, at: i)
                    return
                }
            }
            
            array.insert(list, at: pos)
        }
    }
    

    I thought the problem might be that the insert(childList) and remove(at: 0) methods of the Swift Array are too slow (the doc says they both run in O(n)). So I implemented a solution by performing the operations myself by swapping the values and removing/inserting only the last element which should be in O(1):

    class Solution {
        
        private var heap = [ListNode]()
        
        func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
            let dummyHead = ListNode(0)
            var tail = dummyHead
            buildHeap(lists)
            
            while let current = popElement() {
                tail.next = current
                tail = current
                if let next = current.next {
                    addElement(list: next)
                }
            }
            
            return dummyHead.next
        }
        
        private func buildHeap(_ lists: [ListNode?]) {
            heap.reserveCapacity(lists.count)
            for list in lists {
                if let list = list {
                    addElement(list: list)
                }
            }
        }
        
        private func addElement(list: ListNode) {
            heap.append(list)
            shiftUp(index: heap.count - 1)
        }
        
        private func popElement() -> ListNode? {
            if heap.isEmpty {
                return nil
            } else if heap.count == 1 {
                return heap.removeLast()
            } else {
                let value = heap[0]
                heap[0] = heap.removeLast()
                shiftDown(index: 0, heapSize: heap.count)
                return value
            }
        }
        
        private func shiftUp(index: Int) {
            var childIndex = index
            let child = heap[childIndex]
            var parentIndex = (childIndex - 1) / 2
            
            while childIndex > 0 && child.val < heap[parentIndex].val{
                heap[childIndex] = heap[parentIndex]
                childIndex = parentIndex
                parentIndex = (childIndex - 1) / 2
            }
            
            heap[childIndex] = child
        }
        
        private func shiftDown(index: Int, heapSize: Int) {
            var parentIndex = index
            
            while true {
                let leftChildIndex = 2 * parentIndex + 1
                let rightChildIndex = leftChildIndex + 1
                
                var first = parentIndex
                if leftChildIndex < heapSize && heap[leftChildIndex].val < heap[first].val {
                    first = leftChildIndex
                }
                if rightChildIndex < heapSize && heap[rightChildIndex].val < heap[first].val {
                    first = rightChildIndex
                }
                if first == parentIndex { return }
                
                swap(&heap[parentIndex], &heap[first])
                parentIndex = first
            }
        }
    }
    

    But this is still running out of time on that same test case.


  • 0
    N

    all of my solutions also resulted in TLE, even one i converted from my previous javascript accepted solution.


  • 0
    S

    The only one way how I could make all tests pass in time was sorting all as integers and then recreating the nodes structure again. Not nice but it works (in 142ms actually):

    class Solution {
    
        func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
            let dummyHead = ListNode(0)
            let _ = lists.flatMap({ flatten($0) }).sorted().reduce(dummyHead) { (prevNode, nextVal) in
                prevNode.next = ListNode(nextVal)
                return prevNode.next! 
            }
            return dummyHead.next
        }
        
        private func flatten(_ head: ListNode?) -> [Int] {
            var array = [Int]()
            var head = head
            
            while head != nil {
                array.append(head!.val)
                head = head!.next
            } 
            
            return array
        }
        
    }
    

Log in to reply
 

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