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

Problem Explanation

The goal here is to find out the maximum length of a subarray, in a given array, in which the absolute difference of any pair of elements is less or equal to a given limit.

To elaborate more let's take the first example:

The array is [8,2,4,7] and the limit is 4.

We have to find the longest subarray consisting of contiguous elements in the array such that the maximum absolute difference between any two of its elements is less than 4.

Here we see that subarrays [8,2], [8,2,4] and [8,2,4,7] have a difference more than 4. Hence they are discarded.

Subarrays [2,4,7], [2,4] and [4,7] have absolute differences less than 4. Out of these, [2,4,7] is the longest with a length of 3 so that would be the answer.

The algorithm approach we will use to solve this efficiently is a sliding window. We will keep track of the maximum and minimum elements in the current window using two deques.

A deque (double-ended queue) is an ordered collection of items where items can be added or removed from both ends -- either from the front or the rear.

These two deques will help to find maximum and minimum in the window with a complexity of O(1). As we slide the window we will eliminate the elements from the front of the deques if they are not part of the window anymore.

Python Solution

1
2python
3from collections import deque
4
5class Solution:
6    def longestSubarray(self, nums: List[int], limit: int) -> int:
7        max_deque = deque()
8        min_deque = deque()
9        start = 0
10        for end in range(len(nums)):
11            while max_deque and max_deque[-1] < nums[end]:
12                max_deque.pop()
13            max_deque.append(nums[end])
14            while min_deque and min_deque[-1] > nums[end]:
15                min_deque.pop()
16            min_deque.append(nums[end])
17            if max_deque[0] - min_deque[0] > limit:
18                if max_deque[0] == nums[start]:
19                    max_deque.popleft()
20                if min_deque[0] == nums[start]:
21                    min_deque.popleft()
22                start += 1
23        return end - start + 1

Java Solution

1
2java
3class Solution {
4    public int longestSubarray(int[] nums, int limit) {
5        Deque<Integer> maxDeque = new LinkedList<>();
6        Deque<Integer> minDeque = new LinkedList<>();
7        int start = 0;
8        int end;
9        for (end = 0; end < nums.length; ++end) {
10            while (!maxDeque.isEmpty() && nums[end] > maxDeque.peekLast())
11                maxDeque.pollLast();
12            while (!minDeque.isEmpty() && nums[end] < minDeque.peekLast())
13                minDeque.pollLast();
14            maxDeque.offer(nums[end]);
15            minDeque.offer(nums[end]);
16            if (maxDeque.peek() - minDeque.peek() > limit) {
17                if (nums[start] == maxDeque.peek())
18                    maxDeque.poll();
19                if (nums[start] == minDeque.peek())
20                    minDeque.poll();
21                ++start;
22            }
23        }
24        return end - start;
25    }
26}

JavaScript Solution

1
2javascript
3class Solution {
4  longestSubarray(nums, limit) {
5    const minDeque = [] // Non-decreasing deque
6    const maxDeque = [] // Non-increasing deque
7    let start = 0, end = 0, n = nums.length
8
9    for (; end < n; ++end) {
10      while (minDeque.length && nums[end] < minDeque[minDeque.length - 1])
11        minDeque.pop()
12      while (maxDeque.length && nums[end] > maxDeque[maxDeque.length - 1])
13        maxDeque.pop()
14      minDeque.push(nums[end])
15      maxDeque.push(nums[end])
16      if (maxDeque[0] - minDeque[0] > limit) {
17        if (nums[start] === minDeque[0])
18          minDeque.shift()
19        if (nums[start] === maxDeque[0])
20          maxDeque.shift()
21        ++start
22      }
23    }
24
25    return end - start
26  }
27}

C++ Solution

1
2c++
3class Solution {
4public:
5    int longestSubarray(vector<int>& nums, int limit) {
6        deque<int> maxDeque;
7        deque<int> minDeque;
8        int start = 0, end = 0, n = nums.size();
9
10        for (; end < n; ++end) {
11            while (!minDeque.empty() && nums[end] < minDeque.back())
12                minDeque.pop_back();
13            while (!maxDeque.empty() && nums[end] > maxDeque.back())
14                maxDeque.pop_back();
15            minDeque.push_back(nums[end]);
16            maxDeque.push_back(nums[end]);
17            if (maxDeque.front() - minDeque.front() > limit) {
18                if (nums[start] == minDeque.front())
19                    minDeque.pop_front();
20                if (nums[start] == maxDeque.front())
21                    maxDeque.pop_front();
22                ++start;
23            }
24        }
25
26        return end - start;
27    }
28};

C# Solution

1
2csharp
3public class Solution {
4    public int LongestSubarray(int[] nums, int limit) {
5        var minDeque = new LinkedList<int>();
6        var maxDeque = new LinkedList<int>();
7        int start = 0;
8        int end;
9        for (end = 0; end < nums.Length; ++end) {
10            while (minDeque.Count > 0 && nums[end] < minDeque.Last.Value)
11                minDeque.RemoveLast();
12            while (maxDeque.Count > 0 && nums[end] > maxDeque.Last.Value)
13                maxDeque.RemoveLast();
14            minDeque.AddLast(nums[end]);
15            maxDeque.AddLast(nums[end]);
16            if (maxDeque.First.Value - minDeque.First.Value > limit) {
17                if (nums[start] == minDeque.First.Value)
18                    minDeque.RemoveFirst();
19                if (nums[start] == maxDeque.First.Value)
20                    maxDeque.RemoveFirst();
21                ++start;
22            }
23        }
24        return end - start;
25    }
26}

In all these given solutions, we can see the use of two of Deque’s functionalities: pushing and popping elements from both the ends and to peek at both ends.

To summarise the steps involved:

1. We first initiate an empty deque for both minimum and maximum elements and also a variable called ‘start’ set at 0.

2. As we iterate over the array maintaining a window, a) We check if the deque has elements, and if it does have, we check if the last element present in the deque is less than the current array value for the max_deque and greater for min_deque. If it does, we drop the element. b) Then we append the current array value to the respective deques.

3. After adding, we check if the first elements (which are the max and min) of both the deques have a difference greater than the limit, a) If they do, we check and drop the first element if it is equal to the beginning of the sliding window. Then we slide the window to the next array element.

4. After the loop is ended we deduct the beginning of the window from the end and add 1 because the end will be pointing at the last element’s index. This gives us the length of the longest subarray with an absolute difference less than or equal to the limit.

These solutions can be easily implemented in Python, JS, Java, C++ and C# and are quite efficient. The time complexity for this approach is linear i.e., O(n), which makes it a great solution for larger data sets. The simplicity of this approach allows it to be widely applicable across various programming languages with minimal modifications.