Longest Continuous Subarray Within Limit

Interview Problem Interview Medium Monotonic Queue Variable-size Window Array

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.longestSubarray(nums, limit). Return the longest contiguous subarray whose maximum value minus minimum value is at most limit.

Starter code

class Solution:
    def longestSubarray(self, nums, limit):
        pass

Test cases

alternating

{
  "args": [
    [
      8,
      2,
      4,
      7
    ],
    4
  ]
}

Expected: 2

Wizard outline

Step 1: Initialize Solution.longestSubarray
Replace the empty starter with the first real state owned by Solution.longestSubarray. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Duplicates case
Complete the readable core algorithm for one representative Interview case. Maintain decreasing maximum candidates and increasing minimum candidates while a variable window slides.
Step 4: Harden the Alternating boundary
Repair the reviewed boundary and pass the complete submission contract. Deque fronts are exactly the current window maximum and minimum because dominated and expired indices are removed. Shrinking until their difference fits makes the retained window feasible and longest for each right endpoint.

Footguns and prerequisites

Store indices so expired extrema can be removed when left advances.
arrays strings two pointers sliding window

Reviewed references

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

Practice prerequisites

Shrink Until the Window Is Valid(opens in a new tab)
Shrink Until the Window Is Valid isolates after shrinking, the current half-open window is valid and no earlier left boundary works for the same right endpoint. That focused state discipline is required when implementing longest continuous subarray limit as a complete Interview Problem.

Recommended approach and implementation

Use one deque of indices with decreasing values for the maximum and another with increasing values for the minimum; shrink left while their front difference exceeds limit.

Why it works: Deque fronts are exactly the current window maximum and minimum because dominated and expired indices are removed. Shrinking until their difference fits makes the retained window feasible and longest for each right endpoint.

class Solution:
    def longestSubarray(self, nums, limit):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        from collections import deque
        maximums = deque()
        minimums = deque()
        left = best = 0
        for right, value in enumerate(nums):
            while maximums and nums[maximums[-1]] < value:
                maximums.pop()
            while minimums and nums[minimums[-1]] > value:
                minimums.pop()
            maximums.append(right)
            minimums.append(right)
            while nums[maximums[0]] - nums[minimums[0]] > limit:
                if maximums[0] == left:
                    maximums.popleft()
                if minimums[0] == left:
                    minimums.popleft()
                left += 1
            best = max(best, right - left + 1)
        return best