Advanced Coding Patterns for Interviews

0% completed

Previous
Next
Solution: Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Problem Statement

Given an integer array nums and an integer limit, return the maximum length of a continuous subarray such that the absolute difference between any two elements in this subarray is less than or equal to limit. The subarray must be non-empty.

Examples

Example 1:

  • Input: nums = [1, 3, 6, 7, 9, 10], limit = 3
  • Output: 3
  • Explanation: Consider the [6, 7, 9] or [7, 9, 10] array. The absolute difference between any two elements in these subarrays is at most 3.

Example 2:

  • Input: nums = [8, 2, 4, 10, 12], limit = 6
  • Output: 3
  • Explanation: The longest subarray is [8, 2, 4]. The absolute difference between any two elements in this subarray is at most 6.

Example 3:

  • Input: nums = [1, 5, 9, 13, 14], limit = 4
  • Output: 2
  • Explanation: Consider the [1, 5], [5, 9], [9, 13] or [13, 14] array. The absolute difference between any two elements in these subarrays is at most 4.

Constraints:

  • 1 <= nums.length <= 10<sup>5</sup>
  • 1 <= nums[i] <= 10<sup>9</sup>
  • 0 <= limit <= 10<sup>9</sup>

Solution

To solve this problem, we employ the Monotonic Queue technique to maintain two deques: one for tracking the maximum values and one for tracking the minimum values within the current window (subarray). The idea is to expand the window by moving the end pointer while checking if the difference between the maximum and minimum elements within this window exceeds the given limit. If it does, we shrink the window by moving the start pointer until the difference is within the limit. The length of the window is tracked to determine the maximum length of any valid subarray.

This approach works because the deques allow us to efficiently maintain and update the maximum and minimum values in the window, which enables us to check the conditions and adjust the window size in an optimal manner.

Step-by-Step Algorithm

  1. Initialize Data Structures:

    • Create two empty deques: maxDeque for storing indices of elements in decreasing order (to track the maximum values) and minDeque for storing indices in increasing order (to track the minimum values).
    • Initialize two integer variables, start and maxLength, to 0. start will represent the beginning of the current subarray, and maxLength will store the maximum length of the valid subarray found.

  2. Iterate Through the Array:

    • Use a for-loop with end iterating from 0 to nums.length - 1. end represents the end of the current subarray.

  3. Update maxDeque:

    • While maxDeque is not empty and the value at nums[end] is greater than or equal to the value at nums[maxDeque.peekLast()], remove the last element from maxDeque.
      Reason: We want to keep the largest element at the front of maxDeque.
    • Add the current index end to maxDeque.

  4. Update minDeque:

    • While minDeque is not empty and the value at nums[end] is less than or equal to the value at nums[minDeque.peekLast()], remove the last element from minDeque.
      Reason: We want to keep the smallest element at the front of minDeque.
    • Add the current index end to minDeque.

  5. Check the Condition:

    • While the difference between the values at nums[maxDeque.peekFirst()] and nums[minDeque.peekFirst()] is greater than limit, perform the following steps:
      • Increment the start pointer by 1 to shrink the window from the left.
      • If maxDeque.peekFirst() is less than start, remove the first element from maxDeque. Reason: We are no longer considering elements before the start index.
      • If minDeque.peekFirst() is less than start, remove the first element from minDeque. Reason: We are no longer considering elements before the start index.

  6. Update Maximum Length:

    • Calculate the length of the current window as end - start + 1.
    • Update maxLength to be the maximum of its current value and the current window length.

  7. Return Result:

    • After completing the loop, return maxLength, which contains the length of the longest subarray satisfying the condition.

Algorithm Walkthrough

Let's walk through the algorithm with the input nums = [1, 3, 6, 7, 9, 10] and limit = 3.

