Tasks

Two Heaps

May 2023

Index	Name	Number	Difficulty	Link
1	Merge k Sorted Lists	23	Hard	https://leetcode.com/problems/merge-k-sorted-lists/
2	Find Median from Data Stream	295	Hard	https://leetcode.com/problems/find-median-from-data-stream/
3	Sliding Window Median	480	Hard	https://leetcode.com/problems/sliding-window-median/
4	Kth Largest Element in a Stream	703	Medium	https://leetcode.com/problems/kth-largest-element-in-a-stream/
5	Find Median from Two Sorted Arrays	4	Hard	https://leetcode.com/problems/median-of-two-sorted-arrays/
6	IPO	502	Hard	https://leetcode.com/problems/ipo/
7	Find K Pairs with Smallest Sums	373	Medium	https://leetcode.com/problems/find-k-pairs-with-smallest-sums/
8	Last Stone Weight	1046	Easy	https://leetcode.com/problems/last-stone-weight/
9	Kth Smallest Element in a Sorted Matrix	378	Medium	https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
10	Top K Frequent Elements	347	Medium	https://leetcode.com/problems/top-k-frequent-elements/

// 295. Find Median from Data Stream

var MedianFinder = function() {
    this.maxHeap = new Heap(Heap.maxComparator);
    this.minHeap = new Heap(Heap.minComparator);
};

/** 
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function(num) {
    // Add all less then current max to max heap.
    if(this.maxHeap.peek() === null || num < this.maxHeap.peek()) {
        this.maxHeap.add(num);
    // Add all greater or equal to max -> to the min heap.
    } else {
        this.minHeap.add(num);
    }
    
    // Keep heaps same (or n+1) length.
    if(this.maxHeap.size - this.minHeap.size > 1) {
        this.minHeap.add(this.maxHeap.poll());
    } else if(this.minHeap.size - this.maxHeap.size > 1) {
        this.maxHeap.add(this.minHeap.poll());
    }
};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function() {
    if(this.maxHeap.size > this.minHeap.size) {
        return this.maxHeap.peek();
    }
    if(this.minHeap.size > this.maxHeap.size) {
        return this.minHeap.peek();
    }
    return (this.maxHeap.peek() + this.minHeap.peek()) / 2;
};

/*
Two Heaps
------------------------------------
1. Create min and max heap.
2. Add all less then current max to max heap.
3. Add all greater or equal to max -> to the min heap.
4. Keep heaps same (or n+1) length.
5. Return peek of the longer heap or (max.peek + min.peek) / 2.
------------------------------------
Time: O(log n) | Space: O(n)
*/

// 480. Sliding Window Median

// Time: O(n log n) | Space: O(n)
var medianSlidingWindow = function(nums, k) {
    const result = [];
    const medianFinder = new MedianFinder();
    let start = 0;
    for (let end = 0; end < nums.length; end++) {
        medianFinder.add(nums[end]);
        const size = end - start + 1;
        if (size === k) {
            result.push(medianFinder.median());
            medianFinder.remove(nums[start]);
            start++;
        }
    }
    return result;
};

class MedianFinder {
    constructor() {
        this.minHeap = new Heap(Heap.minComparator);
        this.maxHeap = new Heap(Heap.maxComparator);
    }

    add(value) {
        if (this.maxHeap.size() === 0 || this.maxHeap.peek() > value) {
            this.maxHeap.add(value);
        } else {
            this.minHeap.add(value);
        }
        this.balance();
    }

    remove(value) {
        if (value <= this.maxHeap.peek()) {
            this.maxHeap.remove(value);
        } else {
            this.minHeap.remove(value);
        }
        this.balance();
    }

    median() {
        if(this.maxHeap.size() > this.minHeap.size()) {
            return this.maxHeap.peek();
        }
        if(this.minHeap.size() > this.maxHeap.size()) {
            return this.minHeap.peek();
        }
        return this.maxHeap.peek() / 2 + this.minHeap.peek() / 2;
    }

    balance() {
        // If max heap size is bigger by 2 elements or more.
        if (this.maxHeap.size() > this.minHeap.size() + 1) {
            this.minHeap.add(this.maxHeap.pop());
        // If min heap size is bigger by 1 element or more.
        } else if (this.minHeap.size() > this.maxHeap.size()) {
            this.maxHeap.add(this.minHeap.pop());
        }
    }
}

class Heap {
    constructor(comparator) {
        this.values = [];
        this.fn = comparator || Heap.minComparator;
    }

    size() {
        return this.values.length;
    }
    
    isEmpty() {
        return this.size() === 0;
    }

    pop() {
        return this.remove(this.values[0]);
    }

    peek() {
        return this.values[0];
    }

    add(value) {
        this.values.push(value);
        this.#bubbleUp(this.size() - 1);
    }

    remove(value) {
        const index = this.values.indexOf(value);
        // If value is not in heap, return
        if (index === -1) {
            return undefined;
        }
        if (index === this.size() - 1) {
            return this.values.pop();
        }
        this.#swap(index, this.size() - 1);
        const val = this.values.pop();
        this.#bubbleDown(this.#bubbleUp(index));
        return val;
    }

