Longest Subarray with Limited Difference
Given an array of N integers, find the length of the longest contiguous subarray such that the absolute difference between any two elements in the subarray is less than or equal to a given integer K.
Input
The first line contains two integers N and K, separated by a space. The second line contains N integers, the elements of the array.
Output
Print a single integer representing the length of the longest subarray satisfying the condition.
Constraints
1 <= N <= 200000 0 <= K <= 10^9 Elements of the array are integers between -10^9 and 10^9.
Example 1
5 2 1 3 2 4 5
3
The subarray [1, 3, 2] has min 1, max 3, diff 2 <= 2. Length 3. The subarray [3, 2, 4] has min 2, max 4, diff 2 <= 2. Length 3. The subarray [2, 4, 5] has min 2, max 5, diff 3 > 2. The longest valid subarray is length 3.
Example 2
7 1 1 1 1 1 1 1 1
7
All elements are the same, so any subarray is valid. The longest subarray is the entire array, length 7.
Hints
Similar problems
- Longest Subarray with Alternating ParityMedium
- Longest Subarray with Sum at Most KMedium
- Count Subarrays with Distinct ElementsMedium
- Longest Subarray with At Most K Distinct ElementsMedium
- Longest Subarray with Constant DifferenceMedium
- Longest Sorted SubsegmentMedium
More topics: Two Pointers problems, Sliding Window problems, Greedy 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
7 1 1 1 1 1 1 1 1