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.
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; }}Video 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.