Contiguous Score Range — Problem Statement & Solution Guide
Problem Description
Given an array of integers scores, find the length of the longest valid subarray where the absolute difference between any two elements does not exceed 1.
Examples
Input
[1, 1, 1, 1, 1]
Output
5
Explanation: Step-by-step: Given the input [1, 1, 1, 1, 1], we initialize two pointers, left and right, to the start of the array. We then enter a loop where we expand the window by moving the right pointer to the right and check if the absolute difference between the elements at the left and right pointers is greater than 1. If it is, we move the left pointer to the right until the condition is met. We then update the maximum length of the valid subarray. In this case, the maximum length is 5 because the subarray [1, 1, 1, 1, 1] is valid since the absolute difference between any two elements does not exceed 1.
Input
[1]
Output
1
Explanation: Step-by-step: Given the input [1], we initialize two pointers, left and right, to the start of the array. We then enter a loop where we expand the window by moving the right pointer to the right and check if the absolute difference between the elements at the left and right pointers is greater than 1. Since the array only contains one element, the absolute difference is 0, which is less than 1. We then update the maximum length of the valid subarray. In this case, the maximum length is 1 because the subarray [1] is valid since the absolute difference between any two elements does not exceed 1.
Constraints
- 1 <= n <= 10^5
- 1 <= arr[i] <= 10^4
Optimal Approach & Strategy
Sliding window + TreeMap / Hash Map. Maintain min and max in current window. If max - min > 1, shrink left. Time O(N), Space O(N).
Brute Force Approach
Check all subarrays. Time O(N^2).
Verified Code Solutions
function longestValidSubarray(scores) { let maxLen = 0, left = 0; for (let right = 0; right < scores.length; right++) { while (scores[right] - scores[left] > 1 || scores[right] - scores[left] < -1) { left++; } if (scores[right] - scores[left] > 1 || scores[right] - scores[left] < -1) { maxLen = 0; } else { maxLen = Math.max(maxLen, right - left + 1); } } return maxLen; }class Solution {
public int contiguousScoreRange(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int max_length = 1;
int left = 0;
for (int right = 1; right < nums.length; right++) {
if (Math.abs(nums[right] - nums[right - 1]) > 1) {
left = right;
}
max_length = Math.max(max_length, right - left + 1);
}
return max_length;
}
}def contiguous_score_range(nums):
if not nums:
return 0
max_length = 1
left = 0
for right in range(1, len(nums)):
if abs(nums[right] - nums[right - 1]) > 1:
left = right
max_length = max(max_length, right - left + 1)
return max_lengthfunction longestValidSubarray(scores) { let maxLen = 0, left = 0; for (let right = 0; right < scores.length; right++) { while (scores[right] - scores[left] > 1 || scores[right] - scores[left] < -1) { left++; } if (scores[right] - scores[left] > 1 || scores[right] - scores[left] < -1) { maxLen = 0; } else { maxLen = Math.max(maxLen, right - left + 1); } } return maxLen; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.