Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Problem Description
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 the limit.
What is a Subarray ?
It's a sequence of elements taken from the original array that are next to each other, without skipping any elements.
For the array [1, 2, 3, 4], here are all possible subarrays:
Single element subarrays:
[1], [2], [3], [4]
Subarrays of length 2:
[1, 2], [2, 3], [3, 4]
Subarrays of length 3:
[1, 2, 3], [2, 3, 4]
Subarray of length 4:
[1, 2, 3, 4] (the entire array)
Note:- { 1, 3 ,4 } or { 2,4 } are not the subarrays of arr[ ] = { 1 , 2 , 3 , 4 }
Examples of Longest contiguous subarray
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.
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.
Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3
Explanation:
Constraints:
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- 0 <= limit <= 10^9
The given problem statement can be solved with different approaches such as Sliding Window/Two pointers, Deque, etc. Each approach has its own benefits and challenges in terms of how fast it works and how much memory it uses.
Brute Force Approach (Generate All Subarrays)
Intuition
We will be given a nums array of integers and an integer limit. The problem asks us to find the length/size of the longest subarray where the absolute difference between any two elements of that subarray is less than or equal to the limit.
The first approach that came to our mind is quite obvious i.e to simply generate all subarrays and then check which subarray satisfies the condition(absolute difference between any two elements of that subarray is less than or equal to the limit) and then update the maximum length as long as we complete the array traversal.
How to generate Subarray of an Array ?
Pick a starting point (i): This can be any index from 0 to n-1 (where n is the length of the array).
Pick an ending point (j): This can be any index from the current starting point i to n-1.
Extract the subarray: Once you have both the starting (i) and ending (j) points, you can extract the subarray by slicing from index i to j (inclusive).
For arr = [1, 2, 3]:
Start at i = 0:
Subarray [1] (from i = 0 to j = 0)
Subarray [1, 2] (from i = 0 to j = 1)
Subarray [1, 2, 3] (from i = 0 to j = 2)
Start at i = 1:
Subarray [2] (from i = 1 to j = 1)
Subarray [2, 3] (from i = 1 to j = 2)
Start at i = 2:
Subarray [3] (from i = 2 to j = 2)
But which two values are to be compared?
We will be calculating the absolute difference between the highest and lowest values in that subarray.
Why Consider the Absolute Difference Between the Highest and Lowest Values?
The absolute difference between the highest (max_value) and lowest (min_value) values in a subarray represents the largest gap between any two numbers in that subarray. If this gap is within the given limit, then all other differences between elements will also be within the limit.
For example:
- Subarray: [8, 2, 4, 7]
- max_value = 8
- min_value = 2
- |max_value - min_value| = |8 - 2| = 6 (violates the limit if limit = 4)
If the condition fails for max_value - min_value, there’s no need to check other differences, as this represents the largest possible difference in the subarray. This ensures efficiency in the checking process.
If our absolute difference is less than or equal to the limit, we will update the maximum Length. If it is not, we will break it as they will also violate the condition for longer subarrays.
How To Approach This Problem
Generate all possible subarrays:
Use nested loops to consider all possible starting and ending points of subarrays in the given array.
Check the condition for each subarray:
For every subarray, calculate the maximum and minimum values. If the absolute difference between the maximum and minimum values is less than or equal to the given limit, then the subarray satisfies the condition.
Update the maximum length:
Keep track of the length of the largest subarray that satisfies the condition.
Dry-Run
nums = [1, 5, 6, 7, 8, 10, 6, 5, 6]
limit = 4
Answer: 5
Explanation: The longest subarray that satisfies the condition has a length of 5. The longest subarray is [6, 7, 8, 10, 6].
Initialize:
max_length = 0
Outer Loop (i as the start index of subarray):
i = 0:
Subarray starts at index 0
- Inner Loop (j = 0):
Subarray: [1] - current_min = 1, current_max = 1
- |current_max - current_min| = |1 - 1| = 0 (satisfies limit)
- max_length = max(0, 1) = 1
- Inner Loop (j = 1):
Subarray: [1, 5] - current_min = 1, current_max = 5
- |current_max - current_min| = |5 - 1| = 4 (satisfies limit)
- max_length = max(1, 2) = 2
- Inner Loop (j = 2):
Subarray: [1, 5, 6] - current_min = 1, current_max = 6
- |current_max - current_min| = |6 - 1| = 5 (violates limit)
- Break.
i = 1:
Subarray starts at index 1
- Inner Loop (j = 1):
Subarray: [5] - current_min = 5, current_max = 5
- |current_max - current_min| = |5 - 5| = 0 (satisfies limit)
- max_length = max(2, 1) = 2
- Inner Loop (j = 2):
Subarray: [5, 6] - current_min = 5, current_max = 6
- |current_max - current_min| = |6 - 5| = 1 (satisfies limit)
- max_length = max(2, 2) = 2
- Inner Loop (j = 3):
Subarray: [5, 6, 7] - current_min = 5, current_max = 7
- |current_max - current_min| = |7 - 5| = 2 (satisfies limit)
- max_length = max(2, 3) = 3
- Inner Loop (j = 4):
Subarray: [5, 6, 7, 8] - current_min = 5, current_max = 8
- |current_max - current_min| = |8 - 5| = 3 (satisfies limit)
- max_length = max(3, 4) = 4
- Inner Loop (j = 5):
Subarray: [5, 6, 7, 8, 10] - current_min = 5, current_max = 10
- |current_max - current_min| = |10 - 5| = 5 (violates limit)
- Break.
i = 2:
Subarray starts at index 2
- Inner Loop (j = 2):
Subarray: [6] - current_min = 6, current_max = 6
- |current_max - current_min| = |6 - 6| = 0 (satisfies limit)
- max_length = max(4, 1) = 4
- Inner Loop (j = 3):
Subarray: [6, 7] - current_min = 6, current_max = 7
- |current_max - current_min| = |7 - 6| = 1 (satisfies limit)
- max_length = max(4, 2) = 4
- Inner Loop (j = 4):
Subarray: [6, 7, 8] - current_min = 6, current_max = 8
- |current_max - current_min| = |8 - 6| = 2 (satisfies limit)
- max_length = max(4, 3) = 4
- Inner Loop (j = 5):
Subarray: [6, 7, 8, 10] - current_min = 6, current_max = 10
- |current_max - current_min| = |10 - 6| = 4 (satisfies limit)
- max_length = max(4, 4) = 4
- Inner Loop (j = 6):
Subarray: [6, 7, 8, 10, 6] - current_min = 6, current_max = 10
- |current_max - current_min| = |10 - 6| = 4 (satisfies limit)
- max_length = max(4, 5) = 5
Final Answer:
The longest subarray that satisfies the condition has a length of 5.
Example subarray: [6, 7, 8, 10, 6].
Brute Force Code in all Languages
1. C++ Try on Compiler
class Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
int n = nums.size();
int max_length = 0; // Store the maximum length of valid subarrays
// Iterate over all possible starting points of subarrays
for (int i = 0; i < n; i++) {
int current_min = INT_MAX; // Track the minimum in the current subarray
int current_max = INT_MIN; // Track the maximum in the current subarray
// Iterate over all possible ending points
for (int j = i; j < n; j++) {
// Update the minimum and maximum for the current subarray
current_min = min(current_min, nums[j]);
current_max = max(current_max, nums[j]);
// Check if the condition is satisfied
if (abs(current_max - current_min) <= limit) {
// Update the maximum length
max_length = max(max_length, j - i + 1);
} else {
break; // Stop further processing for this subarray
}
}
}
return max_length; // Return the maximum length found
}
};2. Java Try on Compiler
class Solution {
public int longestSubarray(int[] nums, int limit) {
int n = nums.length;
int maxLength = 0; // Store the maximum length of valid subarrays
// Iterate over all possible starting points of subarrays
for (int i = 0; i < n; i++) {
int currentMin = Integer.MAX_VALUE; // Track the minimum in the current subarray
int currentMax = Integer.MIN_VALUE; // Track the maximum in the current subarray
// Iterate over all possible ending points
for (int j = i; j < n; j++) {
// Update the minimum and maximum for the current subarray
currentMin = Math.min(currentMin, nums[j]);
currentMax = Math.max(currentMax, nums[j]);
// Check if the condition is satisfied
if (Math.abs(currentMax - currentMin) <= limit) {
// Update the maximum length
maxLength = Math.max(maxLength, j - i + 1);
} else {
break; // Stop further processing for this subarray
}
}
}
return maxLength; // Return the maximum length found
}
}3. Python Try on Compiler
class Solution:
def longestSubarray(self, nums: List[int], limit: int) -> int:
max_length = 0 # Store the maximum length of valid subarrays
# Iterate over all possible starting points of subarrays
for i in range(len(nums)):
current_min = float('inf') # Track the minimum in the current subarray
current_max = float('-inf') # Track the maximum in the current subarray
# Iterate over all possible ending points
for j in range(i, len(nums)):
# Update the minimum and maximum for the current subarray
current_min = min(current_min, nums[j])
current_max = max(current_max, nums[j])
# Check if the condition is satisfied
if abs(current_max - current_min) <= limit:
# Update the maximum length
max_length = max(max_length, j - i + 1)
else:
break # Stop further processing for this subarray
return max_length4. JavaScript Try on Compiler
/**
* @param {number[]} nums
* @param {number} limit
* @return {number}
*/
var longestSubarray = function(nums, limit) {
let maxLength = 0; // Store the maximum length of valid subarrays
// Iterate over all possible starting points of subarrays
for (let i = 0; i < nums.length; i++) {
let currentMin = Infinity; // Track the minimum in the current subarray
let currentMax = -Infinity; // Track the maximum in the current subarray
// Iterate over all possible ending points
for (let j = i; j < nums.length; j++) {
// Update the minimum and maximum for the current subarray
currentMin = Math.min(currentMin, nums[j]);
currentMax = Math.max(currentMax, nums[j]);
// Check if the condition is satisfied
if (Math.abs(currentMax - currentMin) <= limit) {
// Update the maximum length
maxLength = Math.max(maxLength, j - i + 1);
} else {
break; // Stop further processing for this subarray
}
}
}
return maxLength; // Return the maximum length found
};Time Complexity: O(n^2)
Outer Loop (Iterating through starting indices):
The outer loop runs from i = 0 to i = nums.length - 1. Hence, it iterates n times, where n is the length of the nums array.
Inner Loop (Iterating through ending indices):
For each iteration of the outer loop, the inner loop runs from j = i to j = nums.length - 1.
Operations Inside the Loops:
Within the inner loop, we calculate the min and max of the current subarray and check the condition. These are O(1) operations.
Therefore, the Overall Time Complexity is O(n^2).
Space Complexity: O(n)
Auxiliary Space Complexity
Auxiliary space complexity refers to the extra space or temporary space used by an algorithm, excluding the input data. In this solution:
The function uses a constant amount of space for variables: maxLength, currentMin, currentMax, i, and j.
So, Auxiliary Space Complexity is O(1)
Total Space Complexity
Input Space:The input array nums takes O(n) space.
Auxiliary Space:As calculated, the auxiliary space complexity is O(1).
Total Space Complexity:O(n)
For large input sizes (e.g , n = 10^5), the total number of iterations in the worst case is approximately O(n^2) , which translates to 10^10 operations, far exceeding the permissible time limit for competitive programming or high-performance systems.
The interviewer will not be happy with the Brute Force solution. We need to optimize to move further in the interview.
Optimized Approach (Use of Sliding Window)
Intuition
What did we observe to be in-efficient in the Brute Force approach?
If you generate all possible subarrays and check each one individually, it results in a time complexity of O(n^2) (because there are approximately n^2 subarrays for an array of size n).
Additionally, finding the maximum and minimum for each subarray requires iterating through that subarray, which adds another factor to the time complexity.
For large arrays, this becomes very inefficient and can lead to TLE (Time Limit Exceeded) in competitive programming, where n can be up to 100,000 or more.
Key Observations:
- Subarrays with Similar Properties:
- If the maximum and minimum values for a subarray satisfy the condition, then all smaller subarrays within this larger subarray (that start from the same left index) will also likely satisfy the condition. This suggests that we don’t need to recheck subarrays from scratch.
- Max and Min Relationships:
- We care only about the maximum and minimum values of a subarray at any given time since the condition is based on the difference between these two values. Once we know the max and min, we can quickly decide whether the subarray is valid or not.
- Dynamic Subarray Expansion and Contraction:
- As we move through the array, we can expand the subarray by adding elements from the right and shrink it from the left if the condition is violated.
From the third Key Observation, what can we derive?
We are assuming a "frame" which has integers in it. We dynamically adjust it according to our conditions.
Yes, the frame will have two ends, the left end and the right end.
Let's call this "frame" a "window," which will dynamically change its size.
We will keep on adding the elements into/expanding the window until our conditions are satisfied. We will shrink the window size whenever the conditions are violated.
The window tends to slide whenever it expands and shrinks, let's call it the "sliding window".
When the window expands, we will increment our right pointer and include all the elements encountered into the frame.
When the window shrinks, we will increment the left pointer which will exclude the elements which were present inside the frame.
That means, in one go we are able to know which subarray to be considered and which is to not.
We are not done yet !!
The sliding window approach gives us a framework to maintain a valid subarray, but we still need an efficient way to track the maximum and minimum values in the current window.
Is there a way where we can get to know the maximum and minimum values within that subarray in constant time?
We can think of PriorityQueue (Heap), but is it efficient?
No, because it takes O(nlogn) for insertion operation.
What else can we think of?
We can think of maintaining a Deque (Double Ended Queue).
Why using a Deque(Double Ended Queue) ?
- A deque (double-ended queue) allows us to add and remove elements from both ends in constant time, which is perfect for this scenario.
- We need to track the max and min of the current window as we expand or contract the window. If we used a simple array or list to track these values, we'd have to iterate through the entire window every time we expand or shrink it, which would be inefficient (O(n) for each adjustment).
- A deque, on the other hand, allows us to maintain the max and min in constant time.
Cool, How will we make use of this data structure?
We will be using two Deques, one is maxDeque and the other will be minDeque.
- maxDeque ensures that the largest element is always at the front of the deque, and we can access it in constant time.
- minDeque ensures the smallest element is always at the front, and we can access it in constant time.
How does the Deque work for max and min?
Max Deque:
- We maintain the deque in decreasing order (largest at the front).
- As we add new elements to the window, we remove elements from the back of the deque if they are smaller than the new element because they are no longer useful for tracking the maximum.
Min Deque:
- We maintain the deque in increasing order (smallest at the front).
- Similarly, we remove elements from the back of the deque if they are larger than the new element because they can no longer contribute to tracking the minimum.
Why is the Deque efficient?
- Each element is added and removed from the deque at most once, meaning the time complexity for maintaining the deque is O(n).
- As a result, using deques allows us to keep track of the max and min in constant time and ensures that the entire algorithm runs in O(n) time complexity.
Now, let’s summarize how the sliding window and deque come together to solve the problem optimally:
- Sliding Window:
- We expand the window by moving the right pointer (j).
- If the current window is invalid (i.e., the difference between max and min exceeds the limit), we shrink the window by moving the left pointer (i).
- Deque for Max and Min:
- We use two deques, one for tracking the max and one for the min.
- As the window expands, we update the deques to maintain the max and min values efficiently.
- The deques allow us to access the current max and min in constant time.
- Efficiency:
- The sliding window ensures that each element is processed at most twice (once when expanding and once when contracting the window).
- The deques help us maintain the max and min values in constant time, making the entire solution run in O(n) time.
How To Approach This Problem
- Initialize Variables:Create two deques: maxDeque (for tracking the maximum value) and minDeque (for tracking the minimum value).Set left (start of the window) to 0 and maxLength to 0.
- Expand the Window (right pointer):For each element at index right:Update maxDeque and minDeque to maintain the maximum and minimum values in the window.
- Check Window Validity:If the absolute difference between the values at the front of maxDeque and minDeque exceeds the limit:Increment left to shrink the window from the left and remove any outdated indices from the deques.
- Update Maximum Length:Update maxLength with the current window size (right - left + 1).
- Return Result:After iterating, return maxLength, which holds the longest valid subarray length.
Let's Visualize with a Video
Dry-Run
Input:
nums = [1, 5, 6, 7, 8, 10, 6, 5, 6]
limit = 4
Explanation: The longest subarray that satisfies the condition has a length of 5. The longest subarray is [6, 7, 8, 10, 6].
Initialization:
maxDeque = [] (To track indices of the maximum values)
minDeque = [] (To track indices of the minimum values)
left = 0 (The starting index of the window)
maxLength = 0 (The length of the longest valid subarray)
Step-by-Step Dry Run:
Iteration 1: right = 0 (nums[0] = 1)
maxDeque: Add 0 to maxDeque (since it's the first element, it's both max and min).
minDeque: Add 0 to minDeque.
Condition: The absolute difference between the max (1) and min (1) is 0, which is less than or equal to the limit.
Update maxLength: maxLength = max(0, 0 - 0 + 1) = 1.
_________________________________________________________________________________________________________
Iteration 2: right = 1 (nums[1] = 5)
maxDeque: Remove 0 (nums[0] = 1) from the back of maxDeque because 5 > 1.
Add 1 to maxDeque.
minDeque: Add 1 to minDeque.
Condition: The absolute difference between max (5) and min (1) is 4, which is equal to the limit.
Update maxLength: maxLength = max(1, 1 - 0 + 1) = 2.
_________________________________________________________________________________________________________
Iteration 3: right = 2 (nums[2] = 6)
maxDeque: Remove 1 (nums[1] = 5) from the back of maxDeque because 6 > 5.
Add 2 to maxDeque.
minDeque: Add 2 to minDeque.
Condition: The absolute difference between max (6) and min (1) is 5, which exceeds the limit (4).
Shrink the window: Move left to 1. Remove 0 from maxDeque and minDeque.
Update maxLength: maxLength = max(2, 2 - 1 + 1) = 2.
_________________________________________________________________________________________________________
Iteration 4: right = 3 (nums[3] = 7)
maxDeque: Remove 2 (nums[2] = 6) from the back of maxDeque because 7 > 6.
Add 3 to maxDeque.
minDeque: Add 3 to minDeque.
Condition: The absolute difference between max (7) and min (5) is 2, which is less than or equal to the limit.
Update maxLength: maxLength = max(2, 3 - 1 + 1) = 3.
__________________________________________________________________________________________________________
Iteration 5: right = 4 (nums[4] = 8)
maxDeque: Remove 3 (nums[3] = 7) from the back of maxDeque because 8 > 7.
Add 4 to maxDeque.
minDeque: Add 4 to minDeque.
Condition: The absolute difference between max (8) and min (5) is 3, which is less than or equal to the limit.
Update maxLength: maxLength = max(3, 4 - 1 + 1) = 4.
__________________________________________________________________________________________________________
Iteration 6: right = 5 (nums[5] = 10)
maxDeque: Remove 4 (nums[4] = 8) from the back of maxDeque because 10 > 8.
Add 5 to maxDeque.
minDeque: Add 5 to minDeque.
Condition: The absolute difference between max (10) and min (5) is 5, which exceeds the limit.
Shrink the window: Move left to 2. Remove 1 from maxDeque and minDeque.
Update maxLength: maxLength = max(4, 5 - 2 + 1) = 4.
__________________________________________________________________________________________________________
Iteration 7: right = 6 (nums[6] = 6)
maxDeque: Add 6 to maxDeque.
minDeque: Remove 2 (nums[2] = 5) from the back of minDeque because 6 > 5.
Add 6 to minDeque.
Condition: The absolute difference between max (10) and min (6) is 4, which is equal to the limit.
Update maxLength: maxLength = max(4, 6 - 2 + 1) = 5.
_________________________________________________________________________________________________________
Iteration 8: right = 7 (nums[7] = 5)
maxDeque: Add 7 to maxDeque.
minDeque: Remove 6 (nums[6] = 6) from the back of minDeque because 5 < 6.
Add 7 to minDeque.
Condition: The absolute difference between max (10) and min (5) is 5, which exceeds the limit.
Shrink the window: Move left to 3. Remove 3 from maxDeque and minDeque.
Update maxLength: maxLength = max(5, 7 - 3 + 1) = 5.
__________________________________________________________________________________________________________
Iteration 9: right = 8 (nums[8] = 6)
maxDeque: Add 8 to maxDeque.
minDeque: Remove 7 (nums[7] = 5) from the back of minDeque because 6 > 5.
Add 8 to minDeque.
Condition: The absolute difference between max (10) and min (6) is 4, which is equal to the limit.
Update maxLength: maxLength = max(5, 8 - 3 + 1) = 5.
__________________________________________________________________________________________________________
Final Answer:
The longest valid subarray is of length 5.
Thus, the output for the input nums = [1, 5, 6, 7, 8, 10, 6, 5, 6] and limit = 4 is 5.
Optimal Codes in all Languages
1. C++ Try on Compiler
class Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
// Declare deques to track the max and min values within the current window
std::deque<int> maxDeque, minDeque;
// Initialize left pointer for the sliding window
int left = 0;
int maxLength = 0; // Variable to store the maximum length of the valid subarray
// Iterate through the array with right pointer
for (int right = 0; right < nums.size(); right++) {
// Maintain the max deque: remove all elements smaller than the current element
while (!maxDeque.empty() && nums[maxDeque.back()] < nums[right]) {
maxDeque.pop_back();
}
maxDeque.push_back(right); // Add current element index to the max deque
// Maintain the min deque: remove all elements larger than the current element
while (!minDeque.empty() && nums[minDeque.back()] > nums[right]) {
minDeque.pop_back();
}
minDeque.push_back(right); // Add current element index to the min deque
// Shrink the window from the left if the absolute difference condition is violated
while (nums[maxDeque.front()] - nums[minDeque.front()] > limit) {
// If the leftmost index of max deque is out of the window, pop it
if (maxDeque.front() == left) {
maxDeque.pop_front();
}
// If the leftmost index of min deque is out of the window, pop it
if (minDeque.front() == left) {
minDeque.pop_front();
}
left++; // Move left pointer to shrink the window
}
// Calculate the maximum length of the subarray
maxLength = std::max(maxLength, right - left + 1);
}
return maxLength; // Return the result
}
};2. Java Try on Compiler
class Solution {
public int longestSubarray(int[] nums, int limit) {
// Declare deques to track the max and min values within the current window
Deque<Integer> maxDeque = new LinkedList<>();
Deque<Integer> minDeque = new LinkedList<>();
// Initialize left pointer for the sliding window
int left = 0;
int maxLength = 0; // Variable to store the maximum length of the valid subarray
// Iterate through the array with right pointer
for (int right = 0; right < nums.length; right++) {
// Maintain the max deque: remove all elements smaller than the current element
while (!maxDeque.isEmpty() && nums[maxDeque.peekLast()] < nums[right]) {
maxDeque.pollLast();
}
maxDeque.offerLast(right); // Add current element index to the max deque
// Maintain the min deque: remove all elements larger than the current element
while (!minDeque.isEmpty() && nums[minDeque.peekLast()] > nums[right]) {
minDeque.pollLast();
}
minDeque.offerLast(right); // Add current element index to the min deque
// Shrink the window from the left if the absolute difference condition is violated
while (nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > limit) {
// If the leftmost index of max deque is out of the window, poll it
if (maxDeque.peekFirst() == left) {
maxDeque.pollFirst();
}
// If the leftmost index of min deque is out of the window, poll it
if (minDeque.peekFirst() == left) {
minDeque.pollFirst();
}
left++; // Move left pointer to shrink the window
}
// Calculate the maximum length of the subarray
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength; // Return the result
}
}3. Python Try on Compiler
class Solution:
def longestSubarray(self, nums: List[int], limit: int) -> int:
# Deques to track the indices of maximum and minimum values in the current window
maxDeque = deque()
minDeque = deque()
left = 0
maxLength = 0 # Variable to store the maximum length of the valid subarray
# Iterate through the array with right pointer
for right in range(len(nums)):
# Maintain the max deque: remove all elements smaller than the current element
while maxDeque and nums[maxDeque[-1]] < nums[right]:
maxDeque.pop()
maxDeque.append(right) # Add current element index to the max deque
# Maintain the min deque: remove all elements larger than the current element
while minDeque and nums[minDeque[-1]] > nums[right]:
minDeque.pop()
minDeque.append(right) # Add current element index to the min deque
# Shrink the window from the left if the absolute difference condition is violated
while nums[maxDeque[0]] - nums[minDeque[0]] > limit:
# If the leftmost index of max deque is out of the window, pop it
if maxDeque[0] == left:
maxDeque.popleft()
# If the leftmost index of min deque is out of the window, pop it
if minDeque[0] == left:
minDeque.popleft()
left += 1 # Move left pointer to shrink the window
# Calculate the maximum length of the subarray
maxLength = max(maxLength, right - left + 1)
return maxLength # Return the result4. JavaScript Try on Compiler
/**
* @param {number[]} nums
* @param {number} limit
* @return {number}
*/
var longestSubarray = function(nums, limit) {
// Declare deques to track the max and min values within the current window
let maxDeque = [];
let minDeque = [];
let left = 0;
let maxLength = 0; // Variable to store the maximum length of the valid subarray
// Iterate through the array with right pointer
for (let right = 0; right < nums.length; right++) {
// Maintain the max deque: remove all elements smaller than the current element
while (maxDeque.length && nums[maxDeque[maxDeque.length - 1]] < nums[right]) {
maxDeque.pop();
}
maxDeque.push(right); // Add current element index to the max deque
// Maintain the min deque: remove all elements larger than the current element
while (minDeque.length && nums[minDeque[minDeque.length - 1]] > nums[right]) {
minDeque.pop();
}
minDeque.push(right); // Add current element index to the min deque
// Shrink the window from the left if the absolute difference condition is violated
while (nums[maxDeque[0]] - nums[minDeque[0]] > limit) {
// If the leftmost index of max deque is out of the window, pop it
if (maxDeque[0] === left) {
maxDeque.shift();
}
// If the leftmost index of min deque is out of the window, pop it
if (minDeque[0] === left) {
minDeque.shift();
}
left++; // Move left pointer to shrink the window
}
// Calculate the maximum length of the subarray
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength; // Return the result
};
Time Complexity: O(n)
The time complexity is O(n) because we traverse through the array once, and for each element, we perform operations like adding and removing indices from the deques, which happen at most once per element. Hence, the overall time complexity remains linear, proportional to the size of the input array.
Space Complexity: O(n)
Auxiliary Space Complexity:
The auxiliary space complexity is O(n), primarily due to the two deques (maxDeque and minDeque). Each deque can store up to n elements in the worst case, so the space used by both deques is linear with respect to the number of elements in the array.
Total Space Complexity:
The total space complexity is also O(n). This includes the space for the input array, which requires O(n) space, and the two deques used to store the indices of the current window’s maximum and minimum values. Since both the array and deques require space proportional to the size of the input, the overall space complexity is linear.
Learning Tip:
Explore more about Deque (Double Ended Queue).
- Count the Number of Substrings With Dominant Ones
- Minimum Size Subarray Sum
- Longest Repeating Character Replacement
You are given an integer array nums and two integers minK and maxK.
A fixed-bound subarray of nums is a subarray that satisfies the following conditions:
- The minimum value in the subarray is equal to minK.
- The maximum value in the subarray is equal to maxK.
Return the number of fixed-bound subarrays.
A subarray is a contiguous part of an array.
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.