Priority Queue

Question 1

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

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

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

Answer 1

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    const sortedNums = [...nums].sort((a, b) => b - a);
    return sortedNums[k - 1];
};

Question 2

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

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

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

Answer 2

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(matrix, k) {
    const n = matrix.length;
    const res = [];

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            res.push(matrix[i][j]);
        }
    }
    res.sort((a, b) => a - b);
    return res[k - 1];
};

Question 3

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Answer 3

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    if (k === nums.length){
        return nums;
    }

const count = {};

    for (const n of nums) {
        if (count[n]) {
            count[n] += 1;
        } else {
            count[n] = 1;
        }
    }
    const ans = Object.keys(count).sort((key1, key2) => count[key2] - count[key1]);
    return ans.slice(0, k);
};

Question 4

Given a non-empty list of words, return the k most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

Example 1:
Input: [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
Output: [“i”, “love”]
Explanation: “i” and “love” are the two most frequent words.
Note that “i” comes before “love” due to a lower alphabetical order

Answer 4

/**
 * @param {string[]} words
 * @param {number} k
 * @return {string[]}
 */
var topKFrequent = function(words, k) {
    if (k === words.length){
        return words.sort();
    }

const count = {};

    for (const n of words) {
        if (count[n]) {
            count[n] += 1;
        } else {
            count[n] = 1;
        }
    }
    const ans = Object.keys(count).sort().sort((key1, key2) => count[key2] - count[key1]);
    return ans.slice(0, k);
};

Question 5

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Answer 5

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */

var mergeKLists = function(lists) {
    const q = [];
    const head = new ListNode(0);
    let point = head;

    for (let l of lists) {
        while (l) {
            q.push(l.val);
            l = l.next;
        }
    }
    q.sort((a, b) => a - b);
    for (const x of q) {
        point.next = new ListNode(x);
        point = point.next;
    }

return head.next; };

Question 6

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Answer 6

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    const res = [];

    for (let i = 0; i <= nums.length - k; i++) {
        let max = nums[i];
        for (let j = i + 1; j < i + k; j++) {
            if (max < nums[j]) {
                max = nums[j];
            }
        }
        res.push(max);
    }

return res; };