Big(O) of finding K element in a MinHeap build from 2 unsorted arrays

Question

Given the question here. https://www.careercup.com/question?id=9406769 which asks: Given two unsorted int arrays, find the kth element in the merged, sorted array. k element in an index that starts at 1.

What would be the BigO performance of the solution below (prints 1):

    object MergeTwoArraysFindK {

  import scala.collection.mutable.PriorityQueue

  def findK(arrayOne: Array[Int], arrayTwo: Array[Int], k: Int): Int = {
    implicit val ord = Ordering[Int].reverse
    val minHeap = new PriorityQueue[Int] ++= (arrayOne ++ arrayTwo).iterator
    for (i <- 1 to k)
      if (i == k)
        return minHeap.dequeue()
      else
        minHeap.dequeue()
    -1
  }

  def main(args: Array[String]): Unit = {
    val arrayOne = Array[Int](3, 4, 9, 0, 1, 2, 4)
    val arrayTwo = Array[Int](5, 4, 1, 0, 9, 8)
    println(findK(arrayOne, arrayTwo, 4))
  }
}

Answer 1

It takes O(n) time to build the heap, and it requires O(n) extra space.

Finding the kth item is O(k log n) Each call to minheap.dequeue requires O(log n), and you're making k calls.

This approach works if you have enough memory to hold everything in memory. If you don't have enough memory, say you're doing this with two absolutely huge files, then the process is slightly different. See Time complexity of Kth smallest using Heap.