Tasks

Top K Elements

Index	Task Name	Task Number	Difficulty	Link
1	Kth Largest Element in an Array	215	Medium	Link
2	Top K Frequent Elements	347	Medium	Link
3	Find K Pairs with Smallest Sums	373	Medium	Link
4	K Closest Points to Origin	973	Medium	Link
5	Top K Frequent Words	692	Medium	Link
6	Kth Smallest Element in a Sorted Matrix	378	Medium	Link
7	Kth Largest Element in a Stream	703	Easy	Link
8	Kth Smallest Number in Multiplication Table	668	Hard	Link
9	Find Median from Data Stream	295	Hard	Link
10	Kth Smallest Element in a BST	230	Medium	Link
11	Reorganize String	767	Medium	Link

// 215. Kth Largest Element in an Array

// Time: O(n log k) | Space: O(k)
var findKthLargest = function(nums, k) {
    const minHeap = new Heap();
    for (let i = 0; i < k; i++) {
        minHeap.add(nums[i]);
    }
    for (let i = k; i < nums.length; i++) {
        if (nums[i] > minHeap.peek()) {
            minHeap.pop();
            minHeap.add(nums[i]);
        }
    }
    return minHeap.peek();
};

/*
 * Min Heap
 * ------------------------------
 * 1. Initialize min heap.
 * 2. Add first k elements to the heap.
 * 3. Iterate over remaining array and update the heap.
 * 4. Return heap root as the k-th largest number.
 * ------------------------------
 * Time: O(n log k) | Space: O(k)
 */ 

// 347. Top K Frequent Elements

// Time: O(n log k) | Space: O(n)
var topKFrequent = function(nums, k) {
    // Initialize min heap and frequency hash map.
    const minHeap = new Heap((a, b) => a.frequency > b.frequency);
    const map = new Map();

    // Fill-in the frequency hash map.
    for (let i = 0; i < nums.length; i++) {
        if (map.has(nums[i])) {
            map.set(nums[i], map.get(nums[i]) + 1);
        } else {
            map.set(nums[i], 1);
        }
    }
    let count = 0;
    const result = [];
    // Fill-in min heap. Keep only k elements in the heap.
    for (const [element, frequency] of map.entries()) {
        minHeap.add({
            element,
            frequency,
        });
        count++;
        if (count > k) {
            minHeap.pop();
        }
    }
    // Get result elements from the heap.
    while (!minHeap.isEmpty()) {
        result.push(minHeap.pop().element);
    }
    return result;
};

/*
 * Min Heap
 * ----------------------------------
 * 1. Initialize min heap and hash map.
 * 2. Fill in the frequency hash map.
 * 3. Iterate over hash map entries to fill in the heap.
 * 4. Keep only k items in the heap.
 * 5. Return heap values.
 * ----------------------------------
 * Time: O(n log k) | Space: O(n)
 */

// 973. K Closest Points to Origin

// Time: O(n log k) | Space: O(k)
var kClosest = function(points, k) {
    // Initialize max heap.
    const maxHeap = new Heap((a, b) => b.distance > a.distance);
    const getDistance = (x, y) => {
        return x*x + y*y;
    }

    // Push k points to the heap.
    for (let i = 0; i < k; i++) {
        maxHeap.add({
            distance: getDistance(...points[i]),
            points: points[i],
        });
    }
    // Iterate over points and update the heap.
    for (let i = k; i < points.length; i++) {
        const ithDistance = getDistance(...points[i]);
        const { distance } = maxHeap.peek();
        if (ithDistance < distance) {
            maxHeap.pop();
            maxHeap.add({
                distance: ithDistance,
                points: points[i],
            });
        }
    }
    // Push all elements from the heap to the result.
    const result = [];
    while (!maxHeap.isEmpty()) {
        result.push(maxHeap.pop().points);
    }
    return result;
};

/*
 * Max Heap
 * ----------------------------------
 * 1. Create the max heap by points distance.
 * 2. Add k elements to the heap.
 * 3. From k-th to length-1 element replace peek with the i-th element if i-th distance is smaller.
 * 4. Push all elements from the heap to the result.
 * 5. Return result.
 * ----------------------------------
 * Time: O(n log k) | Space: O(k)
 */

// 703. Kth Largest Element in a Stream

// Time: O(n log k) | Space: O(n)
var KthLargest = function(k, nums) {
    this.k = k;
    this.minHeap = new Heap();
    for (let i = 0; i < nums.length; i++) {
        this.add(nums[i]);
    }
};

/** 
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function(val) {
    this.minHeap.add(val);
    while (this.minHeap.size() > this.k) {
        this.minHeap.pop();
    }
     return this.minHeap.peek();
};

/*
 * Min Heap
 * ------------------------------
 * 1. Create min heap.
 * 2. Add all nums to the heap.
 * 3. Every add -> add the element, remove while heap.size > k, return peek.
 * ------------------------------
 * Time: O(n log k) | Space: O(n)
 */

// 230. Kth Smallest Element in a BST

// Time: O(n) | Space: O(k)
var kthSmallest = function(root, k) {
    const stack = [];
    const dfs = (node) => {
        if (!node || stack.length === k) {
            return;
        }
        dfs(node.left);
        stack.push(node.val);
        dfs(node.right);
    }
    dfs(root);
    return stack[k - 1];
};

/*
 * DFS
 * --------------------------------
 * 1. Go through the tree using DFS.
 * 2. Push node.val every iteration.
 * 3. Break the loop once stak.length is equal to k.
 * 4. Return stak last element.
 * --------------------------------
 * Time: O(n) | Space: O(k)
 */

// 767. Reorganize String

// Time: O(n log k) | Space: O(1)
var reorganizeString = function(s) {
    const map = new Map();
    const maxHeap = new Heap((a, b) => b.frequency > a.frequency);
    // Add chars to the frequency map.
    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        if (map.has(char)) {
            map.set(char, map.get(char) + 1);
        } else {
            map.set(char, 1);
        }
    }
    // Add chars to the maxHeap.
    for (const [char, frequency] of map.entries()) {
        maxHeap.add({ char, frequency });
    }
    let result = "";
    let prev = null;
    // While we have chars to iterate through.
    while (maxHeap.size() || prev) {
        // Last char is the same as the previous one.
        if (!maxHeap.size() && prev) {
            return "";
        }
        let { char, frequency } = maxHeap.pop();
        result += char;
        frequency--;
        
        // Add prev to the heap
        if (prev) {
            maxHeap.add(prev);
            prev = null;
        }
        // Keep the current popped as prev.
        if (frequency) {
            prev = { char, frequency };
        }
    }
    return result;
};

/*
 * Max Heap
 * ------------------------------
 * 1. Create the frequency map.
 * 2. Create the max heap by frequency.
 * 3. Itrate through the heap and update the result string.
 * ------------------------------
 * Time: O(n log k) | Space: O(1)
 */