Given an integer array nums and a non-negative integer limit, find the maximum length of a contiguous subarray with every pairwise absolute difference at most limit.
Example 1
Input: nums = [8, 2, 4, 7], limit = 4
Output: 2
Explanation: Subarray [2, 4] has maximum value 4 and minimum value 2. The difference equals 2, so the length is 2. Every length-three subarray has a difference greater than 4.
Example 2
Input: nums = [4, 4, 4], limit = 0
Output: 3
Explanation: Every value is equal, so the maximum and minimum difference remains 0 across the complete array.
Brute Force Approach
A subarray is valid when the difference between its maximum and minimum values is at most limit. The simplest method is to choose every possible starting position and keep extending the subarray toward the right.
While extending, maintain the current minimum and maximum instead of scanning the complete subarray again. Once the difference becomes greater than limit, the search can stop because adding more elements cannot decrease the current range.
Algorithm
Initialize
longest = 0to store the maximum length of a valid subarray.Select every array index as the left boundary of a candidate subarray.
Set
currentMinimumandcurrentMaximumto the left-boundary value, because the first subarray contains only that element.Extend the right boundary from the left index to the end of the array, generating every subarray with the selected start.
Update
currentMinimumandcurrentMaximumafter including each new value, so they represent the range of the current subarray.If
currentMaximum - currentMinimum <= limit, updatelongestwith the current subarray length.Otherwise, stop extending the current subarray because adding more elements cannot reduce the maximum-minus-minimum difference.
Return
longestafter processing every possible left boundary.
Dry Run
longest-continuous-subarray-brute-force-approach
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds the longest valid subarray by enumeration. int longestSubarray(vector<int>& nums, int limit) { // Stores the best valid length. int longest = 0; // Tries every possible left boundary. for (int left = 0; left < nums.size(); left++) { // Tracks both extremes in the current range. int minimum = nums[left]; int maximum = nums[left]; // Extends the current range toward the right. for (int right = left; right < nums.size(); right++) { // Includes the new value in both extremes. minimum = min(minimum, nums[right]); maximum = max(maximum, nums[right]); // Further extensions cannot restore validity. if (maximum - minimum > limit) { break; } // Records the valid current range length. int length = right - left + 1; longest = max(longest, length); } } // Returns the largest valid length. return longest; }};// Driver codeint main() { vector<int> nums = {8, 2, 4, 7}; int limit = 4; Solution obj; cout << obj.longestSubarray(nums, limit) << endl; return 0;}Note: The brute-force approach may fail for large arrays. Quadratic work can cause an online judge to report Time Limit Exceeded.
Complexity Analysis
Time Complexity: O(N2), every left boundary can extend across the remaining array.
Space Complexity: O(1), only running extremes and boundary variables are stored.
Optimal Approach
The brute-force method repeatedly finds the minimum and maximum for many overlapping subarrays. A sliding window avoids this repeated work by expanding the right boundary and moving the left boundary only when the current window becomes invalid.
Two monotonic deques keep the required maximum and minimum available at their fronts. The maximum deque stores values in decreasing order, while the minimum deque stores values in increasing order. Indices are stored so values that leave the window can also be removed from the deques.
Algorithm
Initialize
left = 0andlongest = 0. Create two empty deques to track possible maximum and minimum indices.Traverse every index as the right boundary of the current window.
Remove indices from the back of the maximum deque while their values are smaller than or equal to
nums[right], because they cannot become the maximum while the current value remains in the window.Remove indices from the back of the minimum deque while their values are larger than or equal to
nums[right], because they cannot become the minimum while the current value remains in the window.Add
rightto both deques so the current value can participate in future windows.While the difference between the maximum and minimum exceeds
limit:Remove the front index from either deque when it is equal to
left, because that value is leaving the window.Move
leftone position to the right to reduce the window size.
Update
longestwithright - left + 1after the window becomes valid, because this expression gives the current window length.Return
longestafter processing every right boundary.
Dry Run
longest-continuous-subarray-optimal-approach
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds the longest valid window with two deques. int longestSubarray(vector<int>& nums, int limit) { // Stores indices of decreasing maximum candidates. deque<int> maximumDeque; // Stores indices of increasing minimum candidates. deque<int> minimumDeque; int left = 0; int longest = 0; // Expands the sliding window one value at a time. for (int right = 0; right < nums.size(); right++) { // Removes values unable to become a maximum. while (!maximumDeque.empty() && nums[maximumDeque.back()] <= nums[right]) { maximumDeque.pop_back(); } maximumDeque.push_back(right); // Removes values unable to become a minimum. while (!minimumDeque.empty() && nums[minimumDeque.back()] >= nums[right]) { minimumDeque.pop_back(); } minimumDeque.push_back(right); // Shrinks an invalid window from the left. while (nums[maximumDeque.front()] - nums[minimumDeque.front()] > limit) { // Removes an expired maximum candidate. if (maximumDeque.front() == left) { maximumDeque.pop_front(); } // Removes an expired minimum candidate. if (minimumDeque.front() == left) { minimumDeque.pop_front(); } left++; } // Records the valid current window length. int length = right - left + 1; longest = max(longest, length); } // Returns the largest valid window length. return longest; }};// Driver codeint main() { vector<int> nums = {8, 2, 4, 7}; int limit = 4; Solution obj; cout << obj.longestSubarray(nums, limit) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), every index enters and leaves each monotonic deque at most once.
Space Complexity: O(N), both deques can store up to N candidate indices.
Interview follow-up Questions
The largest absolute difference in any window always occurs between its maximum and minimum values. Therefore, if maximum - minimum is within the allowed limit, every other pair in that window also satisfies the condition.
Be the first to add a comment.