optimistiks

// Implement a data structure that’ll store a dynamically growing list of integers and provide access to their median in O(1)
class medianOfStream {
  // elements smaller than current median (max-heap)
  heapSmall = new Heap();
  // elements larger than current median (min-heap)
  heapLarge = new Heap();

  length() {
    // total length is a sum of both heaps lengths
    return this.heapSmall.length() + this.heapLarge.length();

optimistiks

// nums array of numbers, k sliding window size
// return median of every sliding window
// basically we keep two heaps,
// left heap is a max heap where all the numbers lt or equal to median are kept
// right heap is a min heap where all the numbers gt than median are kept
// this way sliding window median is always either left heap top, or avg of two tops
// elements who exit the sliding window are ignored unless they pop to the top of either heap
// then we drop them (we keep track of them leaving the window using a hashmap)
// we also need to make sure that right heap contains exactly half of the current sliding window numbers,
// so we rebalance the heaps if for example an element exited the window from the left heap, and entered to the right heap

optimistiks

// tasksList is an array of tuples [startTime, endTime]
export function tasks(tasksList) {
  // keep our tasks in min-heap, with task with earliest start time on top
  const tasksHeap = new TupleHeap();
  // keep our machines in min heap, with machine whose task finishes earliest on top
  const machinesHeap = new Heap();

  // push all our tasks into min heap
  for (let i = 0; i < tasksList.length; ++i) {
    tasksHeap.push(tasksList[i]);

optimistiks

export function mergeSorted(nums1, m, nums2, n) {
  let p = nums1.length - 1;
  let p1 = m - 1;
  let p2 = n - 1;

  // our main condition is all elements from nums2 are merged into nums1
  // meaning p2 (index in num2) became < 0
  while (p2 >= 0) {
    const num1 = nums1[p1];
    const num2 = nums2[p2];

optimistiks

export function kSmallestNumber(lists, k) {
  const heap = new MinHeap();

  // initialize by pushing first element of each list into heap
  for (let i = 0; i < lists.length; ++i) {
    const list = lists[i];
    if (list[0] != null) {
      heap.offer([list[0], i, 0]);
    }
  }

optimistiks

export function kSmallestPairs(list1, list2, k) {
  let result = [];
  const heap = new MinHeap();

  // we initialize our heap by pairing the first element of list2
  // with every element of list1
  // since our arrays are sorted, our heap will contain our first min pair
  for (let i = 0; i < list1.length; ++i) {
    const a = list1[i];
    const b = list2[0];

optimistiks

function mergeTwoLists(list1, list2) {
  let a = list1.head;
  let b = list2.head;

  let ll = null;
  let tail = null;

  while (a !== null || b !== null) {
    let nextNode = null;

optimistiks

export function kthSmallestNumber(matrix, k) {
  const heap = new MinHeap();

  // initialize by pushing first element of each row into heap
  // since rows and cols are sorted, these are first n smallest elements in the matrix,
  // where n is the number of rows / cols
  for (let i = 0; i < matrix.length; ++i) {
    heap.offer([matrix[i][0], i, 0]);
  }

optimistiks

export function findMedian(nums1, nums2) {
  const totalLength = nums1.length + nums2.length;
  const leftHalfLength = Math.floor(totalLength / 2);

  const listA = nums1.length < nums2.length ? nums1 : nums2;
  const listB = nums1.length < nums2.length ? nums2 : nums1;

  let l = 0;
  let r = listA.length - 1;

optimistiks

class KthLargest {
  // constructor to initialize heap and add values in it
  constructor(k, nums) {
    // we add all elements into the heap, and then pop until we have k elements
    // those k elements are k largest elements from the stream,
    // and the minimum of those elements is in the top of the heap,
    // and this is the element we need - the kth largest element
    const heap = new MinHeap(nums);
    while (heap.size() > k) {
      heap.poll();