Solving Algorithmic Problems

Description   Solution: Heap Keep a max heap of the kth nearest obstacle distances from the origin. If the size of the heap exceeds  k , we remove the furthest distance. The top of the max heap is the kth nearest obstacle at any point in time. n = length of queries Time Complexity:  O(n log(k)) Space Complexity:  O(k) function resultsArray(queries, k) { let heap = new Heap((a, b) => b - a); let results = []; for (let [x, y] of queries) { let dist = Math.abs(x) + Math.abs(y); heap.add(dist); if (heap.size > k) { heap.remove(); } results.push(heap.size < k ? - 1 : heap.top()); } return results; }; class Heap { constructor (comparator = ((a, b) => a - b)) { this .values = []; this .comparator = comparator; this .size = 0 ; } add( val ) { this .size++; this .values.push( val ); let idx = this .size - 1 , parentIdx = Math.floor((idx - 1 ) / 2 ); while (parentIdx >= 0 && ...

Description   Solution 1: Segment Tree Use a max segment tree to efficiently find and update the maximum frequency in the range  (0, 10^5) . n = length of nums ,  m = max(nums[i]) Time Complexity:  O(m + n log(m)) Space Complexity:  O(m)  (excluding output) var mostFrequentIDs = function ( nums, freq ) { let n = nums.length, m = Math .max(...nums), tree = new MaxSegmentTree(m); let ans = Array (n); for ( let i = 0 ; i < n; i++) { let id = nums[i] - 1 ; tree.add(id, freq[i]); ans[i] = tree.maxRange( 0 , m - 1 ); } return ans; }; class MaxSegmentTree { constructor ( n ) { this .size = n; this .segTree = Array (n * 2 ).fill( 0 ); } add ( index, value ) { let n = this .size, idx = index + n; this .segTree[idx] += value; idx = Math .floor(idx / 2 ); while (idx > 0 ) { this .segTree[idx] = Math .max( this .segTree[idx * 2 ], this .segTree[idx * 2 + 1 ]); idx = Math .floor(idx /...