Longest Subarray with Bounded Difference
Given an array of N integers and an integer K, find the length of the longest subarray such that the difference between the maximum element and the minimum element within that subarray is at most K. If multiple such subarrays have the maximum length, return the length of the first one encountered.
Input
The first line contains two integers N and K. The second line contains N integers representing the array.
Output
Print a single integer, the length of the longest subarray satisfying the condition.
Constraints
1 <= N <= 200000 0 <= K <= 10^9 -10^9 <= array elements <= 10^9
Example 1
5 2 1 3 2 4 5
3
The subarray [1, 3, 2] has max 3, min 1, difference 2 <= K. Its length is 3. The subarray [2, 4] has max 4, min 2, difference 2 <= K. Its length is 2. The subarray [4, 5] has max 5, min 4, difference 1 <= K. Its length is 2. The longest is 3.
Example 2
6 3 8 2 4 7 1 6
2
The subarray [2, 4, 7] has max 7, min 2, difference 5 > K. The subarray [2, 4] has max 4, min 2, difference 2 <= K (length 2). The subarray [4, 7] has max 7, min 4, difference 3 <= K (length 2). The subarray [7, 1, 6] has max 7, min 1, difference 6 > K. The subarray [1, 6] has max 6, min 1, differen
Hints
Similar problems
- Longest Subarray with Alternating ParityMedium
- Longest Subarray with At Most K Distinct ElementsMedium
- Optimal Training ScheduleMedium
- Longest Subarray with Limited DifferenceMedium
- Longest Subarray with Increasing SumMedium
- Longest Subarray with Sum at Most KMedium
More topics: Two Pointers problems, Sliding Window problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 2 1 3 2 4 5
6 3 8 2 4 7 1 6