Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Longest Continuous Subarray (medium)

Problem Statement

Find the length of the longest contiguous subarray within an array of integers, where the absolute difference between any two elements in this subarray does not exceed a specified limit. The challenge lies in ensuring the subarray is continuous and the range (difference between the maximum and minimum element in the subarray) fits within the given threshold.

Examples

  1. Example 1:
    • Input: Array = [10, 1, 2, 4, 7], Limit = 5
    • Expected Output: 3

.....

.....

.....

Like the course? Get enrolled and start learning!
Sachin Dev S

Sachin Dev S

· 2 years ago

from collections import defaultdict
from bisect import bisect_left, bisect_right, insort_left

class Solution:
    @staticmethod
    def longestSubarray(nums, limit):
        sorted_window = []
        left = maxLength = 0

        for right, value in enumerate(nums):
            insort_left(sorted_window, value)

            # Shrink the window if the condition is violated
            while sorted_window[-1] - sorted_window[0] > limit:
                sorted_window.pop(bisect_left(sorted_window, nums[left]))
                left += 1

            # Update the maximum length found
            maxLength = max(maxLength, right - left + 1)

        return maxLength
Viktor Pokazanyev

Viktor Pokazanyev

· 7 months ago

from collections import deque

class Solution:
    def longestSubarray(self, nums, limit):
        maxLength = 0
        start = 0
        min_dq, max_dq = deque(), deque()
        for end in range(len(nums)):
            # Update max.
            while max_dq and max_dq[0] < start:
                max_dq.popleft()
            while max_dq and nums[max_dq[-1]] <= nums[end]:
                max_dq.pop()
            max_dq.append(end)
            # Update min.
            while min_dq and min_dq[0] < start:
                min_dq.popleft()
            while min_dq and nums[min_dq[-1]] >= nums[end]:
                min_dq.pop()
            min_dq.append(end)
            # Check limit and update max length.
            w_min, w_max = nums[min_dq[0]], nums[max_dq[0]]
            i