The O(n) Club: Longest Continuous Subarray with Absolute Diff ≤ Limit (or, How to Win at Window-Stretching)

The O(n) Club: Longest Continuous Subarray with Absolute Diff ≤ Limit (or, How to Win at Window-Stretching)

⚡ TL;DR

Need the biggest, baddest subarray where the gap between the largest and smallest number won’t give your compliance manager a panic attack? Sure, brute force works…if your job title is ‘Human Delay Processor’. But real pros use two monotonic deques to track the window min and max in O(n) time, like this:

// Please don't: O(n^2) boredom ahead
for (int i = 0; i < nums.length; i++) {
    for (int j = i; j < nums.length; j++) {
        int min = findMin(nums, i, j);
        int max = findMax(nums, i, j);
        if (max - min <= limit) updateAnswer(i, j);
    }
}

Do yourself a favor—read on and win the interview.

🧠 How Devs Usually Mess This Up

Classic rookie moves:

• Comparing every possible element pair—because nothing says ‘fast’ like O(n²).
• Recomputing min/max from scratch each window—sure, rebuild the kitchen every time you want a snack.
• Mixing up subarrays (contiguous!) and subsequences—remember, only stretches count, not your algorithm’s greatest hits playlist.

This is why brute-force Java forests and existential developer crises exist.

🔍 What’s Actually Going On

Imagine a conveyor belt rolling out snacks. You want the longest stretch where your largest potato chip and your smallest potato chip aren’t picking a fight bigger than your limit. You only care about the biggest and smallest—comparing everything else is like arguing about the humidity on Mars.

Monotonic deques are hungry little robots that line up all candidates for min/max—and promptly throw out anyone who can’t possibly matter anymore. Slide your window, update the deques, check if the window got too rowdy (max – min > limit), and move on. Happens in O(n) because each chip enters and leaves the lineup at most once.

🛠️ PseudoCode

• Initialize window bounds: left = 0
• Track possible mins with minDeque (smallest at the front), maxs with maxDeque (largest at the front)
• Loop right from 0 to nums.length-1:
  • Pop from minDeque’s back while nums[right] < nums[minDeque.peekLast()]
  • Pop from maxDeque’s back while nums[right] > nums[maxDeque.peekLast()]
  • Add right index to both deques
  • While nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > limit:
    • Increase left, remove indices now out of the window from both deques
  • Update result if right - left + 1 is bigger than ever

// ...see? Step-by-step, no time for existential dread.

💻 The Code

import java.util.ArrayDeque;
import java.util.Deque;
 public int longestSubarray(int[] nums, int limit) {
    Deque
<integer> minDeque = new ArrayDeque<>();
    Deque
<integer> maxDeque = new ArrayDeque<>();
    int left = 0, ans = 0;
    for (int right = 0; right < nums.length; right++) {
        while (!minDeque.isEmpty() && nums[right] < nums[minDeque.peekLast()])
            minDeque.pollLast();
        minDeque.offerLast(right);
         while (!maxDeque.isEmpty() && nums[right] > nums[maxDeque.peekLast()])
            maxDeque.pollLast();
        maxDeque.offerLast(right);
         while (nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > limit) {
            left++;
            if (minDeque.peekFirst() < left) minDeque.pollFirst();
            if (maxDeque.peekFirst() < left) maxDeque.pollFirst();
        }
         ans = Math.max(ans, right - left + 1);
    }
    return ans;
}
</integer></integer>

⚠️ Pitfalls, Traps & Runtime Smacks

• Zombie indices: Don’t let deques keep indices of elements that already left the window. That way lies madness (and wrong answers).
• Confusing indices with values: Hold indices, not values, so you can boot them when left passes their sell-by date.
• Check your window math! ans = Math.max(ans, right - left + 1) is classic fencepost-territory.
• Each element enters and exits at most once per deque: O(n), not O(n^2). No need for a stopwatch, it’s fast.

🧠 Interviewer Brain-Tattoo

“If you’re recomputing min and max every window, you’re building a rocket to order pizza. Deque and slide, or prepare for takeoff.”