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

Medium

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

Example 4:

Input: nums = [2,2,2,4,4,2,5,5,5,5,5,2], limit = 2
Output: 6

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
0 <= limit <= 10⁹

Solution:

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $limit
     * @return Integer
     */
    function longestSubarray($nums, $limit) {
        $ans = 1;
        $minQ = new SplDoublyLinkedList();
        $maxQ = new SplDoublyLinkedList();

        for ($l = 0, $r = 0; $r < count($nums); ++$r) {
            while (!$minQ->isEmpty() && $minQ->top() > $nums[$r])
                $minQ->pop();
            $minQ->push($nums[$r]);
            while (!$maxQ->isEmpty() && $maxQ->top() < $nums[$r])
                $maxQ->pop();
            $maxQ->push($nums[$r]);
            while ($maxQ->bottom() - $minQ->bottom() > $limit) {
                if ($minQ->bottom() == $nums[$l])
                    $minQ->shift();
                if ($maxQ->bottom() == $nums[$l])
                    $maxQ->shift();
                ++$l;
            }
            $ans = max($ans, $r - $l + 1);
        }

        return $ans;
    }
}

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub