Problem

Given an array of integers nums and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

Example 2:

1
2
3

Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4 
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.

Example 3:

1
2

Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3

Solution

Method 1 - Sliding Window + Deque

Here is the approach we can follow:

  1. Sliding Window:
    • Use two pointers (left and right) to represent the current window. The right pointer is used to expand the window, and the left pointer is used to contract it when needed.
  2. Deques for Min and Max:
    • Maintain two deques:
      • Monotonically decreasing maxDeque to store the indices of elements in a way that the values are in decreasing order. This helps in quickly accessing the maximum element.
      • minDeque to store the indices of elements in a way that the values are in increasing order. This helps in quickly accessing the minimum element.
  3. Adjust the Window:
    • For every element added to the window (expansion by moving right),
    • Update the maxDeque - We need to dequeue the “tail” element who is smaller than the nums[right]. Since, those “old small tail” elements will never be the range maximum from now on. After “clean up” the “old small tail” elements, add nums[right] into the deque, and then, the head of deque is the current maximum.
    • Update minDeque - Clean up “old big tail” elements, add nums[right], the head of deque is the current minimum.
    • check if the absolute difference between the minimum and maximum elements in the window exceeds the limit.
    • If it does, slide the left pointer to reduce the window until the condition is satisfied again.
  4. Track the Longest Subarray:
    • Keep track of the length of the valid window.

Dry Run

Initial Setup
1
2
3
4
5
6

nums = [8, 2, 4, 7]
limit = 4
maxDeque = [] (to keep indices of max elements)
minDeque = [] (to keep indices of min elements)
left = 0
ans = 0
Sliding Window
Iteration 1 - right = 0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

nums[right] is 8

Update maxDeque: 
maxDeque becomes [0] (index of 8)

Update minDeque:
minDeque becomes [0] (index of 8)

Update Window:
No need to move left, the window size is now 1 (right - left + 1)
ans = 1
Iteration 2 - right = 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

nums[right] is 2

Update maxDeque: 
Nothing is removed from maxDeque
maxDeque becomes [0, 1] (index of 8)

Update minDeque:
Remove 0, since 8 > 2
minDeque becomes [1] (index of 2)

Update Window:
max - min = 8 - 2 = 6 > limit
Hence, move left. left = 1

We remove all indices less than left from the maxDeque and minDeque as they are out window
maxDeque = [1]
minDeque = [1]

ans = right - left + 1 = 1
Iteration 3 - right = 2
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

nums[right] is 4

Update maxDeque: 
Remove 1, since 4 > 2
maxDeque becomes [2] (index of 4)

Update minDeque:
Nothing is removed from minDeque
minDeque becomes [1, 2]

Update Window:
max - min = 4 - 2 = 2 < limit
No need to move left
ans = right - left + 1 = 2 - 1 + 1 = 2
Iteration 1 - right = 3
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

nums[right] is 7

Update maxDeque: 
Remove 2, since 7 > 4
maxDeque becomes [3] (index of 7)

Update minDeque:
Nothing is removed from minDeque
minDeque becomes [1, 2, 3]

Update Window:
max - min = 7 - 2 = 5 > limit
We move left, left += 1 = 2

We remove all indices less than left from the maxDeque and minDeque as they are out window
maxDeque = [3]
minDeque = [2, 3]

Check max - min = 7 - 4 = 3 < limit
No need to move left
ans = right - left + 1 = 3 - 2 + 1 = 2
Final Step

Final result becomes 2.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

public class Solution {

	public int longestSubarray(int[] nums, int limit) {
		int n = nums.length;

		if (n == 0) {
			return 0;
		}

		// Deques to keep track of minimum and maximum elements in the window
		Deque<Integer> maxDeque = new ArrayDeque<>();
		Deque<Integer> minDeque = new ArrayDeque<>();

		int left = 0;
		int ans = 0;

		for (int right = 0; right < n; right++) {
			while (!maxDeque.isEmpty() && nums[maxDeque.peekLast()]  <= nums[right]) {
				maxDeque.pollLast();
			}

			maxDeque.offerLast(right);

			while (!minDeque.isEmpty() && nums[minDeque.peekLast()] >= nums[right]) {
				minDeque.pollLast();
			}

			minDeque.offerLast(right);

			// Check the condition
			while (!maxDeque.isEmpty() && !minDeque.isEmpty() &&
				nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > limit) {
				left++;
				// Remove the elements which are out of this new window
				if (maxDeque.peekFirst()<left) {
					maxDeque.pollFirst();
				}

				if (minDeque.peekFirst()<left) {
					minDeque.pollFirst();
				}
			}

			ans = Math.max(ans, right - left + 1);
		}

		return ans;
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)