[Leetcode/Heap] 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

🌷 Subarray vs Subsequence

"Do I need to pick connected elements?" - have to be contiguous	Subarray	Ex) arr = [1, 2, 3, 4] ❌ [1, 3] is not valid — skips 2
"Can I pick elements freely as long as I keep the order?" - do not have to be contiguous	Subsequence	✅ [1, 4] is valid — it's in the correct order.

 

---

✅ Code Overview

You're implementing a sliding window approach, where:

• You track the maximum and minimum values inside the window.
• If max - min > limit, the window is invalid and needs to be shrunk.
• You update the result with the maximum window length that is valid.

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        min_heap = []  # (value, index)
        max_heap = []  # (-value, index) for max heap
        left = 0
        res = 0

        # Loop through right (end of window)
        for right in range(len(nums)):
            # Push current number into both heaps
            heapq.heappush(min_heap, (nums[right], right))
            heapq.heappush(max_heap, (-nums[right], right))

            # Check if the window is valid
            while -max_heap[0][0] - min_heap[0][0] > limit:
                left += 1  # shrink the window

                # Remove elements that are out of the window
                while min_heap and min_heap[0][1] < left:
                    heapq.heappop(min_heap)
                while max_heap and max_heap[0][1] < left:
                    heapq.heappop(max_heap)

            # Update max result
            res = max(res, right - left + 1)

        return res

❌ Check if window is invalid:

while -max_heap[0][0] - min_heap[0][0] > limit:

while -max_heap[0][0] - min_heap[0][0] > limit:

• -max_heap[0][0] gives you the maximum value.
• min_heap[0][0] gives you the minimum value.
• If their difference is greater than the limit, the window is not valid.

✅ Now what does min_heap[0][1] mean?

• min_heap[0] → The smallest value tuple in the heap
• min_heap[0][1] → The index of that smallest value in the original array

🔍 Why check min_heap[0][1] < left?

Remember:
We’re using a sliding window from left to right.

As you shrink the window from the left (when the window becomes invalid), some elements in the heap might be outside the window (i.e., their index is less than left).

 

➡️ So we do this:

while min_heap and min_heap[0][1] < left:
	heapq.heappop(min_heap)

To remove stale (out-of-window) elements from the heap — even if they are still at the top of the heap.

 

📌 Example:

Let's say:

nums = [8, 2, 4, 7]
limit = 4

Steps:

• Start with left = 0, right = 0 → 3
• Build window: [8] → [8,2] → [8,2,4] (max=8, min=2 → diff=6 > 4) → shrink left
• New window: [2,4] (max=4, min=2 → diff=2 <= 4) → valid
• Then [2,4,7] → max=7, min=2 → diff=5 > 4 → shrink again

So the longest valid subarray is [2,4] → length = 2