Leetcode 1438 - Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit [23/6/24]

Time Taken: ~40 mins
Tag: LeetCode Medium
Basic ideas:
Keep track of 2 deques, “minQueue” and “maxQueue”.
Purpose of minQueue is to keep track of the minimum element in current sliding window.
Purpose of maxQueue is to keep track of the maximum element in current sliding window.
Keep track of left starting index and right ending index (exclusive) of current sliding window
While difference between max element and min element exceeds limit, reduce sliding window by incrementing the starting index.
Tips:
Why use 2 deques instead of a queue? To keep track of the min and max element of current sliding window.
We do so by making “minQueue” store elements in increasing order, “maxQueue” store elements in decreasing order.
When the current element is considered, we add current element to “minQueue” after popping all elements from the back that is greater than current element. This ensures that the information about “minimum element” in current sliding window would always be accurate just by considering the front element of “minQueue”.
Similarly for “maxQueue”, we add current element to “maxQueue” after popping all elements from the back that is smaller than current element to ensure that information about “maximum element” in current sliding window would always be accurate just by considering the front element of “maxQueue”.
When shifting starting index to the right,
if nums[startInd] is the current minimum element (meaning it is the front of minQueue), we pop element from the front of minQueue.
if nums[startInd] is the current maximum element (meaning it is the front of maxQueue), we pop element from the front of maxQueue.
This helps us continue the accuracy of tracking “minimum element” and “maximum element” just by looking at the front of “minQueue” and “maxQueue” respectively.