Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Longest Continuous Subarray

Problem Statement

Given an array of integers nums and an integer limit, find the length of the longest contiguous non-empty subarray withinnums, where the absolute difference between any two elements in this subarray does not exceed a specified limit.

Examples

  1. Example 1:

    • Input: Array = [10, 1, 2, 4, 7], Limit = 5
    • Expected Output: 3
    • Justification: The longest subarray where the absolute difference between any two numbers is at most 5 is [1, 2, 4].

  2. Example 2:

    • Input: Array = [4, 8, 5, 1, 7, 9], Limit = 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