Image

  1. Initial State:

    • maxDeque = [], minDeque = [], start = 0, maxLength = 0

  2. Iteration 1 (end = 0):

    • Value: nums[0] = 1
    • Update maxDeque: maxDeque = [0] (1 is the only element, so it remains)
    • Update minDeque: minDeque = [0] (1 is the only element, so it remains)
    • Condition Check: The difference is nums[0] - nums[0] = 0 (within the limit)
    • Update maxLength: maxLength = max(0, 0 - 0 + 1) = 1

  3. Iteration 2 (end = 1):

    • Value: nums[1] = 3
    • Update maxDeque: maxDeque = [1] (3 is greater than 1, so remove index 0)
    • Update minDeque: minDeque = [0, 1] (3 is greater than 1, so add index 1)
    • Condition Check: The difference is nums[1] - nums[0] = 3 - 1 = 2 (within the limit)
    • Update maxLength: maxLength = max(1, 1 - 0 + 1) = 2

  4. Iteration 3 (end = 2):

    • Value: nums[2] = 6
    • Update maxDeque: maxDeque = [2] (6 is greater than 3, so remove index 1)
    • Update minDeque: minDeque = [0, 1, 2] (6 is greater than 3, so add index 2)
    • Condition Check: The difference is nums[2] - nums[0] = 6 - 1 = 5 (exceeds the limit)
    • Adjust start: Move start to 1 (increment by 1)
    • Update Deques: Remove 0 from minDeque since it is out of the window (minDeque = [1, 2])
    • Update maxLength: maxLength = max(2, 2 - 1 + 1) = 2

  5. Iteration 4 (end = 3):

    • Value: nums[3] = 7
    • Update maxDeque: maxDeque = [3] (7 is greater than 6, so remove index 2)
    • Update minDeque: minDeque = [1, 2, 3] (7 is greater than 6, so add index 3)
    • Condition Check: The difference is nums[3] - nums[1] = 7 - 3 = 4 (exceeds the limit)
    • Adjust start: Move start to 2 (increment by 1)
    • Update Deques: Remove 1 from minDeque since it is out of the window (minDeque = [2, 3])
    • Update maxLength: maxLength = max(2, 3 - 2 + 1) = 2

  6. Iteration 5 (end = 4):

    • Value: nums[4] = 9
    • Update maxDeque: maxDeque = [4] (9 is greater than 7, so remove index 3)
    • Update minDeque: minDeque = [2, 3, 4] (9 is greater than 7, so add index 4)
    • Condition Check: The difference is nums[4] - nums[2] = 9 - 6 = 3 (within the limit)
    • Update maxLength: maxLength = max(2, 4 - 2 + 1) = 3

  7. Iteration 6 (end = 5):

    • Value: nums[5] = 10
    • Update maxDeque: maxDeque = [5] (10 is greater than 9, so remove index 4)
    • Update minDeque: minDeque = [2, 3, 4, 5] (10 is greater than 9, so add index 5)
    • Condition Check: The difference is nums[5] - nums[2] = 10 - 6 = 4 (exceeds the limit)
    • Adjust start: Move start to 3 (increment by 1)
    • Update Deques: Remove 2 from minDeque since it is out of the window (minDeque = [3, 4, 5])
    • Update maxLength: maxLength = max(3, 5 - 3 + 1) = 3

  8. Final Result:

    • The algorithm completes, and maxLength = 3, which is the length of the longest subarray where the absolute difference between the maximum and minimum elements is within the given limit.

Code

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • The algorithm iterates through the array nums using the end pointer, and for each end, it may move the start pointer.
  • Each element is added and removed from the maxDeque and minDeque at most once, leading to a time complexity of O(n), where n is the number of elements in the array.

So, the overall time complexity of the algorithm is O(n).

Space Complexity

  • The space complexity is O(n) due to the space required by the two deques (maxDeque and minDeque). In the worst case, both deques may store all the elements of the array if the window size covers the entire array.
Previous
Next
Mark as Completed