1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Problem Description
The problem provides an array of integers named nums
and an integer called limit
. The task is to find the length of the longest non-empty contiguous subarray (a sequence of adjacent elements from the array) where the absolute difference between any two elements in the subarray does not exceed the limit
value.
For example, if the input array is [10, 1, 2, 4, 7, 2]
and the limit is 5
, the longest subarray where the absolute difference between any two elements is less than or equal to 5
is [1, 2, 4, 7, 2]
, which has a length of 5
.
The two key aspects of the problem are:
- Working with contiguous elements (subarray), not just any subsets of the array.
- Ensuring that every pair of elements in the subarray has an absolute difference of at most
limit
.
Intuition
The solution approach involves using a data structure that maintains a sorted order of elements. This allows the efficient retrieval of the smallest and largest elements in the current window (subarray) to check if their absolute difference is within the limit
.
A suitable data structure for this problem is a SortedList, provided by the sortedcontainers
library in Python. Here's how we can arrive at the solution:
- Maintain a sliding window that expands and contracts as we iterate through the
nums
array. - In each iteration, add the current element to the SortedList, which is our window.
- Check if the absolute difference between the smallest and largest elements in the SortedList exceeds the
limit
. - If it does, we remove the leftmost element from our window (which was first added when the window was last valid) to try and bring the difference back within
limit
. - We keep track of the maximum size of the window that satisfied the condition of staying within the
limit
.
This approach ensures that at any given point, we have the longest valid subarray ending at the current position, and we keep updating the answer with the maximum size found so far.
The reason we use a SortedList instead of sorting the window array in each iteration is the time complexityāSortedList maintains the order of elements with a far lesser time complexity for insertion and removal compared to sorting an array at each step.
Learn more about Queue, Sliding Window, Monotonic Queue and Heap (Priority Queue) patterns.
Solution Approach
The implementation is based on the sliding window pattern, which is an optimization technique to reduce repeated work and maintain a range of elements that fulfill certain criteria. Here is a detailed explanation:
-
Initialize a
SortedList
namedsl
and two pointers for the window indicesi
andj
withi
being the right pointer andj
being the left one. Also, initialize a variableans
to store the longest length of the subarray found so far. -
Loop through the elements of
nums
with indexi
and valuev
.- Add the new element
v
to theSortedList
. Because the list is always sorted, doing this helps us quickly reference the smallest and largest elements up to the current position.
- Add the new element
-
Inside the loop, check if the current window (from
j
toi
inclusively) is valid, meaning that the absolute difference between the largest (sl[-1]
) and smallest (sl[0]
) elements in theSortedList
does not exceed thelimit
.- If the limit is exceeded, we need to contract the window by removing the leftmost element. This is done by removing
nums[j]
fromSortedList
sincej
corresponds to the leftmost index of the window. - Increment
j
to move the start of the window to the right.
- If the limit is exceeded, we need to contract the window by removing the leftmost element. This is done by removing
-
Update the answer
ans
with the maximum length found so far. We compute the current window size withi - j + 1
, asi
is the end of the window andj
is the beginning. -
After the loop ends, return
ans
, which holds the size of the longest subarray found that satisfies the condition.
Here is a code snippet to illustrate the solution's core logic:
sl = SortedList() # Instantiate a SortedList data structure.
ans = j = 0 # Initialize the answer and the left pointer of the window to 0.
for i, v in enumerate(nums):
sl.add(v)
while sl[-1] - sl[0] > limit: # If current window is invalid, contract it.
sl.remove(nums[j])
j += 1
ans = max(ans, i - j + 1) # Store the largest size of the valid window.
return ans
The SortedList is efficient because it keeps elements sorted at all times. Hence, we can always get the smallest and largest element in O(1) time and remove elements in O(log N) time, where N
is the number of elements in the list. This is much more optimal than sorting a list which would take O(N log N) time for each change in the window.
Overall, the use of a sliding window algorithm with SortedList allows us to efficiently solve this problem with a time complexity that depends on inserting and removing each element into the sorted list (generally O(log N) for each operation), rather than re-evaluating the entire subarray every time.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a small example to illustrate the solution approach. Consider the input array nums = [4, 2, 2, 5, 4]
with limit = 2
.
Following the proposed solution:
-
We initialize an empty
SortedList
namedsl
, set two pointers for the window indicesj = 0
andi = 0
, andans = 0
, the variable that will hold the answer. -
We start iterating through the elements of
nums
.- For
i = 0
(v = 4
): Add4
tosl
, sosl = [4]
. The window[4]
is valid because there is only one element. Updateans
to1
.
- For
-
Move to
i = 1
(v = 2
):- Add
2
tosl
, leading tosl = [2, 4]
. The window[4, 2]
is valid as4 - 2 = 2
, which does not exceed the limit. Updateans
to2
.
- Add
-
Proceed to
i = 2
(v = 2
):- Add another
2
tosl
, sosl = [2, 2, 4]
. The window[4, 2, 2]
is still valid for the same reasons. Updateans
to3
.
- Add another
-
Move on to
i = 3
(v = 5
):- Add
5
tosl
, which yieldssl = [2, 2, 4, 5]
. The window[4, 2, 2, 5]
is invalid because5 - 2 = 3
, which is larger than the limit. We remove the leftmost element (nums[j]
which is4
) fromsl
, resulting insl = [2, 2, 5]
, and incrementj
to1
. The updated window[2, 2, 5]
is now valid. Updateans
to3
.
- Add
-
Finally, for
i = 4
(v = 4
):- We add
4
tosl
to getsl = [2, 2, 4, 5]
. The window[2, 2, 5, 4]
is again invalid because5 - 2 = 3
exceeds the limit. We removenums[j]
(which is now the leftmost2
) fromsl
, making itsl = [2, 4, 5]
, and incrementj
to2
. The new window[2, 5, 4]
is valid and its size (3
) is used to updateans
if it's larger than the currentans
.
- We add
-
Having iterated through all elements, we find that the longest subarray where the absolute difference between any two elements does not exceed the
limit
is3
. Thus, we returnans = 3
.
This example shows how the sliding window moves through the array and adjusts by adding new elements and potentially removing the leftmost element to maintain a valid subarray within the limit
. The SortedList
makes it efficient to find the minimum and maximum within the current window to decide if the subarray satisfies the condition.
Solution Implementation
1# We import SortedList from the sortedcontainers module
2from sortedcontainers import SortedList
3from typing import List # Import List from typing module for type annotation
4
5class Solution:
6 def longest_subarray(self, nums: List[int], limit: int) -> int:
7 # Initialize a SortedList which allows us to maintain a sorted collection of numbers
8 sorted_list = SortedList()
9
10 # Initialize variables for the answer and the start index of the window
11 max_length = 0
12 window_start = 0
13
14 # Iterate through the array with index and value
15 for window_end, value in enumerate(nums):
16 # Add the current value to the sorted list
17 sorted_list.add(value)
18
19 # Shrink the window from the left if the condition is violated
20 # The condition being if the absolute difference between the max and min values in the window exceeds the limit
21 while sorted_list[-1] - sorted_list[0] > limit:
22 # Remove the leftmost value from the sorted list as we're shrinking the window
23 sorted_list.remove(nums[window_start])
24 # Move the start of the window to the right
25 window_start += 1
26
27 # Calculate the length of the current window and compare with the max
28 # Update the max_length as needed
29 max_length = max(max_length, window_end - window_start + 1)
30
31 # Return the length of the longest subarray after examining all windows
32 return max_length
33
34# Example usage
35# sol = Solution()
36# result = sol.longest_subarray([10,1,2,4,7,2], 5)
37# print(result) # Output: 4
38
1class Solution {
2 public int longestSubarray(int[] nums, int limit) {
3 // Create a TreeMap to keep track of the frequency of each number
4 TreeMap<Integer, Integer> frequencyMap = new TreeMap<>();
5 int maxLength = 0; // Stores the maximum length of the subarray
6 int left = 0; // The left pointer for our sliding window
7
8 // Iterate over the array using the right pointer 'right'
9 for (int right = 0; right < nums.length; ++right) {
10 // Update the frequency of the current number
11 frequencyMap.put(nums[right], frequencyMap.getOrDefault(nums[right], 0) + 1);
12
13 // Shrink the sliding window until the absolute difference between the max
14 // and min within the window is less than or equal to 'limit'
15 while (frequencyMap.lastKey() - frequencyMap.firstKey() > limit) {
16 // Decrease the frequency of the number at the left pointer
17 frequencyMap.put(nums[left], frequencyMap.get(nums[left]) - 1);
18 // If the frequency drops to zero, remove it from the frequency map
19 if (frequencyMap.get(nums[left]) == 0) {
20 frequencyMap.remove(nums[left]);
21 }
22 // Move the left pointer to the right, shrinking the window
23 ++left;
24 }
25
26 // Update the maximum length found so far
27 maxLength = Math.max(maxLength, right - left + 1);
28 }
29 // Return the maximum length of the subarray that satisfies the condition
30 return maxLength;
31 }
32}
33
1#include <vector>
2#include <set>
3#include <algorithm>
4
5class Solution {
6public:
7 // Function to calculate the length of the longest subarray with the absolute difference
8 // between any two elements not exceeding `limit`.
9 int longestSubarray(vector<int>& nums, int limit) {
10 // Initialize a multiset to maintain the elements in the current sliding window.
11 multiset<int> window_elements;
12 int longest_subarray_length = 0; // Variable to keep track of the max subarray length.
13 int window_start = 0; // Starting index of the sliding window.
14
15 // Iterate over the array using `i` as the end of the sliding window.
16 for (int window_end = 0; window_end < nums.size(); ++window_end) {
17 // Insert the current element into the multiset.
18 window_elements.insert(nums[window_end]);
19
20 // If the difference between the largest and smallest elements in the multiset
21 // exceeds the `limit`, shrink the window from the left until the condition is satisfied.
22 while (*window_elements.rbegin() - *window_elements.begin() > limit) {
23 // Erase the leftmost element from the multiset and shrink the window.
24 window_elements.erase(window_elements.find(nums[window_start++]));
25 }
26
27 // Calculate the length of the current subarray and update the maximum length.
28 int current_subarray_length = window_end - window_start + 1;
29 longest_subarray_length = max(longest_subarray_length, current_subarray_length);
30 }
31
32 // Return the length of the longest subarray found.
33 return longest_subarray_length;
34 }
35};
36
1type CompareFunction<T> = (a: T, b: T) => number;
2
3interface ITreapNode<T> {
4 value: T;
5 count: number;
6 size: number;
7 priority: number;
8 left: ITreapNode<T> | null;
9 right: ITreapNode<T> | null;
10}
11
12let compareFn: CompareFunction<any>;
13let leftBound: any;
14let rightBound: any;
15let root: ITreapNode<any>;
16
17function getSize(node: ITreapNode<any> | null): number {
18 return node?.size ?? 0;
19}
20
21function getFac(node: ITreapNode<any> | null): number {
22 return node?.priority ?? 0;
23}
24
25function createTreapNode<T>(value: T): ITreapNode<T> {
26 const node: ITreapNode<T> = {
27 value: value,
28 count: 1,
29 size: 1,
30 priority: Math.random(),
31 left: null,
32 right: null,
33 };
34
35 return node;
36}
37
38function pushUp(node: ITreapNode<any>): void {
39 let tmp = node.count;
40 tmp += getSize(node.left);
41 tmp += getSize(node.right);
42 node.size = tmp;
43}
44
45function rotateRight<T>(node: ITreapNode<T>): ITreapNode<T> {
46 const left = node.left;
47 node.left = left?.right ?? null;
48 if (left) {
49 left.right = node;
50 }
51 if (node.right) pushUp(node.right);
52 pushUp(node);
53 return left ?? node;
54}
55
56function rotateLeft<T>(node: ITreapNode<T>): ITreapNode<T> {
57 const right = node.right;
58 node.right = right?.left ?? null;
59 if (right) {
60 right.left = node;
61 }
62 if (node.left) {
63 pushUp(node.left);
64 }
65 pushUp(node);
66 return right ?? node;
67}
68
69// ... (Other methods would be similarly defined as global functions, but not included here for brevity)
70
71// Initialize the global Treap
72function initTreap<T>(
73 compFn: CompareFunction<T>,
74 leftBnd: T = -Infinity as unknown as T,
75 rightBnd: T = Infinity as unknown as T,
76): void {
77 compareFn = compFn as unknown as CompareFunction<any>;
78 leftBound = leftBnd;
79 rightBound = rightBnd;
80 const treapRoot: ITreapNode<any> = createTreapNode<any>(rightBound);
81 treapRoot.priority = Infinity;
82 treapRoot.left = createTreapNode<any>(leftBound);
83 treapRoot.left.priority = -Infinity;
84 pushUp(treapRoot.left);
85 pushUp(treapRoot);
86 root = treapRoot;
87}
88
89// Example usage of initializing and using the treap
90initTreap<number>((a, b) => a - b);
91addNode(root, 10); // This assumes the addNode function is implemented globally as mentioned above.
92
Time and Space Complexity
Time Complexity
The provided code utilizes a sliding window approach within a loop and a SortedList to keep track of the order of elements. For each element in nums
, it is added to the SortedList
, which is typically an O(log n)
operation due to the underlying binary search tree or similar data structure used for keeping the list sorted.
The while
loop inside the for
loop is executed only when the current subarray does not meet the limit condition. Within the loop, remove(nums[j])
is called, which is also an O(log n)
operation because the list must be searched for the value to remove it, and it might need restructuring to keep it sorted.
The variable ans
is updated using a max()
function which is an O(1)
operation.
Since the for
loop iterates over each element in nums
once, and the inner while
loop only processes each element once due to the sliding window mechanism, the overall time complexity is O(n log n)
, where n
is the number of elements in the nums
list.
Space Complexity
The additional space used by the algorithm consists of the SortedList
and the variables used for iteration and storing the current longest subarray's length. The space complexity of the SortedList
depends on the number of unique elements inserted. In the worst-case scenario, all elements of nums
are different, and the SortedList
will contain n
elements, leading to a space complexity of O(n)
.
The space for the other variables is comparatively negligible (O(1)
), so the overall space complexity is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the maximum element can be found in:
Recommended Readings
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
https algomonster s3 us east 2 amazonaws com 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
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!