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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

In a binary min heap, the maximum element can be found in:

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.

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

Which type of traversal does breadth first search do?

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

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
Not Sure What to Study? Take the 2-min Quiz:

What data structure does Breadth-first search typically uses to store intermediate states?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

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

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