Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (LeetCode 1438)
Take the integer array nums and an integer limit. Look for the longest non-empty contiguous run of nums (a subarray) in which every pair of elements inside the run differs by at most limit.
Equivalently, the run's largest value minus its smallest value must be at most limit. Return the length of the longest such run.
Worked Examples
nums = [8,2,4,7], limit = 42nums = [10,1,2,4,7,2], limit = 54⚖️Formal Constraints & Bounds
1 <= nums.length <= 1051 <= nums[i] <= 1090 <= limit <= 109
Core Insight
Two deques read the same window side by side: max_dq strictly decreasing gives the window's maximum at its front, min_dq strictly increasing gives the minimum at its front, so nums[max_dq[0]] - nums[min_dq[0]] is the window's exact spread with no rescan. Shrinking the window checks both fronts on every step, because each deque only evicts the indices it has itself checked.
Real-World Scenario & Production Applications
Alerting systems that only fire while a sensor or price feed's recent range (its maximum minus its minimum) stays inside a tolerance band, such as a thermostat's calm range or a trading band that should not fire on ordinary noise.
Subproblems & Recurrence Decomposition3 Phases
max_dq pops every value <= nums[right] from the back, so its values strictly decrease. min_dq pops every value >= nums[right] from the back, so its values strictly increase. Each rule is the single-deque Monotonic Deque rule, run on its own side.
while max_dq and nums[max_dq[-1]] <= nums[right]:
max_dq.pop()
max_dq.append(right)
while min_dq and nums[min_dq[-1]] >= nums[right]:
min_dq.pop()
min_dq.append(right)Step-by-Step Execution Trace Table
right | nums[right] | max_dq after push | min_dq after push | Shrink while spread > limit | best |
|---|---|---|---|---|---|
| 0 | 8 | [0] (values 8) | [0] (values 8) | spread 0, no shrink | 1 |
| 1 | 2 | [0, 1] (values 8, 2) | [1] (pops 0: 8 >= 2) | spread 6 > 4: left -> 1, max_dq drops 0 -> [1] | 1 |
| 2 | 4 | [2] (pops 1: 2 <= 4) | [1, 2] (values 2, 4) | spread 2, no shrink | 2 |
| 3 | 7 | [3] (pops 2: 4 <= 7) | [1, 2, 3] (values 2, 4, 7) | spread 5 > 4: left -> 2, min_dq drops 1 -> [2, 3] | 2 |
| 1 | max_dq, min_dq = deque(), deque() |
| 2 | left = 0 |
| 3 | best = 0 |
| 4 | for right in range(len(nums)): |
| 5 | while max_dq and nums[max_dq[-1]] <= nums[right]: |
| 6 | max_dq.pop() |
| 7 | max_dq.append(right) |
| 8 | while min_dq and nums[min_dq[-1]] >= nums[right]: |
| 9 | min_dq.pop() |
| 10 | min_dq.append(right) |
| 11 | while nums[max_dq[0]] - nums[min_dq[0]] > limit: |
| 12 | left += 1 |
| 13 | if max_dq[0] < left: max_dq.popleft() |
| 14 | if min_dq[0] < left: min_dq.popleft() |
| 15 | best = max(best, right - left + 1) |
| 16 | return best |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The Monotonic Deque card gives a window's maximum (or its minimum) in O(1) per step. This problem needs both the maximum and the minimum of the same window at once, because the window is only valid while they stay within limit of each other. Running one deque of each kind side by side, over the same two pointers, answers both questions together without rescanning the window.
⚖️ The Analogy: Two Leaderboards, Tallest and Shortest, Watching the Same Room
Keep two leaderboards for the same room of people: one for "tallest so far," one for "shortest so far," exactly like the single-deque leaderboard, run twice. Every time someone new walks in, both leaderboards update by their own rule. When someone leaves (the window shrinks), each leaderboard must check its own front on its own: the tallest-so-far leaderboard might still have a current leader standing in the room, while the shortest-so-far leaderboard's current leader already walked out. Checking only one leaderboard when someone leaves means the other can keep naming someone who isn't there anymore.
🔑 The Key Idea in the Code
nums[max_dq[0]] - nums[min_dq[0]] is the window's exact spread, read with no scan. While that spread is greater than limit, left moves forward one step, and both if max_dq[0] < left and if min_dq[0] < left run every time, because each deque only knows about the indices it has personally evicted.
Shrinking checks only
max_dq's stale front, nevermin_dq'sWriting
>=instead of<=when poppingmax_dq's backEvicting a stale front on
<=instead of<Storing values instead of indices in
max_dqandmin_dq
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks about every pair of elements inside a subarray, which is the same as its maximum minus its minimum. The window's validity depends on both running extremes at once, which a single Monotonic Deque cannot answer, since it only tracks one side.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision at each right: keep max_dq strictly decreasing and min_dq strictly increasing, then while nums[max_dq[0]] - nums[min_dq[0]] > limit, move left forward and check max_dq[0] < left and min_dq[0] < left separately before recording right - left + 1.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
if max_dq[0] < left: ... if min_dq[0] < left: ...: both checks run on every shrink step, never only one (gotcha 1 has the failing input).while max_dq and nums[max_dq[-1]] <= nums[right]:: keep the<=direction for the max deque,>=for the min deque, never swapped (gotcha 2).if max_dq[0] < left:: strictly<, not<=, since indexleftitself is still inside the window (gotcha 3).
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'll use a Dual Monotonic Deque. I run two Monotonic Deques over the same window: max_dq strictly decreasing, so its front is the window's maximum, and min_dq strictly increasing, so its front is the window's minimum. For each right, I push right onto both deques after popping whatever it dominates. Then, while the window's spread, nums of max_dq's front minus nums of min_dq's front, is over the limit, I move left forward one step and check both fronts on their own: if max_dq's front fell behind left I pop it, and separately if min_dq's front fell behind left I pop it. The trap is checking only one of those two: each deque only evicts what it has itself checked, so one front can go stale before the other. After the window is valid again, I record right minus left plus one as a candidate length. Every index is pushed into each deque once and popped at most once, so it's
O(N)time andO(N)space for the two deques."
Complexity & Mathematical Proof
O(N)
Look at the code: for right in range(len(nums)) runs N times. Inside it, max_dq.append(right) and min_dq.append(right) are one push each, and the two while loops that pop from their backs (nums[max_dq[-1]] <= nums[right], nums[min_dq[-1]] >= nums[right]) can run many times in one step, but each pop removes an index that was appended earlier, and every index is appended exactly once into each deque, so across the whole run each deque's back pops total at most N. The shrink loop while nums[max_dq[0]] - nums[min_dq[0]] > limit moves left forward; left only increases and never exceeds right, and each of its if max_dq[0] < left / if min_dq[0] < left pops an index from the front of its own deque at most once, so these front pops also total at most N each across the whole run. Adding up: N pushes and at most N back-pops per deque, plus at most N front-pops per deque from the shrink loop: O(N) total, not O(N) per deque doubled into something larger, since every bound here is already linear in N.
O(N)
Look at the allocations: max_dq and min_dq each hold only indices still inside the window nums[left..right], so together they never exceed 2N entries, still O(N). There is no recursion, and the answer best is one integer.
Derivation Progression
for right in range(len(nums)): N passes, each pushing once into max_dq and once into min_dq
Everything outside the two inner while loops and the shrink loop costs a constant amount per index.
total max_dq.pop() <= total max_dq.append(right) = N; same bound for min_dq
An index can only be popped from a deque's back after it was appended to that same deque, and each index is appended once per deque, so each deque's inner while pops at most N times across all passes together.
total max_dq.popleft() + total min_dq.popleft() <= N, since left only increases and left <= right <= N
left starts at 0 and only increases, and it never exceeds right, so it increases at most N times across the whole run; each increase pops at most one index from each deque's front.
2N + 2N + 2N = O(N)
Appends, back pops and front pops on both deques together add up to a constant times N.
Variable Definitions
len(nums), the number of values
Memory Architecture & Bounds
O(1): no recursion
O(N): max_dq and min_dq together hold at most 2N indices inside the current window
O(1): best, a single integer
Boundary Best / Worst Cases
: every value equal, nothing is ever popped from either deque's back, and the window never has to shrink
: an alternating high-low pattern, where every new value pops something from one deque's back and the window must shrink often
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "every pair of elements in this subarray", "absolute difference... less than or equal to limit". The window's validity depends on both its maximum and its minimum at once: two Monotonic Deques, one of each kind, not a single deque and not a heap of pairs.
, values in . Checking every pair inside a candidate subarray is in the worst case; a shrinking window with two deques is , since each index is pushed once into each deque and popped from it at most once.
THE SHARED-SHRINK TRAP: when the window shrinks, each deque's front is checked on its own if, never only one of them, because a deque only evicts the indices it has itself checked; skipping one check leaves a stale front that no longer belongs to the window.
Core Algorithmic State Invariants
- Two Deques, Two Independent Fronts
max_dq and min_dq each run the same Monotonic Deque rule on their own side, so each deque only ever evicts the indices it has itself checked. One deque's front can fall behind left before the other's does, which is why the shrink loop tests max_dq[0] and min_dq[0] separately, on every step, instead of assuming one check covers both.
- The Window's Spread, Read Without a Scan
nums[max_dq[0]] - nums[min_dq[0]] is the window's exact maximum minus its exact minimum, because both fronts are kept current by the same rule that keeps a single Monotonic Deque's front current. No element of the window is ever re-read to compute this.
Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (LeetCode 1438)
Take the integer array nums and an integer limit. Look for the longest non-empty contiguous run of nums (a subarray) in which every pair of elements inside the run differs by at most limit.
Equivalently, the run's largest value minus its smallest value must be at most limit. Return the length of the longest such run.
Worked Examples
nums = [8,2,4,7], limit = 42nums = [10,1,2,4,7,2], limit = 54⚖️Formal Constraints & Bounds
1 <= nums.length <= 1051 <= nums[i] <= 1090 <= limit <= 109
Core Insight
Two deques read the same window side by side: max_dq strictly decreasing gives the window's maximum at its front, min_dq strictly increasing gives the minimum at its front, so nums[max_dq[0]] - nums[min_dq[0]] is the window's exact spread with no rescan. Shrinking the window checks both fronts on every step, because each deque only evicts the indices it has itself checked.
Real-World Scenario & Production Applications
Alerting systems that only fire while a sensor or price feed's recent range (its maximum minus its minimum) stays inside a tolerance band, such as a thermostat's calm range or a trading band that should not fire on ordinary noise.
Subproblems & Recurrence Decomposition3 Phases
max_dq pops every value <= nums[right] from the back, so its values strictly decrease. min_dq pops every value >= nums[right] from the back, so its values strictly increase. Each rule is the single-deque Monotonic Deque rule, run on its own side.
while max_dq and nums[max_dq[-1]] <= nums[right]:
max_dq.pop()
max_dq.append(right)
while min_dq and nums[min_dq[-1]] >= nums[right]:
min_dq.pop()
min_dq.append(right)Step-by-Step Execution Trace Table
right | nums[right] | max_dq after push | min_dq after push | Shrink while spread > limit | best |
|---|---|---|---|---|---|
| 0 | 8 | [0] (values 8) | [0] (values 8) | spread 0, no shrink | 1 |
| 1 | 2 | [0, 1] (values 8, 2) | [1] (pops 0: 8 >= 2) | spread 6 > 4: left -> 1, max_dq drops 0 -> [1] | 1 |
| 2 | 4 | [2] (pops 1: 2 <= 4) | [1, 2] (values 2, 4) | spread 2, no shrink | 2 |
| 3 | 7 | [3] (pops 2: 4 <= 7) | [1, 2, 3] (values 2, 4, 7) | spread 5 > 4: left -> 2, min_dq drops 1 -> [2, 3] | 2 |
| 1 | max_dq, min_dq = deque(), deque() |
| 2 | left = 0 |
| 3 | best = 0 |
| 4 | for right in range(len(nums)): |
| 5 | while max_dq and nums[max_dq[-1]] <= nums[right]: |
| 6 | max_dq.pop() |
| 7 | max_dq.append(right) |
| 8 | while min_dq and nums[min_dq[-1]] >= nums[right]: |
| 9 | min_dq.pop() |
| 10 | min_dq.append(right) |
| 11 | while nums[max_dq[0]] - nums[min_dq[0]] > limit: |
| 12 | left += 1 |
| 13 | if max_dq[0] < left: max_dq.popleft() |
| 14 | if min_dq[0] < left: min_dq.popleft() |
| 15 | best = max(best, right - left + 1) |
| 16 | return best |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The Monotonic Deque card gives a window's maximum (or its minimum) in O(1) per step. This problem needs both the maximum and the minimum of the same window at once, because the window is only valid while they stay within limit of each other. Running one deque of each kind side by side, over the same two pointers, answers both questions together without rescanning the window.
⚖️ The Analogy: Two Leaderboards, Tallest and Shortest, Watching the Same Room
Keep two leaderboards for the same room of people: one for "tallest so far," one for "shortest so far," exactly like the single-deque leaderboard, run twice. Every time someone new walks in, both leaderboards update by their own rule. When someone leaves (the window shrinks), each leaderboard must check its own front on its own: the tallest-so-far leaderboard might still have a current leader standing in the room, while the shortest-so-far leaderboard's current leader already walked out. Checking only one leaderboard when someone leaves means the other can keep naming someone who isn't there anymore.
🔑 The Key Idea in the Code
nums[max_dq[0]] - nums[min_dq[0]] is the window's exact spread, read with no scan. While that spread is greater than limit, left moves forward one step, and both if max_dq[0] < left and if min_dq[0] < left run every time, because each deque only knows about the indices it has personally evicted.
Shrinking checks only
max_dq's stale front, nevermin_dq'sWriting
>=instead of<=when poppingmax_dq's backEvicting a stale front on
<=instead of<Storing values instead of indices in
max_dqandmin_dq
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks about every pair of elements inside a subarray, which is the same as its maximum minus its minimum. The window's validity depends on both running extremes at once, which a single Monotonic Deque cannot answer, since it only tracks one side.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision at each right: keep max_dq strictly decreasing and min_dq strictly increasing, then while nums[max_dq[0]] - nums[min_dq[0]] > limit, move left forward and check max_dq[0] < left and min_dq[0] < left separately before recording right - left + 1.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
if max_dq[0] < left: ... if min_dq[0] < left: ...: both checks run on every shrink step, never only one (gotcha 1 has the failing input).while max_dq and nums[max_dq[-1]] <= nums[right]:: keep the<=direction for the max deque,>=for the min deque, never swapped (gotcha 2).if max_dq[0] < left:: strictly<, not<=, since indexleftitself is still inside the window (gotcha 3).
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'll use a Dual Monotonic Deque. I run two Monotonic Deques over the same window: max_dq strictly decreasing, so its front is the window's maximum, and min_dq strictly increasing, so its front is the window's minimum. For each right, I push right onto both deques after popping whatever it dominates. Then, while the window's spread, nums of max_dq's front minus nums of min_dq's front, is over the limit, I move left forward one step and check both fronts on their own: if max_dq's front fell behind left I pop it, and separately if min_dq's front fell behind left I pop it. The trap is checking only one of those two: each deque only evicts what it has itself checked, so one front can go stale before the other. After the window is valid again, I record right minus left plus one as a candidate length. Every index is pushed into each deque once and popped at most once, so it's
O(N)time andO(N)space for the two deques."
Complexity & Mathematical Proof
O(N)
Look at the code: for right in range(len(nums)) runs N times. Inside it, max_dq.append(right) and min_dq.append(right) are one push each, and the two while loops that pop from their backs (nums[max_dq[-1]] <= nums[right], nums[min_dq[-1]] >= nums[right]) can run many times in one step, but each pop removes an index that was appended earlier, and every index is appended exactly once into each deque, so across the whole run each deque's back pops total at most N. The shrink loop while nums[max_dq[0]] - nums[min_dq[0]] > limit moves left forward; left only increases and never exceeds right, and each of its if max_dq[0] < left / if min_dq[0] < left pops an index from the front of its own deque at most once, so these front pops also total at most N each across the whole run. Adding up: N pushes and at most N back-pops per deque, plus at most N front-pops per deque from the shrink loop: O(N) total, not O(N) per deque doubled into something larger, since every bound here is already linear in N.
O(N)
Look at the allocations: max_dq and min_dq each hold only indices still inside the window nums[left..right], so together they never exceed 2N entries, still O(N). There is no recursion, and the answer best is one integer.
Derivation Progression
for right in range(len(nums)): N passes, each pushing once into max_dq and once into min_dq
Everything outside the two inner while loops and the shrink loop costs a constant amount per index.
total max_dq.pop() <= total max_dq.append(right) = N; same bound for min_dq
An index can only be popped from a deque's back after it was appended to that same deque, and each index is appended once per deque, so each deque's inner while pops at most N times across all passes together.
total max_dq.popleft() + total min_dq.popleft() <= N, since left only increases and left <= right <= N
left starts at 0 and only increases, and it never exceeds right, so it increases at most N times across the whole run; each increase pops at most one index from each deque's front.
2N + 2N + 2N = O(N)
Appends, back pops and front pops on both deques together add up to a constant times N.
Variable Definitions
len(nums), the number of values
Memory Architecture & Bounds
O(1): no recursion
O(N): max_dq and min_dq together hold at most 2N indices inside the current window
O(1): best, a single integer
Boundary Best / Worst Cases
: every value equal, nothing is ever popped from either deque's back, and the window never has to shrink
: an alternating high-low pattern, where every new value pops something from one deque's back and the window must shrink often
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "every pair of elements in this subarray", "absolute difference... less than or equal to limit". The window's validity depends on both its maximum and its minimum at once: two Monotonic Deques, one of each kind, not a single deque and not a heap of pairs.
, values in . Checking every pair inside a candidate subarray is in the worst case; a shrinking window with two deques is , since each index is pushed once into each deque and popped from it at most once.
THE SHARED-SHRINK TRAP: when the window shrinks, each deque's front is checked on its own if, never only one of them, because a deque only evicts the indices it has itself checked; skipping one check leaves a stale front that no longer belongs to the window.
Core Algorithmic State Invariants
- Two Deques, Two Independent Fronts
max_dq and min_dq each run the same Monotonic Deque rule on their own side, so each deque only ever evicts the indices it has itself checked. One deque's front can fall behind left before the other's does, which is why the shrink loop tests max_dq[0] and min_dq[0] separately, on every step, instead of assuming one check covers both.
- The Window's Spread, Read Without a Scan
nums[max_dq[0]] - nums[min_dq[0]] is the window's exact maximum minus its exact minimum, because both fronts are kept current by the same rule that keeps a single Monotonic Deque's front current. No element of the window is ever re-read to compute this.