215-Kth-largest-element-in-an-array.js

/*
Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
*/
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
/*
Approach 1: Heap
Time complexity : O(N log k)
Space complexity : O(k)
*/
class MaxHeap {
  constructor() {
    this.heap = [0];
  }

  //return the data in the heap
  heapData = () => {
    return this.heap;
  };

  //add the data
  push = (num) => {
    this.heap.push(num);
    if (this.heap.length > 2) {
      let idx = this.heap.length - 1;
      while (this.heap[idx] > this.heap[Math.floor(idx / 2)]) {
        if (idx >= 1) {
          [this.heap[Math.floor(idx / 2)], this.heap[idx]] = [
            this.heap[idx],
            this.heap[Math.floor(idx / 2)],
          ];
          if (Math.floor(idx / 2) > 1) {
            idx = Math.floor(idx / 2);
          } else {
            break;
          }
        }
      }
    }
  };

  //remove the data
  pop = () => {
    let smallest = this.heap[1];
    if (this.heap.length > 2) {
      this.heap[1] = this.heap[this.heap.length - 1];
      this.heap.splice(this.heap.length - 1);
      if (this.heap.length == 3) {
        if (this.heap[1] < this.heap[2]) {
          [this.heap[1], this.heap[2]] = [this.heap[2], this.heap[1]];
        }
        return smallest;
      }
      let i = 1;
      let left = 2 * i;
      let right = 2 * i + 1;
      while (
        this.heap[i] <= this.heap[left] ||
        this.heap[i] <= this.heap[right]
      ) {
        if (this.heap[left] > this.heap[right]) {
          [this.heap[i], this.heap[left]] = [this.heap[left], this.heap[i]];
          i = 2 * i;
        } else {
          [this.heap[i], this.heap[right]] = [this.heap[right], this.heap[i]];
          i = 2 * i + 1;
        }
        left = 2 * i;
        right = 2 * i + 1;
        if (this.heap[left] == undefined || this.heap[right] == undefined) {
          break;
        }
      }
    } else if (this.heap.length == 2) {
      this.heap.splice(1, 1);
    } else {
      return null;
    }
    return smallest;
  };
}

var findKthLargest = function (nums, k) {
  let heap = new MaxHeap();
  for (let i = 0; i < nums.length; i++) {
    heap.push(nums[i]);
  }

  let index = 1;

  while (index < k) {
    heap.pop();
    index++;
  }

  return heap.pop();
};

/*
Approach 2: Quickselect 
Time complexity : O(N) in the average case. O(N^2) in the worst case.
Space complexity : O(1)
*/
var findKthLargest = function (nums, k) {
  k = nums.length - k;

  function quickSelect(l, r) {
    let [pivot, p] = [nums[r], l];

    for (let i = l; i < r; i++) {
      if (nums[i] <= pivot) {
        [nums[p], nums[i]] = [nums[i], nums[p]];
        p += 1;
      }
    }
    [nums[p], nums[r]] = [nums[r], nums[p]];

    if (p > k) {
      return quickSelect(l, p - 1);
    } else if (p < k) {
      return quickSelect(p + 1, r);
    } else {
      return nums[p];
    }
  }

  return quickSelect(0, nums.length - 1);
};

const result = findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4);
console.log(result);