Skip to main content

Longest Subarray With Bounded Element Gap

easy
Sliding WindowArrayDequeMonotonic QueueSliding WindowMonotonic Queue
Asked atGoogleAmazonMeta

Problem Description

Given an integer array `values` and a non-negative integer `gapLimit`, find the length of the longest contiguous subarray such that the difference between any two elements within the subarray (i.e., `max - min`) is at most `gapLimit`.

**Example 1:**
```
Input: values = [8, 2, 4, 7, 3, 5], gapLimit = 3
Output: 3
Explanation: The subarray [2, 4, 3] has max=4, min=2, difference=2 ≤ 3. Length = 3.
[4, 7, 3] has max=7, min=3, difference=4 > 3.
[3, 5] has difference 2, length 2.
Best is length 3.
```

**Example 2:**
```
Input: values = [10, 10, 10, 10], gapLimit = 0
Output: 4
Explanation: All elements are equal, so max - min = 0 for the entire array.
```

Constraints

  • 1 <= values.length <= 100000
  • 0 <= gapLimit <= 200000
  • 0 <= values[i] <= 100000

Follow-up

Can you solve this in O(n log n) using a sorted data structure like a balanced BST or ordered multiset instead of deques?

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.