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

Medium

Capital One

0 views

Topics:

ArraysSliding WindowsTwo Pointers

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⁹

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

Medium

Capital One

0 views

Topics:

ArraysSliding WindowsTwo Pointers

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⁹

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `nums` and the value of `limit`?
Can the input array `nums` contain negative numbers, zeros, or floating-point numbers?
If no subarray satisfies the condition (absolute difference <= limit), what should I return?
Are there any specific edge cases I should consider, such as an empty input array or an array with only one element?
If multiple subarrays have the maximum length and satisfy the condition, do I need to return a specific one (e.g., the first one found), or can I return any valid one?

Brute Force Solution

Approach

The brute force strategy involves checking every possible group of numbers within the list. We essentially look at every possible continuous section of numbers to see if it meets the specified condition.

Here's how the algorithm would work step-by-step:

Start by looking at the very first number in the list as a single group.
Then, expand the group by including the next number, so now it's the first two numbers.
Keep expanding the group, one number at a time, always starting from the first number in the list.
For each of these groups, find the biggest and smallest numbers in that group.
Calculate the difference between the biggest and smallest numbers in the group.
If the difference is less than or equal to the specified limit, then this group is valid. Otherwise, it's not.
After checking all groups starting from the first number, move on to the second number in the list and repeat the process of expanding the group and checking the difference.
Continue this process, moving one number at a time, until you've checked all possible starting points and all possible group sizes.
Keep track of the length of the longest valid group you find during this entire process.
The longest valid group found is the answer.

Code Implementation

def longest_subarray_brute_force(numbers, limit):
    longest_subarray_length = 0

    for start_index in range(len(numbers)):
        for end_index in range(start_index, len(numbers)):
            # Create the subarray to inspect
            current_subarray = numbers[start_index:end_index + 1]

            maximum_value = float('-inf')
            minimum_value = float('inf')

            for number in current_subarray:
                maximum_value = max(maximum_value, number)
                minimum_value = min(minimum_value, number)

            # Check if the current subarray meets the condition
            if (maximum_value - minimum_value) <= limit:
                
                # Update the length of the longest subarray
                longest_subarray_length = max(longest_subarray_length, len(current_subarray))

    return longest_subarray_length

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n³) – The outer loop iterates through each of the n elements of the input array. The inner loop expands the subarray starting from the current element of the outer loop, resulting in another n iterations in the worst case. Inside the inner loop, finding the maximum and minimum values in the subarray takes O(n) time. Therefore, the total time complexity is n * n * n, which simplifies to O(n³).

Space Complexity

O(1) – The brute force approach described primarily uses a few variables to track the start and end of the subarray being considered, as well as the maximum and minimum values within that subarray. The space used for these variables does not scale with the input size (N, the number of elements in the list). No additional data structures, such as auxiliary arrays or hash maps, are created to store intermediate results. Thus, the auxiliary space used is constant, resulting in a space complexity of O(1).

Optimal Solution

Approach

The goal is to find the longest group of numbers where the difference between the biggest and smallest number in that group is within a specific limit. We can efficiently track the biggest and smallest numbers as we move through the larger list of numbers, adjusting the group's start to meet the difference limit, without re-checking every possible group.

Here's how the algorithm would work step-by-step:

Imagine you have a sliding window that moves across the numbers.
Keep track of the biggest and smallest numbers within the current window.
If the difference between the biggest and smallest is okay (within the limit), expand the window by moving its right edge to include the next number.
If the difference is too big (exceeds the limit), shrink the window by moving its left edge to exclude the earliest numbers until the difference is okay again.
At each position, remember the size of the largest valid window you've found so far.
Continue sliding the window across all the numbers, adjusting its size as needed.
In the end, the largest valid window size you remembered is your answer.

Code Implementation

def longestSubarray(numbers, absolute_difference_limit):
    window_start = 0
    max_length = 0
    min_queue = []
    max_queue = []

    for window_end in range(len(numbers)):
        number = numbers[window_end]

        while min_queue and numbers[min_queue[-1]] >= number:
            min_queue.pop()
        min_queue.append(window_end)

        while max_queue and numbers[max_queue[-1]] <= number:
            max_queue.pop()
        max_queue.append(window_end)

        # Ensure the absolute difference condition is met.
        while numbers[max_queue[0]] - numbers[min_queue[0]] > absolute_difference_limit:
            
            # Shrink the window from the left until the condition holds.
            window_start += 1

            if min_queue[0] < window_start:
                min_queue.pop(0)
            if max_queue[0] < window_start:
                max_queue.pop(0)

        # Update max length with the current window size.
        max_length = max(max_length, window_end - window_start + 1)

    return max_length

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n using a sliding window. While the outer loop iterates up to n times, the inner loop (shrinking the window) ensures that each element is visited and removed from the window at most once. Therefore, the total number of operations is proportional to n, resulting in a time complexity of O(n).

Space Complexity

O(N) – The provided explanation uses a sliding window and needs to keep track of the biggest and smallest numbers within the current window. This can be efficiently implemented using data structures like a monotonically increasing queue and a monotonically decreasing queue (or similar structures like sorted lists) to track the maximum and minimum values within the sliding window. In the worst-case scenario, these queues could potentially store all N elements of the input array, leading to O(N) auxiliary space. The algorithm also uses a few constant space variables, but they are insignificant compared to the size of the queues.

Edge Cases

Case	How to Handle
Empty input array (nums is null or has length 0)	Return 0 as there's no subarray to consider.
Input array with only one element	Return 1 since a single element satisfies the condition.
All elements in the input array are identical	The longest subarray will be the entire array, so return the length of the array.
All elements differ by more than the limit	The longest subarray will have a length of 1.
Array contains very large positive or negative numbers, potentially causing integer overflow in calculations	Use appropriate data types (e.g., long) to prevent overflow during difference calculations.
Limit is zero	The subarray can only consist of identical numbers; sliding window should handle this correctly.
Large input array (e.g., 10^5 elements) - consider time complexity	Use a sliding window approach with a min/max deque for O(n) time complexity to avoid exceeding time limits.
Array contains both very large positive and very large negative numbers	The absolute difference calculation should still be correct given appropriate data types (e.g., long).