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:

1. Maintain a sliding window that expands and contracts as we iterate through the nums array.
2. In each iteration, add the current element to the SortedList, which is our window.
3. Check if the absolute difference between the smallest and largest elements in the SortedList exceeds the limit.
4. 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.
5. 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:

1. Initialize a SortedList named sl and two pointers for the window indices i and j with i being the right pointer and j being the left one. Also, initialize a variable ans to store the longest length of the subarray found so far.

2. Loop through the elements of nums with index i and value v.

   • Add the new element v to the SortedList. Because the list is always sorted, doing this helps us quickly reference the smallest and largest elements up to the current position.

3. Inside the loop, check if the current window (from j to i inclusively) is valid, meaning that the absolute difference between the largest (sl[-1]) and smallest (sl[0]) elements in the SortedList does not exceed the limit.

   • If the limit is exceeded, we need to contract the window by removing the leftmost element. This is done by removing nums[j] from SortedList since j corresponds to the leftmost index of the window.
   • Increment j to move the start of the window to the right.

4. Update the answer ans with the maximum length found so far. We compute the current window size with i - j + 1, as i is the end of the window and j is the beginning.

5. 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:

1sl = SortedList()  # Instantiate a SortedList data structure.
2ans = j = 0  # Initialize the answer and the left pointer of the window to 0.
3for i, v in enumerate(nums):
4    sl.add(v)
5    while sl[-1] - sl[0] > limit:  # If current window is invalid, contract it.
6        sl.remove(nums[j])
7        j += 1
8    ans = max(ans, i - j + 1)  # Store the largest size of the valid window.
9return 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.

Example 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:

1. We initialize an empty SortedList named sl, set two pointers for the window indices j = 0 and i = 0, and ans = 0, the variable that will hold the answer.

2. We start iterating through the elements of nums.

   • For i = 0 (v = 4): Add 4 to sl, so sl = [4]. The window [4] is valid because there is only one element. Update ans to 1.

3. Move to i = 1 (v = 2):

   • Add 2 to sl, leading to sl = [2, 4]. The window [4, 2] is valid as 4 - 2 = 2, which does not exceed the limit. Update ans to 2.

4. Proceed to i = 2 (v = 2):

   • Add another 2 to sl, so sl = [2, 2, 4]. The window [4, 2, 2] is still valid for the same reasons. Update ans to 3.

5. Move on to i = 3 (v = 5):

   • Add 5 to sl, which yields sl = [2, 2, 4, 5]. The window [4, 2, 2, 5] is invalid because 5 - 2 = 3, which is larger than the limit. We remove the leftmost element (nums[j] which is 4) from sl, resulting in sl = [2, 2, 5], and increment j to 1. The updated window [2, 2, 5] is now valid. Update ans to 3.

6. Finally, for i = 4 (v = 4):

   • We add 4 to sl to get sl = [2, 2, 4, 5]. The window [2, 2, 5, 4] is again invalid because 5 - 2 = 3 exceeds the limit. We remove nums[j] (which is now the leftmost 2) from sl, making it sl = [2, 4, 5], and increment j to 2. The new window [2, 5, 4] is valid and its size (3) is used to update ans if it's larger than the current ans.

7. Having iterated through all elements, we find that the longest subarray where the absolute difference between any two elements does not exceed the limit is 3. Thus, we return ans = 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

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.