Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

MEDIUM

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 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 <= 10⁵
1 <= nums[i] <= 10⁹
0 <= limit <= 10⁹

Approaches

Checkout 3 different approaches to solve Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Optimization

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 i from 0 to n-1 (this will be the start of the subarray).
Inside this loop, initialize minVal = nums[i] and maxVal = nums[i].
Start a second loop with an index j from i to n-1 (this will be the end of the subarray).
Update minVal = min(minVal, nums[j]) and maxVal = max(maxVal, nums[j]).
If maxVal - minVal <= limit, update maxLength = 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.

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 Analysis

Time Complexity: O(n^2), where n is the length of `nums`. The two nested loops dominate the runtime.Space Complexity: O(1), as we only use a few variables to store the state.

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

Inefficient for large inputs, leading to a "Time Limit Exceeded" error on most platforms.

Code Solutions

Checking out 3 solutions in different languages for Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Patterns:

Sliding Window

Data Structures:

ArrayHeap (Priority Queue)Ordered SetQueueMonotonic Queue

Companies:

Nutanix |Visa |eBay |Capital One |