mediumTwo PointersPattern: Sliding Window / Ordered Map
Contiguous Score Range Solution
Problem Statement
You are given an array of integers `scores`. A valid subarray is defined as a contiguous sequence where the absolute difference between any two elements does not exceed 1. Find the length of the longest valid subarray.
Examples
Example 1:
Input:[1, 2, 3, 2, 1, 2, 3]
Output:3
Explanation: The longest valid run is [1, 2, 3] or [2, 3] or [1, 2] where no two batch quality scores differ by more than 1
Example 2:
Input:[1, 5, 2, 3, 4]
Output:1
Explanation: The longest valid run is [1] or [5] or [2] or [3] or [4] where no two batch quality scores differ by more than 1
Constraints
- 1 <= n <= 10^5
- 1 <= arr[i] <= 10^4
Time: O(N) Space: O(N)
Sliding window + TreeMap / Hash Map. Maintain min and max in current window. If max - min > 1, shrink left. Time O(N), Space O(N).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.