package com.kingchampion36.dsa.arrays

import java.util.PriorityQueue

/**
 * Sort the list and find kth smallest element
 * Time complexity - O(n * log(n))
 */
fun List<Int>.kthSmallestElementBySorting(k: Int) = when {
  isEmpty() -> throw IllegalArgumentException("List should not be empty")
  k <= 0 || k >= size -> throw IllegalArgumentException("Invalid value $k of k")
  else -> sorted()[k - 1]
}

/**
 * Time Complexity - O(n * log(k))
 */
fun List<Int>.kthSmallestElementByUsingMaxHeap(k: Int): Int {
  require(isNotEmpty()) { "List should not be empty" }

  // k should be between 0 and size (0 < k <= size)
  require(k in 1..size) { "Invalid value of k" }

  val maxHeap = PriorityQueue<Int>(reverseOrder())

  // Build a max heap with first k elements
  for (i in 0 until k) {
    maxHeap.offer(this[i])
  }

  for (i in k until size) {
    // If current element is smaller than the top element of max heap,
    // pop it and insert current element in the max heap
    if (this[i] < maxHeap.peek()) {
      maxHeap.poll()
      maxHeap.offer(this[i])
    }
  }

  return maxHeap.peek()
}

/**
 * Time Complexity - O(n * log(k))
 */
fun List<Int>.kthLargestElementByUsingMinHeap(k: Int): Int {
  require(isNotEmpty()) { "List should not be empty" }

  // k should be between 0 and size (0 < k <= size)
  require(k in 1..size) { "Invalid value of k" }

  val minHeap = PriorityQueue<Int>()

  // Build a min heap with first k elements
  for (i in 0 until k) {
    minHeap.offer(this[i])
  }

  for (i in k until size) {
    // If current element is greater than the top element of min heap,
    // pop it and insert current element in the min heap
    if (this[i] > minHeap.peek()) {
      minHeap.poll()
      minHeap.offer(this[i])
    }
  }

  return minHeap.peek()
}