    #swap(index_1, index_2) {
        const temp = this.values[index_1];
        this.values[index_1] = this.values[index_2];
        this.values[index_2] = temp;
    }

    #compare(index_1, index_2) {
        return this.fn(this.values[index_1], this.values[index_2]);
    }

    #bubbleUp(index) {
        // If index is 0, we are at the root
        if (index === 0) {
            return index;
        }
        const parentIndex = Math.floor((index - 1) / 2);
        if (this.#compare(parentIndex, index)) {
            this.#swap(parentIndex, index);
            this.#bubbleUp(parentIndex);
        }
        return index;
    }

    #bubbleDown(index) {
        const leftChildIndex = 2 * index + 1;
        const rightChildIndex = 2 * index + 2;
        let largestIndex = index;
        if (leftChildIndex < this.size() && this.#compare(largestIndex, leftChildIndex)) {
            largestIndex = leftChildIndex;
        }
        if (rightChildIndex < this.size() && this.#compare(largestIndex, rightChildIndex)) {
            largestIndex = rightChildIndex;
        }
        if (largestIndex !== index) {
            this.#swap(index, largestIndex);
            this.#bubbleDown(largestIndex);
        }
        return index;
    }
}

Heap.minComparator = (a, b) => a > b;
Heap.maxComparator = (a, b) => a < b;

/*
 * Two Heaps
 * ------------------------------
 * 1. Initialize 2 heaps.
 * 2. Create MedianFinder class on top of heaps.
 * 3. Push result of every slide to the result array.
 * 4. Return result.
 * ------------------------------
 * Time: O(n log n) | Space: O(n)
 */

// 4. Median of Two Sorted Arrays

// Time: O((n + m) * log (n + m)) | Space: O(n + m)
var findMedianSortedArrays = function(nums1, nums2) {
    const medianFinder = new MedianFinder();
    for (let i = 0; i < nums1.length; i++) {
        medianFinder.add(nums1[i]);
    }
    for (let i = 0; i < nums2.length; i++) {
        medianFinder.add(nums2[i]);
    }
    return medianFinder.median();
};

class MedianFinder {
    constructor() {
        this.minHeap = new Heap(Heap.minComparator);
        this.maxHeap = new Heap(Heap.maxComparator);
    }
    add(value) {
        if (this.maxHeap.isEmpty() || this.maxHeap.peek() > value) {
            this.maxHeap.add(value);
        } else {
            this.minHeap.add(value);
        }
        this.balance();
    }
    median() {
        if (this.minHeap.size() > this.maxHeap.size()) {
            return this.minHeap.peek();
        }
        if (this.maxHeap.size() > this.minHeap.size()) {
            return this.maxHeap.peek();
        }
        return this.minHeap.peek() / 2 + this.maxHeap.peek() / 2;
    }
    balance() {
        if (this.maxHeap.size() > this.minHeap.size() + 1) {
            this.minHeap.add(this.maxHeap.pop());
        } else if (this.minHeap.size() > this.maxHeap.size()) {
            this.maxHeap.add(this.minHeap.pop());
        }
    }
}

/*
 * Two Heaps
 * -------------------------------
 * 1. Create class MedianFinder.
 * 2. Initialize 2 heaps -> min and max.
 * 3. Add elements to heaps and keep them balanced.
 * 4. Return median after all elements are pushed to the heaps.
 * -------------------------------
 * Time: O((n + m) log (n + m)) | Space: O(n + m)
 */

// 502. IPO

// k -> count of projects to use.
// w -> initial capital.
// profits -> [i]profit of every [i]capital.
// capital -> min capital to be able to invest into project. 

// Time: O(n log n) | Space: O(n)
var findMaximizedCapital = function(k, w, profits, capital) {
    let projects = [];
    let heap = new MaxHeap();
    let index = 0;

    // Our result profit.
    let result = w;

    // Merge profits and capitals in one projects array.
    for(let i = 0; i < profits.length; i++) {
        projects.push({
            profit: profits[i],
            capital: capital[i],
        });
    }
    // Sort projects by capital in asc order.
    projects.sort((a, b) => a.capital - b.capital);

    // Push all profits to heap if their capital <= our current capital.
    const addProfitsToHeap = () => {
        while(projects[index]?.capital <= result) {
            heap.insert(projects[index].profit);
            index++;
        }
    }

    // Fill heap with initial available profits.
    addProfitsToHeap();

    // Update result and repeat k times.
    while(heap.heap.length > 0 && k > 0) {
        result += heap.removeMax() || 0;
        addProfitsToHeap();
        k--;
    }

    return result;
};

/*
 * Max Heap
 * -------------------------------
 * 1. Merge profits and capitals into 1 projects array.
 * 2. Sort projects by capital in asc order.
 * 3. Fill-in heap with the profits from projects that match our capital.
 * 4. Count result, update heap with new profits that match our current capital.
 * 5. Return result.
 * -------------------------------
 * Time: O( n log n) | Space: O(n)
 */