Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
MedPrompt
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.
Example 1:
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:
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:
Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1090 <= limit <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through all possible continuous subarrays. For each starting point i, it expands a window to the right with an endpoint j. While expanding, it keeps track of the minimum and maximum values within the current subarray nums[i...j].
Algorithm
- Initialize
maxLength = 0. - Iterate through the array with an index
ifrom0ton-1(this will be the start of the subarray). - Inside this loop, initialize
minVal = nums[i]andmaxVal = nums[i]. - Start a second loop with an index
jfromiton-1(this will be the end of the subarray). - Update
minVal = min(minVal, nums[j])andmaxVal = max(maxVal, nums[j]). - If
maxVal - minVal <= limit, updatemaxLength = max(maxLength, j - i + 1). - If
maxVal - minVal > limit, break the inner loop, as any further extension will also be invalid. - After the loops complete, return
maxLength.
Walkthrough
We use two nested loops. The outer loop fixes the starting index i of the subarray, and the inner loop iterates through all possible ending indices j starting from i.
For each subarray nums[i...j], we maintain the minimum (minVal) and maximum (maxVal) elements seen so far within that specific subarray.
In the inner loop, as we consider nums[j], we update minVal and maxVal.
We then check if the condition maxVal - minVal <= limit holds.
If it holds, the current subarray is valid, and we update our answer for the maximum length: maxLength = max(maxLength, j - i + 1).
If the condition is violated (maxVal - minVal > limit), we can break the inner loop. This is a small optimization because any further extension of the subarray from the current starting point i will also violate the condition.
class Solution { public int longestSubarray(int[] nums, int limit) { int maxLength = 0; for (int i = 0; i < nums.length; i++) { int minVal = nums[i]; int maxVal = nums[i]; for (int j = i; j < nums.length; j++) { minVal = Math.min(minVal, nums[j]); maxVal = Math.max(maxVal, nums[j]); if (maxVal - minVal <= limit) { maxLength = Math.max(maxLength, j - i + 1); } else { // Optimization: If the condition is violated, // any further extension from 'i' will also be invalid. break; } } } return maxLength; }}Complexity
Time
O(n^2), where n is the length of `nums`. The two nested loops dominate the runtime.
Space
O(1), as we only use a few variables to store the state.
Trade-offs
Pros
Simple to understand and implement.
Cons
Inefficient for large inputs, leading to a "Time Limit Exceeded" error on most platforms.
This approach uses a sliding window, defined by a left and right pointer. To efficiently find the minimum and maximum elements within the window, we use a self-balancing binary search tree. In Java, a TreeMap is a suitable data structure for this, as it keeps its keys sorted.
Algorithm
- Initialize
left = 0,maxLength = 0. - Initialize an empty
TreeMapcalledmapto store counts of numbers in the window. - Iterate
rightfrom0ton-1:- Add
nums[right]to themap, incrementing its count. - While
map.lastKey() - map.firstKey() > limit:- Decrement the count of
nums[left]in themap. - If the count of
nums[left]becomes0, remove it from themap. - Increment
left.
- Decrement the count of
- Update
maxLength = max(maxLength, right - left + 1).
- Add
- Return
maxLength.
Walkthrough
The core idea is to maintain a window of elements that satisfies the condition max - min <= limit. We expand this window by moving the right pointer and shrink it by moving the left pointer.
We use a TreeMap to store the elements in the current window and their frequencies. The keys of the TreeMap are the numbers, and the values are their counts.
We iterate through the array with the right pointer. For each element nums[right], we add it to our TreeMap.
The minimum element in the window is treeMap.firstKey() and the maximum is treeMap.lastKey().
We check if treeMap.lastKey() - treeMap.firstKey() > limit. If it is, our window is invalid. We must shrink it from the left.
To shrink the window, we remove nums[left] from the TreeMap (by decrementing its count, and removing the key if the count becomes zero) and increment the left pointer. We repeat this until the window becomes valid again.
After ensuring the window is valid, we calculate its size (right - left + 1) and update the maxLength.
import java.util.TreeMap; class Solution { public int longestSubarray(int[] nums, int limit) { TreeMap<Integer, Integer> map = new TreeMap<>(); int left = 0; int maxLength = 0; for (int right = 0; right < nums.length; right++) { map.put(nums[right], map.getOrDefault(nums[right], 0) + 1); while (map.lastKey() - map.firstKey() > limit) { map.put(nums[left], map.get(nums[left]) - 1); if (map.get(nums[left]) == 0) { map.remove(nums[left]); } left++; } maxLength = Math.max(maxLength, right - left + 1); } return maxLength; }}Complexity
Time
O(n log n). The `right` pointer moves `n` times. In each step, we might perform insertions and deletions on the `TreeMap`. These operations take O(log k) time, where `k` is the number of distinct elements in the window (`k <= n`).
Space
O(n) in the worst case, where the `TreeMap` might need to store all `n` elements if they are all distinct and part of a valid window.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Passes most test cases on competitive programming platforms.
Cons
The logarithmic factor from the
TreeMapoperations makes it slightly slower than the most optimal solution.
This is the most optimal approach. It uses a sliding window and two Deques (Double-Ended Queues) to keep track of the minimum and maximum values in the current window in O(1) time on average. One deque maintains potential maximums in decreasing order, and the other maintains potential minimums in increasing order.
Algorithm
- Initialize
left = 0,maxLength = 0. - Initialize an empty
maxDequeand an emptyminDequeto store indices. - Iterate
rightfrom0ton-1:- While
maxDequeis not empty and the value at its last index is less than or equal tonums[right], remove the last element frommaxDeque. - Add
rightto the end ofmaxDeque. - While
minDequeis not empty and the value at its last index is greater than or equal tonums[right], remove the last element fromminDeque. - Add
rightto the end ofminDeque. - While the difference between the values at the front of the deques (
nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()]) is greater thanlimit:- If the index at the front of
maxDequeisleft, remove it. - If the index at the front of
minDequeisleft, remove it. - Increment
leftto shrink the window.
- If the index at the front of
- Update
maxLength = max(maxLength, right - left + 1).
- While
- Return
maxLength.
Walkthrough
We maintain a sliding window [left, right]. We also use two deques: maxDeque and minDeque. These deques will store the indices of the elements.
maxDeque: Stores indices of elements in the current window in decreasing order of their values. The front of the deque always holds the index of the maximum element in the window.minDeque: Stores indices of elements in the current window in increasing order of their values. The front of the deque always holds the index of the minimum element in the window. As we iterate with therightpointer, we addnums[right]to the window. To maintain the properties of the deques, before adding the indexright, we remove from the back ofmaxDequeall indicesiwherenums[i] <= nums[right], and do the opposite forminDeque. Then we addrightto the back of both deques. The maximum in the current window isnums[maxDeque.peekFirst()]and the minimum isnums[minDeque.peekFirst()]. We check if their difference exceeds thelimit. If it does, we shrink the window from the left by incrementingleftand removingleftfrom the deques if it was the head. After each step, the window[left, right]is valid, and we updatemaxLength.
import java.util.Deque;import java.util.LinkedList; class Solution { public int longestSubarray(int[] nums, int limit) { Deque<Integer> maxDeque = new LinkedList<>(); Deque<Integer> minDeque = new LinkedList<>(); int left = 0; int maxLength = 0; for (int right = 0; right < nums.length; right++) { // Maintain the maxDeque in decreasing order of values while (!maxDeque.isEmpty() && nums[maxDeque.peekLast()] <= nums[right]) { maxDeque.pollLast(); } maxDeque.addLast(right); // Maintain the minDeque in increasing order of values while (!minDeque.isEmpty() && nums[minDeque.peekLast()] >= nums[right]) { minDeque.pollLast(); } minDeque.addLast(right); // Check if the current window is invalid and shrink it until it's valid while (nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > limit) { if (maxDeque.peekFirst() == left) { maxDeque.pollFirst(); } if (minDeque.peekFirst() == left) { minDeque.pollFirst(); } left++; } // The window [left, right] is now valid. Update the max length. maxLength = Math.max(maxLength, right - left + 1); } return maxLength; }}Complexity
Time
O(n). Each element is added to and removed from each deque at most once. The `left` and `right` pointers traverse the array once. This gives a linear time complexity.
Space
O(n). In the worst case (e.g., a sorted array), the deques could store indices for all elements. In the best case, it's O(1).
Trade-offs
Pros
Most efficient solution with linear time complexity.
Cons
Can be slightly more complex to understand and implement correctly compared to the
TreeMapapproach.
Solutions
Solution
class Solution {public int longestSubarray(int[] nums, int limit) { TreeMap<Integer, Integer> tm = new TreeMap<>(); int ans = 0, j = 0; for (int i = 0; i < nums.length; ++i) { tm.put(nums[i], tm.getOrDefault(nums[i], 0) + 1); while (tm.lastKey() - tm.firstKey() > limit) { tm.put(nums[j], tm.get(nums[j]) - 1); if (tm.get(nums[j]) == 0) { tm.remove(nums[j]); } ++j; } ans = Math.max(ans, i - j + 1); } return ans; }}class Solution { public: int longestSubarray ( vector < int >& nums , int limit ) { multiset < int > s ; int ans = 0 , j = 0 ; for ( int i = 0 ; i < nums . size (); ++ i ) { s . insert ( nums [ i ]); while ( * s . rbegin () - * s . begin () > limit ) { s . erase ( s . find ( nums [ j ++ ])); } ans = max ( ans , i - j + 1 ); } return ans ; } };from sortedcontainers import SortedList class Solution : def longestSubarray ( self , nums : List [ int ], limit : int ) -> int : sl = SortedList () ans = j = 0 for i , v in enumerate ( nums ): sl . add ( v ) while sl [ - 1 ] - sl [ 0 ] > limit : sl . remove ( nums [ j ]) j += 1 ans = max ( ans , i - j + 1 ) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.