1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (LeetCode 1438) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.
How to solve Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit is a Variable Size Sliding Window problem, part of Sliding Window. Master variable-size sliding window for condition-based problems like longest substring without repeating characters.
Work towards the solution in these steps:
- Use a sliding window approach keeping the maximum and minimum value using a data structure like a multiset from STL in C++.
- 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.
The reference solution runs in O(n) time and O(n) space.
The Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit solution and editorial walks through the full approach with reference code.
Problem statement
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 <= 105
- 1 <= nums[i] <= 109
- 0 <= limit <= 109
Topics and companies
Topics: Array, Queue, Sliding Window, Heap (Priority Queue), Ordered Set, Monotonic Queue.
Reported in interviews at Google.
How to practise Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.
Open Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit in the code editor, or read the Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit editorial for a worked solution with its approach and complexity analysis.
Where Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit sits in the DSA pattern sheet
Problems related to Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Other problems that use the same Variable Size (Condition-Based) and Sliding Window techniques:
- Contains Duplicate II — Easy, same subpattern
- Continuous Subarrays — Medium, same subpattern
- Find Longest Special Substring That Occurs Thrice I — Medium, same subpattern
- Frequency of the Most Frequent Element — Medium, same subpattern
- Fruit Into Baskets — Medium, same subpattern
- Jump Game VII — Medium, same subpattern
Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit FAQ
What is the LeetCode number of Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit?
Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit is LeetCode problem 1438, rated Medium.
What pattern is used to solve Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit?
Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit is a Variable Size Sliding Window problem. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.
What is the time complexity of Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit?
The reference solution runs in O(n) time and O(n) space.
Which companies ask Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit?
Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit has been reported in interviews at Google.