Using Priority Queues on LeetCode in JavaScript and TypeScript to avoid Time Limit Exceeded

A lot of problems on LeetCode require the use of a Priority Queue. Without it, even though your implementation works, it will not be efficient enough and the submission might fail with the dreaded "Time Limit Exceeded", passing only 980 out of 1000 tests.

Solving questions without a Priority Queue

Since browsers do not offer Priority Queues, I've usually resorted to sorting the whole array every time I need to get the largest or smallest element. That runs in O(n * log n).

const queue = [];
queue.push(start);

while (queue.length) {
// Restore the order. Sort by increasing cost.
queue.sort((a, b) => cost[a] - cost[b]);
// Take the most costly element.
queue.pop();

// Do things
...
// Add them to the queue, but now queue is unsorted.
queue.push(new elements);
}

I could have tried to implement some kind of Priority Queue myself using an array, doing binary search to find where to insert it in O(log n), then using splice to insert the element where it should be, but that seems like too much work, and even then, insertion using splice in the browser takes O(n), so the total complexity of such an insertion would be O(n + log n) = O(n), which is larger than the usual heap insertion, which runs in O(log n).

LeetCode provides a Priority Queue

I was trying to solve https://leetcode.com/problems/path-with-maximum-probability/ in TypeScript using the method above but couldn't optimize it enough. So I looked at the solutions in TypeScript and came across this solution:

const heap = new MaxPriorityQueue({ priority: comparator });
heap.enqueue([start, 1]);
const visited = new Set<number>();

while(!heap.isEmpty()){
const [current, prob] = heap.dequeue().element;
...
}

What is this sorcery? After googling a bit, I found this post on StackOverflow that links to the LeetCode documentation of each runtime environment:

JavaScript

Your code is run with --harmony flag, enabling new ES6 features.
lodash.js library is included by default.
For Priority Queue / Queue data structures, you may use version 4.1 datastructures-js/priority-queue and datastructures-js/queue.

Amazing!

TypeScript

It appears MaxPriorityQueue is not available

Your code is run with --harmony flag, enabling new ES2020 features. lodash.js library is included by default.

Does it mean that TypeScript does not ship with @datastructures-js/priority-queue?? Indeed the syntactic check underlines new MaxPriorityQueue() in red.

I tried to import it at the top of my solution with:

import { MaxPriorityQueue } from '@datastructures-js/priority-queue';


And this too got underlined in red.

But it really is

But if I remove the import and just use the MaxPriorityQueue blindly, it actually works. You can confirm that by running console.log(queue).

They use version 4.1

Finally I was getting really strange results because the new API of version 6 looks like this:

const bidsQueue = new MaxPriorityQueue((bid) => bid.value);
pq.dequeue(); // returns the actual bid object.

But version 4, which dates back from 3 years ago, looks like this:

const bidsQueue = new MaxPriorityQueue({ priority: (bid) => bid.value });
pq.dequeue(); // returns { priority: number, element: bid }

The problem is the compiler does not complain at all if you accidentally write it in the version 6 style. It will simply ignore the function that you passed, since the value for key "priority" is undefined.

I filed a ticket to suggest they fix both the documentation of the TypeScript runtime environment, and use version 6, which has a much better API.