Solving Algorithmic Problems

Description   Solution: Two Monotonic Queues Use two deques to keep track of the indices of the maximum and minimum numbers so far. queueDec: monotonic decreasing queue of numbers so far queueInc: monotonic increasing queue of numbers so far For each  nums[i] , count the number of subarrays that end with  nums[i] . Pop out elements from the back of the queues to maintain the monotonic decreasing and increasing properties. Pop out elements from the front of the queue that have gone out of range (difference between  nums[queue.front()]  and  nums[i]  is greater than  2 ). Between the two indexes at the front of the both queues, we take the maximum index. The number of subarrays ending at nums[i] =  i - Math.max(decIndex, incIndex) + 1 Time Complexity:  O(n) Space Complexity:  O(n) var continuousSubarrays = function(nums) { let n = nums.length, queueDec = new Deque(), queueInc = new Deque(); let ans = 0 , decIndex = 0 , incIndex =...

Description   Solution: Sliding Window & Monotonic Decreasing Deque Maintain a sliding window where the  total cost <= budget . When the total cost exceeds the budget, move up the left pointer until it is within the budget. To get the maximum chargeTime so far, maintain a monotonic decreasing queue. There is no point keeping smaller chargeTimes at earlier indexes. Remove smaller chargeTimes from the back of the queue. As we move the left pointer up, remove expired indexes from the front of the queue. The chargeTime at the front of the queue is the maximum chargeTime in the current window. Record the largest size of the sliding window. Time Complexity:  O(n)  276ms Space Complexity:  O(n)  58.9MB var maximumRobots = function(chargeTimes, runningCosts, budget) { let n = chargeTimes.length, queue = new Deque(); let runningCost = 0 , ans = 0 ; for (let j = 0 , i = 0 ; j < n; j++) { runningCost += runningCosts[j]; while (!queue.isEmpty...

Description   Solution 1: DP w/ Max Heap Use an array 'dp' to keep track of the maximum score from each position to n - 1. Set dp[n - 1] to nums[n - 1], since we must end up there. Maintain a heap of indices and initialize the heap with n - 1. The heap is sorted in descending order by the values in dp. Loop from n - 2 to 0, Remove the expired indices from the top of the heap (indices greater than i + k) Set the value of dp[i] to nums[i] + the best option in the range of [i + 1, i + k] (top of the heap) Add the current index to the heap. The answer is dp[0]. Time Complexity: O(n log(n)) 305ms Space Complexity: O(n) 91.8MB var maxResult = function(nums, k) { let n = nums.length, dp = Array(n); let heap = new PriorityQueue((a, b) => dp[b] - dp[a]); dp[n - 1 ] = nums[n - 1 ]; heap.add(n - 1 ); for (let i = n - 2 ; i >= 0 ; i--) { while (heap.top() > i + k) heap.remove(); // remove expired dp[i] = nums[i] + dp[heap.top()]; heap.add(i); } ret...

Description   Solution: Sliding Window & Montonic Increasing/Decreasing Queue Use two deques to keep track of the minimum and maximum within the window. min_queue: monotonic increasing queue (min_queue[0] is min) max_queue: monotonic decreasing queue (max_queue[0] is max) Instead of storing the values of nums in the queues, store the indices. Maintain two pointers for a sliding window where max - min is within the limit. Record the length of the longest window. Time Complexity: O(n) 149ms Space Complexity: O(n) 54.2MB var longestSubarray = function(nums, limit) { let min_queue = new Deque(), max_queue = new Deque(); let ans = 0 ; for (let j = 0 , i = 0 ; j < nums.length; j++) { while (min_queue.size && nums[min_queue.back()] >= nums[j]) min_queue.pop(); // pop out larger elements while (max_queue.size && nums[max_queue.back()] <= nums[j]) max_queue.pop(); // pop out smaller elements min_queue.push(j), max_queue.push(j); ...