# Swift solutions are too slow?

• 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? {
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 {
}
}

}

// 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? {
buildHeap(lists)

while let current = popElement() {
tail.next = current
tail = current
if let next = current.next {
}
}

}

private func buildHeap(_ lists: [ListNode?]) {
heap.reserveCapacity(lists.count)
for list in lists {
if let list = list {
}
}
}

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.

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

• 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 _ = lists.flatMap({ flatten(\$0) }).sorted().reduce(dummyHead) { (prevNode, nextVal) in
prevNode.next = ListNode(nextVal)
return prevNode.next!
}
}

private func flatten(_ head: ListNode?) -> [Int] {
var array = [Int]()