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

How to solve Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (LeetCode 1438): the approach in brief

The problem

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.

Pattern

Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit is a Sliding Window problem, in the Variable Size (Condition-Based) subpattern. The pattern covers fixed-size, variable-size, and character frequency matching window techniques

Master variable-size sliding window for condition-based problems like longest substring without repeating characters.

Approach outline

1. Use a sliding window approach keeping the maximum and minimum value using a data structure like a multiset from STL in C++.
2. More specifically, use the two pointer technique, moving the right pointer as far as possible to the right until the subarray is not valid (maxValue - minValue > limit), then moving the left pointer until the subarray is valid again (maxValue - minValue <= limit). Keep repeating this process.

Complexity

The reference solution runs in O(n) time and O(n) space.

Asked at

Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit has been reported in interviews at Google.