Facebook Pixel

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

MediumQueueArrayOrdered SetSliding WindowMonotonic QueueHeap (Priority Queue)
Leetcode Link

Problem Description

You are given an array of integers nums and an integer value limit. Your task is to find the length of the longest contiguous subarray where the absolute difference between any two elements within that subarray is at most limit.

In other words, if you pick any subarray from the given array, and look at the maximum and minimum values in that subarray, their difference should not exceed limit. You need to find the maximum possible length of such a subarray.

For example, if nums = [8, 2, 4, 7] and limit = 4:

  • The subarray [2, 4] is valid because |4 - 2| = 2 ≤ 4
  • The subarray [2, 4, 7] is not valid because |7 - 2| = 5 > 4
  • The longest valid subarray would be [2, 4] with length 2

The solution uses a sliding window approach with a sorted list to efficiently track the minimum and maximum values in the current window. As we expand the window by adding elements from the right, we check if the difference between the maximum and minimum exceeds limit. If it does, we shrink the window from the left until the condition is satisfied again. The sorted list allows us to quickly access the minimum (sl[0]) and maximum (sl[-1]) values in the current window.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is that for any valid subarray, the condition that matters is the difference between the maximum and minimum elements. If max - min ≤ limit, then all pairwise differences within that subarray will also be at most limit.

This observation leads us to think about a sliding window approach. We can expand our window to include more elements as long as the condition holds, and shrink it when the condition breaks. The challenge is efficiently tracking the maximum and minimum values as our window changes.

Why sliding window works here: Once we fix the right endpoint of our subarray at position i, we want to find the leftmost valid left endpoint j. If we move to the next right endpoint i+1, the optimal left endpoint can only stay the same or move to the right (it never moves left). This monotonic property makes sliding window perfect for this problem.

To efficiently maintain the max and min values in our current window, we need a data structure that:

  1. Allows us to insert elements when expanding the window
  2. Allows us to remove specific elements when shrinking the window
  3. Gives us quick access to both the minimum and maximum values

A sorted list (or balanced BST) fits these requirements perfectly. It maintains elements in sorted order, so the first element sl[0] is always the minimum and the last element sl[-1] is always the maximum. Both insertion and removal operations are O(log n), making the overall solution efficient.

The algorithm naturally flows: keep expanding the window by adding elements, and whenever max - min > limit, shrink from the left until the condition is satisfied again. Track the maximum window size seen during this process.

Learn more about Queue, Sliding Window, Monotonic Queue and Heap (Priority Queue) patterns.

Solution Approach

The solution implements a sliding window technique with an ordered set to maintain the maximum and minimum values within the current window.

Data Structure Choice: We use a SortedList (from Python's sortedcontainers module) which maintains elements in sorted order. This gives us:

  • O(log n) insertion with sl.add(x)
  • O(log n) removal with sl.remove(x)
  • O(1) access to minimum (sl[0]) and maximum (sl[-1]) values

Algorithm Steps:

  1. Initialize variables:

    • sl = SortedList() - to maintain sorted elements in current window
    • ans = 0 - to track the maximum subarray length found
    • j = 0 - left pointer of the sliding window

  2. Expand window (right pointer):

    • Iterate through the array with index i and value x
    • Add current element to the sorted list: sl.add(x)

  3. Shrink window when constraint violated:

    • While the difference between max and min exceeds limit: sl[-1] - sl[0] > limit
    • Remove the leftmost element from sorted list: sl.remove(nums[j])
    • Move left pointer right: j += 1

  4. Update maximum length:

    • After ensuring the window is valid, calculate current window size: i - j + 1
    • Update answer if current window is larger: ans = max(ans, i - j + 1)

Time Complexity: O(n log n) where n is the length of the array. Each element is added and removed at most once, and each operation on the sorted list takes O(log n) time.

Space Complexity: O(n) in the worst case when all elements form a valid subarray and are stored in the sorted list.

The sliding window naturally finds the longest valid subarray ending at each position, and the maximum among all these lengths is our answer.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the algorithm with nums = [10, 1, 2, 4, 7, 2] and limit = 5.

Initial State:

  • sl = [] (empty sorted list)
  • ans = 0 (max length found)
  • j = 0 (left pointer)

Step 1: i = 0, x = 10

  • Add 10 to sl: sl = [10]
  • Check: max - min = 10 - 10 = 0 ≤ 5 ✓
  • Window = [10], length = 1
  • Update: ans = 1

Step 2: i = 1, x = 1

  • Add 1 to sl: sl = [1, 10]
  • Check: max - min = 10 - 1 = 9 > 5 ✗
  • Need to shrink! Remove nums[0] = 10: sl = [1], j = 1
  • Now: max - min = 1 - 1 = 0 ≤ 5 ✓
  • Window = [1], length = 1
  • ans remains 1

Step 3: i = 2, x = 2

  • Add 2 to sl: sl = [1, 2]
  • Check: max - min = 2 - 1 = 1 ≤ 5 ✓
  • Window = [1, 2], length = 2
  • Update: ans = 2

Step 4: i = 3, x = 4

  • Add 4 to sl: sl = [1, 2, 4]
  • Check: max - min = 4 - 1 = 3 ≤ 5 ✓
  • Window = [1, 2, 4], length = 3
  • Update: ans = 3

Step 5: i = 4, x = 7

  • Add 7 to sl: sl = [1, 2, 4, 7]
  • Check: max - min = 7 - 1 = 6 > 5 ✗
  • Need to shrink! Remove nums[1] = 1: sl = [2, 4, 7], j = 2
  • Check: max - min = 7 - 2 = 5 ≤ 5 ✓
  • Window = [2, 4, 7], length = 3
  • ans remains 3

Step 6: i = 5, x = 2

  • Add 2 to sl: sl = [2, 2, 4, 7]
  • Check: max - min = 7 - 2 = 5 ≤ 5 ✓
  • Window = [2, 4, 7, 2], length = 4
  • Update: ans = 4

Final Answer: 4 (The longest valid subarray is [2, 4, 7, 2] with max - min = 7 - 2 = 5)

Solution Implementation

1from sortedcontainers import SortedList
2from typing import List
3
4class Solution:
5    def longestSubarray(self, nums: List[int], limit: int) -> int:
6        # Use a sorted list to maintain elements in the current window in sorted order
7        sorted_window = SortedList()
8      
9        # Initialize result and left pointer of sliding window
10        max_length = 0
11        left = 0
12      
13        # Iterate through array with right pointer
14        for right, num in enumerate(nums):
15            # Add current element to the sorted window
16            sorted_window.add(num)
17          
18            # Shrink window from left while difference between max and min exceeds limit
19            while sorted_window[-1] - sorted_window[0] > limit:
20                # Remove the leftmost element from sorted window
21                sorted_window.remove(nums[left])
22                # Move left pointer forward
23                left += 1
24          
25            # Update maximum length found so far
26            max_length = max(max_length, right - left + 1)
27      
28        return max_length
29
1class Solution {
2    public int longestSubarray(int[] nums, int limit) {
3        // TreeMap to maintain elements in the current window sorted by value
4        // Key: element value, Value: frequency count
5        TreeMap<Integer, Integer> windowElements = new TreeMap<>();
6      
7        // Variable to store the maximum length of valid subarray
8        int maxLength = 0;
9      
10        // Sliding window approach with left pointer at j and right pointer at i
11        int left = 0;
12      
13        for (int right = 0; right < nums.length; right++) {
14            // Add current element to the window
15            // Increment its frequency count or set to 1 if new
16            windowElements.merge(nums[right], 1, Integer::sum);
17          
18            // Shrink window from left while the difference between max and min exceeds limit
19            while (windowElements.lastKey() - windowElements.firstKey() > limit) {
20                // Remove the leftmost element from the window
21                // Decrement its frequency count
22                if (windowElements.merge(nums[left], -1, Integer::sum) == 0) {
23                    // If frequency becomes 0, remove the element completely from the map
24                    windowElements.remove(nums[left]);
25                }
26                // Move left pointer forward
27                left++;
28            }
29          
30            // Update maximum length with current valid window size
31            maxLength = Math.max(maxLength, right - left + 1);
32        }
33      
34        return maxLength;
35    }
36}
37
1class Solution {
2public:
3    int longestSubarray(vector<int>& nums, int limit) {
4        // Use multiset to maintain elements in current window in sorted order
5        // This allows O(log n) access to min and max elements
6        multiset<int> windowElements;
7      
8        int maxLength = 0;
9        int left = 0;  // Left pointer of sliding window
10      
11        // Iterate through array with right pointer
12        for (int right = 0; right < nums.size(); ++right) {
13            // Add current element to the window
14            windowElements.insert(nums[right]);
15          
16            // Shrink window from left while the difference between max and min exceeds limit
17            // *rbegin() gives maximum element, *begin() gives minimum element
18            while (*windowElements.rbegin() - *windowElements.begin() > limit) {
19                // Remove the leftmost element from window
20                // Use find() to remove only one occurrence of nums[left]
21                windowElements.erase(windowElements.find(nums[left]));
22                left++;
23            }
24          
25            // Update maximum length of valid subarray found so far
26            // Current window size is (right - left + 1)
27            maxLength = max(maxLength, right - left + 1);
28        }
29      
30        return maxLength;
31    }
32};
33
1/**
2 * Finds the longest subarray where the difference between max and min elements doesn't exceed the limit
3 * Uses a sliding window approach with a balanced BST (Treap) to track min/max efficiently
4 * @param nums - Input array of numbers
5 * @param limit - Maximum allowed difference between max and min elements
6 * @returns Length of the longest valid subarray
7 */
8function longestSubarray(nums: number[], limit: number): number {
9    const treapSet = new TreapMultiSet<number>();
10    let maxLength = 0;
11    let leftPointer = 0;
12  
13    // Sliding window: expand with right pointer, contract with left pointer
14    for (let rightPointer = 0; rightPointer < nums.length; rightPointer++) {
15        treapSet.add(nums[rightPointer]);
16      
17        // Contract window while difference exceeds limit
18        while (treapSet.last()! - treapSet.first()! > limit) {
19            treapSet.delete(nums[leftPointer]);
20            leftPointer++;
21        }
22      
23        // Update maximum length found
24        maxLength = Math.max(maxLength, rightPointer - leftPointer + 1);
25    }
26  
27    return maxLength;
28}
29
30/**
31 * Generic comparison function type
32 * @template T - Type of elements being compared
33 * @template R - Return type ('number' for numeric comparison, 'boolean' for boolean)
34 */
35type CompareFunction<T, R extends 'number' | 'boolean'> = (
36    a: T,
37    b: T,
38) => R extends 'number' ? number : boolean;
39
40/**
41 * Interface for a Treap-based multiset (allows duplicate elements)
42 * Provides balanced BST operations with O(log n) complexity
43 */
44interface ITreapMultiSet<T> extends Iterable<T> {
45    // Core operations
46    add: (...values: T[]) => this;
47    has: (value: T) => boolean;
48    delete: (value: T) => void;
49  
50    // Binary search operations
51    bisectLeft: (value: T) => number;
52    bisectRight: (value: T) => number;
53  
54    // Index-based operations
55    indexOf: (value: T) => number;
56    lastIndexOf: (value: T) => number;
57    at: (index: number) => T | undefined;
58  
59    // Min/max operations
60    first: () => T | undefined;
61    last: () => T | undefined;
62  
63    // Predecessor/successor operations
64    lower: (value: T) => T | undefined;
65    higher: (value: T) => T | undefined;
66    floor: (value: T) => T | undefined;
67    ceil: (value: T) => T | undefined;
68  
69    // Queue-like operations
70    shift: () => T | undefined;
71    pop: (index?: number) => T | undefined;
72  
73    // Utility operations
74    count: (value: T) => number;
75    keys: () => IterableIterator<T>;
76    values: () => IterableIterator<T>;
77    rvalues: () => IterableIterator<T>;
78    entries: () => IterableIterator<[number, T]>;
79  
80    readonly size: number;
81}
82
83/**
84 * Node class for Treap data structure
85 * Combines BST properties with heap priority for balancing
86 */
87class TreapNode<T = number> {
88    value: T;                    // The stored value
89    count: number;               // Number of occurrences of this value
90    size: number;                // Total nodes in subtree (including duplicates)
91    priority: number;            // Random priority for heap property
92    left: TreapNode<T> | null;  // Left child
93    right: TreapNode<T> | null; // Right child
94
95    constructor(value: T) {
96        this.value = value;
97        this.count = 1;
98        this.size = 1;
99        this.priority = Math.random();
100        this.left = null;
101        this.right = null;
102    }
103
104    /**
105     * Gets the size of a node's subtree (handles null nodes)
106     */
107    static getSize(node: TreapNode<any> | null): number {
108        return node?.size ?? 0;
109    }
110
111    /**
112     * Gets the priority factor of a node (handles null nodes)
113     */
114    static getFac(node: TreapNode<any> | null): number {
115        return node?.priority ?? 0;
116    }
117
118    /**
119     * Updates the size of current node based on children and count
120     */
121    pushUp(): void {
122        let totalSize = this.count;
123        totalSize += TreapNode.getSize(this.left);
124        totalSize += TreapNode.getSize(this.right);
125        this.size = totalSize;
126    }
127
128    /**
129     * Performs right rotation to maintain heap property
130     * @returns New root after rotation
131     */
132    rotateRight(): TreapNode<T> {
133        let newRoot: TreapNode<T> = this;
134        const leftChild = newRoot.left;
135        newRoot.left = leftChild?.right ?? null;
136      
137        if (leftChild) {
138            leftChild.right = newRoot;
139            newRoot = leftChild;
140        }
141      
142        newRoot.right?.pushUp();
143        newRoot.pushUp();
144        return newRoot;
145    }
146
147    /**
148     * Performs left rotation to maintain heap property
149     * @returns New root after rotation
150     */
151    rotateLeft(): TreapNode<T> {
152        let newRoot: TreapNode<T> = this;
153        const rightChild = newRoot.right;
154        newRoot.right = rightChild?.left ?? null;
155      
156        if (rightChild) {
157            rightChild.left = newRoot;
158            newRoot = rightChild;
159        }
160      
161        newRoot.left?.pushUp();
162        newRoot.pushUp();
163        return newRoot;
164    }
165}
166
167/**
168 * Treap-based multiset implementation
169 * Provides O(log n) operations for sorted set with duplicates
170 */
171class TreapMultiSet<T = number> implements ITreapMultiSet<T> {
172    private readonly root: TreapNode<T>;
173    private readonly compareFn: CompareFunction<T, 'number'>;
174    private readonly leftBound: T;   // Sentinel for minimum boundary
175    private readonly rightBound: T;  // Sentinel for maximum boundary
176
177    constructor(compareFn?: CompareFunction<T, 'number'>);
178    constructor(compareFn: CompareFunction<T, 'number'>, leftBound: T, rightBound: T);
179    constructor(
180        compareFn: CompareFunction<T, any> = (a: any, b: any) => a - b,
181        leftBound: any = -Infinity,
182        rightBound: any = Infinity,
183    ) {
184        // Initialize root with right sentinel (infinite priority)
185        this.root = new TreapNode<T>(rightBound);
186        this.root.priority = Infinity;
187      
188        // Add left sentinel as left child (negative infinite priority)
189        this.root.left = new TreapNode<T>(leftBound);
190        this.root.left.priority = -Infinity;
191        this.root.pushUp();
192
193        this.leftBound = leftBound;
194        this.rightBound = rightBound;
195        this.compareFn = compareFn;
196    }
197
198    /**
199     * Returns the number of elements in the set (excluding sentinels)
200     */
201    get size(): number {
202        return this.root.size - 2;
203    }
204
205    /**
206     * Returns the height of the treap tree
207     */
208    get height(): number {
209        const getHeight = (node: TreapNode<T> | null): number => {
210            if (node == null) return 0;
211            return 1 + Math.max(getHeight(node.left), getHeight(node.right));
212        };
213        return getHeight(this.root);
214    }
215
216    /**
217     * Checks if a value exists in the set
218     * @complexity O(log n)
219     */
220    has(value: T): boolean {
221        const compare = this.compareFn;
222      
223        const search = (node: TreapNode<T> | null, target: T): boolean => {
224            if (node == null) return false;
225          
226            const comparison = compare(node.value, target);
227            if (comparison === 0) return true;
228            if (comparison < 0) return search(node.right, target);
229            return search(node.left, target);
230        };
231
232        return search(this.root, value);
233    }
234
235    /**
236     * Adds one or more values to the sorted set
237     * @complexity O(log n) per value
238     */
239    add(...values: T[]): this {
240        const compare = this.compareFn;
241      
242        const insert = (
243            node: TreapNode<T> | null,
244            value: T,
245            parent: TreapNode<T>,
246            direction: 'left' | 'right',
247        ): void => {
248            if (node == null) return;
249          
250            const comparison = compare(node.value, value);
251          
252            if (comparison === 0) {
253                // Value exists, increment count
254                node.count++;
255                node.pushUp();
256            } else if (comparison > 0) {
257                // Go left
258                if (node.left) {
259                    insert(node.left, value, node, 'left');
260                } else {
261                    node.left = new TreapNode(value);
262                    node.pushUp();
263                }
264              
265                // Maintain heap property via rotation
266                if (TreapNode.getFac(node.left) > node.priority) {
267                    parent[direction] = node.rotateRight();
268                }
269            } else {
270                // Go right
271                if (node.right) {
272                    insert(node.right, value, node, 'right');
273                } else {
274                    node.right = new TreapNode(value);
275                    node.pushUp();
276                }
277              
278                // Maintain heap property via rotation
279                if (TreapNode.getFac(node.right) > node.priority) {
280                    parent[direction] = node.rotateLeft();
281                }
282            }
283          
284            parent.pushUp();
285        };
286
287        values.forEach(value => insert(this.root.left, value, this.root, 'left'));
288        return this;
289    }
290
291    /**
292     * Removes a value from the set
293     * @complexity O(log n)
294     */
295    delete(value: T): void {
296        const compare = this.compareFn;
297      
298        const remove = (
299            node: TreapNode<T> | null,
300            value: T,
301            parent: TreapNode<T>,
302            direction: 'left' | 'right',
303        ): void => {
304            if (node == null) return;
305
306            const comparison = compare(node.value, value);
307          
308            if (comparison === 0) {
309                if (node.count > 1) {
310                    // Multiple occurrences, just decrement
311                    node.count--;
312                    node.pushUp();
313                } else if (node.left == null && node.right == null) {
314                    // Leaf node, remove directly
315                    parent[direction] = null;
316                } else {
317                    // Rotate node down to leaf position
318                    if (node.right == null || 
319                        TreapNode.getFac(node.left) > TreapNode.getFac(node.right)) {
320                        parent[direction] = node.rotateRight();
321                        remove(parent[direction]?.right ?? null, value, parent[direction]!, 'right');
322                    } else {
323                        parent[direction] = node.rotateLeft();
324                        remove(parent[direction]?.left ?? null, value, parent[direction]!, 'left');
325                    }
326                }
327            } else if (comparison > 0) {
328                remove(node.left, value, node, 'left');
329            } else {
330                remove(node.right, value, node, 'right');
331            }
332
333            parent?.pushUp();
334        };
335
336        remove(this.root.left, value, this.root, 'left');
337    }
338
339    /**
340     * Returns insertion index for value (leftmost position)
341     * @complexity O(log n)
342     */
343    bisectLeft(value: T): number {
344        const compare = this.compareFn;
345      
346        const findIndex = (node: TreapNode<T> | null, target: T): number => {
347            if (node == null) return 0;
348
349            const comparison = compare(node.value, target);
350          
351            if (comparison === 0) {
352                return TreapNode.getSize(node.left);
353            } else if (comparison > 0) {
354                return findIndex(node.left, target);
355            } else {
356                return findIndex(node.right, target) + 
357                       TreapNode.getSize(node.left) + node.count;
358            }
359        };
360
361        return findIndex(this.root, value) - 1;
362    }
363
364    /**
365     * Returns insertion index for value (rightmost position)
366     * @complexity O(log n)
367     */
368    bisectRight(value: T): number {
369        const compare = this.compareFn;
370      
371        const findIndex = (node: TreapNode<T> | null, target: T): number => {
372            if (node == null) return 0;
373
374            const comparison = compare(node.value, target);
375          
376            if (comparison === 0) {
377                return TreapNode.getSize(node.left) + node.count;
378            } else if (comparison > 0) {
379                return findIndex(node.left, target);
380            } else {
381                return findIndex(node.right, target) + 
382                       TreapNode.getSize(node.left) + node.count;
383            }
384        };
385      
386        return findIndex(this.root, value) - 1;
387    }
388
389    /**
390     * Returns the index of first occurrence of value, or -1 if not found
391     * @complexity O(log n)
392     */
393    indexOf(value: T): number {
394        const compare = this.compareFn;
395        let found = false;
396
397        const findIndex = (node: TreapNode<T> | null, target: T): number => {
398            if (node == null) return 0;
399
400            const comparison = compare(node.value, target);
401          
402            if (comparison === 0) {
403                found = true;
404                return TreapNode.getSize(node.left);
405            } else if (comparison > 0) {
406                return findIndex(node.left, target);
407            } else {
408                return findIndex(node.right, target) + 
409                       TreapNode.getSize(node.left) + node.count;
410            }
411        };
412      
413        const result = findIndex(this.root, value) - 1;
414        return found ? result : -1;
415    }
416
417    /**
418     * Returns the index of last occurrence of value, or -1 if not found
419     * @complexity O(log n)
420     */
421    lastIndexOf(value: T): number {
422        const compare = this.compareFn;
423        let found = false;
424
425        const findIndex = (node: TreapNode<T> | null, target: T): number => {
426            if (node == null) return 0;
427
428            const comparison = compare(node.value, target);
429          
430            if (comparison === 0) {
431                found = true;
432                return TreapNode.getSize(node.left) + node.count - 1;
433            } else if (comparison > 0) {
434                return findIndex(node.left, target);
435            } else {
436                return findIndex(node.right, target) + 
437                       TreapNode.getSize(node.left) + node.count;
438            }
439        };
440
441        const result = findIndex(this.root, value) - 1;
442        return found ? result : -1;
443    }
444
445    /**
446     * Returns element at specified index (supports negative indexing)
447     * @complexity O(log n)
448     */
449    at(index: number): T | undefined {
450        // Handle negative indexing
451        if (index < 0) index += this.size;
452        if (index < 0 || index >= this.size) return undefined;
453
454        const findByRank = (node: TreapNode<T> | null, rank: number): T | undefined => {
455            if (node == null) return undefined;
456
457            const leftSize = TreapNode.getSize(node.left);
458          
459            if (leftSize >= rank) {
460                return findByRank(node.left, rank);
461            } else if (leftSize + node.count >= rank) {
462                return node.value;
463            } else {
464                return findByRank(node.right, rank - leftSize - node.count);
465            }
466        };
467
468        const result = findByRank(this.root, index + 2);
469      
470        // Filter out sentinel values
471        return ([this.leftBound, this.rightBound] as any[]).includes(result) 
472            ? undefined 
473            : result;
474    }
475
476    /**
477     * Returns the largest element less than value
478     * @complexity O(log n)
479     */
480    lower(value: T): T | undefined {
481        const compare = this.compareFn;
482      
483        const findLower = (node: TreapNode<T> | null, target: T): T | undefined => {
484            if (node == null) return undefined;
485          
486            if (compare(node.value, target) >= 0) {
487                return findLower(node.left, target);
488            }
489
490            const rightResult = findLower(node.right, target);
491          
492            if (rightResult == null || compare(node.value, rightResult) > 0) {
493                return node.value;
494            }
495          
496            return rightResult;
497        };
498
499        const result = findLower(this.root, value) as any;
500        return result === this.leftBound ? undefined : result;
501    }
502
503    /**
504     * Returns the smallest element greater than value
505     * @complexity O(log n)
506     */
507    higher(value: T): T | undefined {
508        const compare = this.compareFn;
509      
510        const findHigher = (node: TreapNode<T> | null, target: T): T | undefined => {
511            if (node == null) return undefined;
512          
513            if (compare(node.value, target) <= 0) {
514                return findHigher(node.right, target);
515            }
516
517            const leftResult = findHigher(node.left, target);
518
519            if (leftResult == null || compare(node.value, leftResult) < 0) {
520                return node.value;
521            }
522          
523            return leftResult;
524        };
525
526        const result = findHigher(this.root, value) as any;
527        return result === this.rightBound ? undefined : result;
528    }
529
530    /**
531     * Returns the largest element less than or equal to value
532     * @complexity O(log n)
533     */
534    floor(value: T): T | undefined {
535        const compare = this.compareFn;
536      
537        const findFloor = (node: TreapNode<T> | null, target: T): T | undefined => {
538            if (node == null) return undefined;
539          
540            const comparison = compare(node.value, target);
541          
542            if (comparison === 0) return node.value;
543            if (comparison >= 0) return findFloor(node.left, target);
544
545            const rightResult = findFloor(node.right, target);
546          
547            if (rightResult == null || compare(node.value, rightResult) > 0) {
548                return node.value;
549            }
550          
551            return rightResult;
552        };
553
554        const result = findFloor(this.root, value) as any;
555        return result === this.leftBound ? undefined : result;
556    }
557
558    /**
559     * Returns the smallest element greater than or equal to value
560     * @complexity O(log n)
561     */
562    ceil(value: T): T | undefined {
563        const compare = this.compareFn;
564      
565        const findCeil = (node: TreapNode<T> | null, target: T): T | undefined => {
566            if (node == null) return undefined;
567          
568            const comparison = compare(node.value, target);
569          
570            if (comparison === 0) return node.value;
571            if (comparison <= 0) return findCeil(node.right, target);
572
573            const leftResult = findCeil(node.left, target);
574
575            if (leftResult == null || compare(node.value, leftResult) < 0) {
576                return node.value;
577            }
578          
579            return leftResult;
580        };
581
582        const result = findCeil(this.root, value) as any;
583        return result === this.rightBound ? undefined : result;
584    }
585
586    /**
587     * Returns the minimum element in the set
588     * @complexity O(log n)
589     */
590    first(): T | undefined {
591        const iterator = this.inOrder();
592        iterator.next(); // Skip left sentinel
593        const result = iterator.next().value;
594        return result === this.rightBound ? undefined : result;
595    }
596
597    /**
598     * Returns the maximum element in the set
599     * @complexity O(log n)
600     */
601    last(): T | undefined {
602        const iterator = this.reverseInOrder();
603        iterator.next(); // Skip right sentinel
604        const result = iterator.next().value;
605        return result === this.leftBound ? undefined : result;
606    }
607
608    /**
609     * Removes and returns the minimum element
610     * @complexity O(log n)
611     */
612    shift(): T | undefined {
613        const firstElement = this.first();
614        if (firstElement === undefined) return undefined;
615      
616        this.delete(firstElement);
617        return firstElement;
618    }
619
620    /**
621     * Removes and returns the maximum element (or element at index)
622     * @complexity O(log n)
623     */
624    pop(index?: number): T | undefined {
625        if (index == null) {
626            const lastElement = this.last();
627            if (lastElement === undefined) return undefined;
628          
629            this.delete(lastElement);
630            return lastElement;
631        }
632
633        const elementToDelete = this.at(index);
634        if (elementToDelete == null) return;
635      
636        this.delete(elementToDelete);
637        return elementToDelete;
638    }
639
640    /**
641     * Returns the number of occurrences of value
642     * @complexity O(log n)
643     */
644    count(value: T): number {
645        const compare = this.compareFn;
646      
647        const countOccurrences = (node: TreapNode<T> | null, target: T): number => {
648            if (node == null) return 0;
649          
650            const comparison = compare(node.value, target);
651          
652            if (comparison === 0) return node.count;
653            if (comparison < 0) return countOccurrences(node.right, target);
654            return countOccurrences(node.left, target);
655        };
656
657        return countOccurrences(this.root, value);
658    }
659
660    /**
661     * Iterator implementation
662     */
663    *[Symbol.iterator](): Generator<T, any, any> {
664        yield* this.values();
665    }
666
667    /**
668     * Returns an iterator of keys (same as values for set)
669     */
670    *keys(): Generator<T, any, any> {
671        yield* this.values();
672    }
673
674    /**
675     * Returns an iterator of values in sorted order
676     */
677    *values(): Generator<T, any, any> {
678        const iterator = this.inOrder();
679        iterator.next(); // Skip left sentinel
680      
681        const elementCount = this.size;
682        for (let i = 0; i < elementCount; i++) {
683            yield iterator.next().value;
684        }
685    }
686
687    /**
688     * Returns an iterator of values in reverse sorted order
689     */
690    *rvalues(): Generator<T, any, any> {
691        const iterator = this.reverseInOrder();
692        iterator.next(); // Skip right sentinel
693      
694        const elementCount = this.size;
695        for (let i = 0; i < elementCount; i++) {
696            yield iterator.next().value;
697        }
698    }
699
700    /**
701     * Returns an iterator of [index, value] pairs
702     */
703    *entries(): IterableIterator<[number, T]> {
704        const iterator = this.inOrder();
705        iterator.next(); // Skip left sentinel
706      
707        const elementCount = this.size;
708        for (let i = 0; i < elementCount; i++) {
709            yield [i, iterator.next().value];
710        }
711    }
712
713    /**
714     * In-order traversal generator (includes duplicates)
715     */
716    private *inOrder(currentRoot: TreapNode<T> | null = this.root): Generator<T, any, any> {
717        if (currentRoot == null) return;
718      
719        yield* this.inOrder(currentRoot.left);
720      
721        const occurrences = currentRoot.count;
722        for (let i = 0; i < occurrences; i++) {
723            yield currentRoot.value;
724        }
725      
726        yield* this.inOrder(currentRoot.right);
727    }
728
729    /**
730     * Reverse in-order traversal generator (includes duplicates)
731     */
732    private *reverseInOrder(currentRoot: TreapNode<T> | null = this.root): Generator<T, any, any> {
733        if (currentRoot == null) return;
734      
735        yield* this.reverseInOrder(currentRoot.right);
736      
737        const occurrences = currentRoot.count;
738        for (let i = 0; i < occurrences; i++) {
739            yield currentRoot.value;
740        }
741      
742        yield* this.reverseInOrder(currentRoot.left);
743    }
744}
745

Time and Space Complexity

The time complexity is O(n log n), where n is the length of the array nums. This is because:

  • The outer loop iterates through all n elements of the array
  • For each element, we perform an add operation on the SortedList, which takes O(log n) time
  • In the worst case, the while loop removes each element once throughout the entire execution, and each remove operation on SortedList takes O(log n) time
  • Since each element is added once and removed at most once, the total operations are at most 2n, each costing O(log n)
  • Therefore, the overall time complexity is O(n log n)

The space complexity is O(n). This is because:

  • The SortedList sl can contain at most n elements (in the case where all elements satisfy the limit condition and form a valid subarray)
  • No other data structures scale with the input size
  • Therefore, the space complexity is O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Regular List Instead of SortedList

Pitfall: A common mistake is trying to use a regular Python list and manually finding min/max values:

# INCORRECT APPROACH
def longestSubarray(self, nums: List[int], limit: int) -> int:
    window = []
    max_length = 0
    left = 0
  
    for right, num in enumerate(nums):
        window.append(num)
      
        # This is O(n) for each iteration!
        while max(window) - min(window) > limit:
            window.pop(0)  # Also inefficient O(n)
            left += 1
          
        max_length = max(max_length, right - left + 1)
  
    return max_length

Problem: Finding min/max in an unsorted list takes O(n) time for each check, leading to O(n²) overall complexity.

Solution: Use SortedList which maintains sorted order, giving O(1) access to min/max values.

2. Using Two Deques for Min/Max Tracking

Pitfall: While using two deques (one for minimum, one for maximum) is a valid approach, it's more complex and error-prone:

# MORE COMPLEX ALTERNATIVE
from collections import deque

def longestSubarray(self, nums: List[int], limit: int) -> int:
    min_deque = deque()  # Stores indices in increasing order of values
    max_deque = deque()  # Stores indices in decreasing order of values
    left = 0
    max_length = 0
  
    for right in range(len(nums)):
        # Maintain decreasing order in max_deque
        while max_deque and nums[max_deque[-1]] <= nums[right]:
            max_deque.pop()
        max_deque.append(right)
      
        # Maintain increasing order in min_deque
        while min_deque and nums[min_deque[-1]] >= nums[right]:
            min_deque.pop()
        min_deque.append(right)
      
        # Remove outdated indices
        while max_deque and max_deque[0] < left:
            max_deque.popleft()
        while min_deque and min_deque[0] < left:
            min_deque.popleft()
      
        # Check constraint
        while nums[max_deque[0]] - nums[min_deque[0]] > limit:
            left += 1
            # Need to check and remove outdated indices again
            while max_deque and max_deque[0] < left:
                max_deque.popleft()
            while min_deque and min_deque[0] < left:
                min_deque.popleft()
      
        max_length = max(max_length, right - left + 1)
  
    return max_length

Problem: Managing two deques requires careful handling of indices, maintaining monotonic properties, and removing outdated elements. This increases code complexity and potential for bugs.

Solution: The SortedList approach is cleaner and more intuitive - just add/remove elements and check min/max directly.

3. Forgetting to Import SortedList

Pitfall: The SortedList is not a built-in Python data structure:

# INCORRECT - Will raise NameError
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        sorted_window = SortedList()  # NameError: name 'SortedList' is not defined

Solution: Always include the import statement:

from sortedcontainers import SortedList

Note: In competitive programming platforms like LeetCode, sortedcontainers is usually available. If not available, you'd need to implement using alternative approaches like the two-deque method or a balanced BST.

4. Off-by-One Error in Window Size Calculation

Pitfall: Calculating window size incorrectly:

# INCORRECT
max_length = max(max_length, right - left)  # Missing +1

Solution: The correct window size for indices [left, right] inclusive is right - left + 1.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

Queue Intro

Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real

Sliding Window Maximum

https assets algo monster cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in the window The window

Monotonic Stack/Queue Intro

Monotonic Stack Deque Intro If you'd prefer a video div class responsive iframe iframe src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div The word monotonic means a list or

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More