Longest Repeating Validation — Problem Statement & Solution Guide
Problem Description
Given an array of integers representing a sequence of discrete signal amplitudes, determine the length of the longest contiguous subarray where the difference between the maximum and minimum values is exactly 1. This specific variance threshold indicates a binary oscillation pattern within the signal, which is critical for identifying stable modulation states in communication protocols. If no such subarray exists, return 0.
The input is a single array of integers. The output must be an integer representing the maximum length of any contiguous segment satisfying the condition: max(subarray) - min(subarray) == 1. Note that a subarray of length 1 has a difference of 0, so it does not satisfy the condition unless the problem context implies a minimum length of 2, but strictly speaking, the difference must be 1. Therefore, the subarray must contain at least two distinct values that differ by 1, and no other values outside this range.
For example, in the sequence [1, 2, 1, 2, 3], the subarray [1, 2, 1, 2] has a max of 2 and a min of 1, with a difference of 1, and has a length of 4. The element 3 breaks this pattern because it would make the difference 2 if included. Your task is to find the longest such segment efficiently.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Longest Repeating Validation"
WHY DOES IT MATTER?
The sliding‑window with frequency map pattern is a cornerstone for problems that require maintaining a dynamic constraint over a contiguous segment, such as longest subarray with at most K distinct elements or with bounded sum. Mastery of this pattern enables engineers to turn quadratic brute‑force scans into linear‑time solutions, a critical skill for performance‑sensitive code.
OPTIMIZATION CHALLENGE
The key insight is that the condition "max‑min = 1" forces the window to contain at most two distinct values that are consecutive. By tracking frequencies of these values, we can instantly know when the window violates the rule and adjust the left pointer, eliminating the need to recompute min/max for every subarray.
REAL-WORLD CONNECTION
Think of a network packet buffer that must hold only packets of two consecutive priority levels to guarantee fair scheduling. As packets arrive, the buffer expands; when a packet of a third priority appears, the oldest packets are evicted until the buffer again contains only two consecutive priorities. This mirrors the sliding window maintaining the max‑min = 1 invariant.
During an interview, first state the invariant (window contains ≤2 consecutive numbers). Then show how you’ll maintain counts and adjust pointers in O(1) amortized time. A quick sketch of the loop and a few edge‑case examples (all equal, alternating values) often impresses the interviewer.
COMPLEXITY AT A GLANCE
O(N)O(1) (since at most two distinct keys are stored)Core Theory — Why This Approach?
The problem asks for the longest contiguous subarray whose maximum and minimum differ by exactly one. A naive solution would examine every possible subarray, compute its min and max, and check the condition, leading to O(N^2) time – infeasible for N up to 10^5 or more. The optimal paradigm leverages the two‑pointer (sliding window) technique combined with a frequency map. As the right pointer expands, we update counts of the encountered values; the window is kept valid only while the set of distinct numbers contains at most two consecutive integers. When the window contains exactly two distinct values whose difference is one, its length is a candidate for the answer. If a third distinct value appears or the gap exceeds one, we shrink the left pointer, decrementing frequencies, until the window regains validity. This linear scan guarantees O(N) time while using O(K) extra space, where K is the number of distinct values inside the window (bounded by 2 for the optimal case).
Interview Questions on This Problem
Q1How would you modify the sliding‑window solution if the required difference between max and min were a configurable integer K instead of 1?
Maintain a frequency map and track the current minimum and maximum values in the window. While max‑min > K, move the left pointer forward, decrementing counts and updating min/max (using a balanced BST or two deques for O(log N) or O(1) amortized updates). The rest of the logic stays the same, yielding O(N log N) or O(N) depending on the data structure.
Q2Explain why a monotonic queue cannot directly solve this problem, even though it efficiently tracks min and max in a sliding window.
Monotonic queues assume a fixed window size; here the window size is dynamic because we must shrink only when the distinct‑value condition breaks. Moreover, the condition depends on the set of distinct values, not just the extreme values, so a monotonic queue alone cannot detect the presence of a third distinct number.
Q3In a distributed system processing a massive stream of signal amplitudes, how would you compute the longest subarray with max‑min = 1 without storing the entire stream?
Apply the same two‑pointer logic in a streaming fashion: keep a sliding window buffer of at most the current valid segment, update frequencies as new elements arrive, and discard elements from the left when the condition fails. Since only the current window’s counts are needed, memory stays O(1) relative to the stream length.
Examples
Input
nums = [1, 2, 1, 2, 3, 2, 1]
Output
4
Explanation: The subarray [1, 2, 1, 2] (indices 0-3) has min=1, max=2, diff=1, length=4. The subarray [2, 1] (indices 5-6) has min=1, max=2, diff=1, length=2. The element 3 at index 4 breaks the previous window. The longest valid length is 4.
Input
nums = [5, 5, 5, 5]
Output
4
Explanation: All elements are identical. The difference between max and min is 0 for any subarray. Since the condition requires the difference to be exactly 1, no valid subarray exists. Return 0.
Input
nums = [10, 11, 10, 11, 10, 11]
Output
6
Explanation: The entire array consists of values 10 and 11. Min=10, Max=11, Diff=1. The length of the entire array is 6. This is the longest valid subarray.
Input
nums = [1, 3, 2, 2, 3, 2]
Output
5
Explanation: Let's check windows. [1,3] diff=2 (invalid). [3,2] diff=1 (valid, len=2). [2,2] diff=0 (invalid). [2,3] diff=1 (valid, len=2). [3,2] diff=1 (valid, len=2). [2,2,3] min=2, max=3, diff=1 (valid, len=3). [2,3,2] min=2, max=3, diff=1 (valid, len=3). The longest is 3.
Constraints
- 1 <= nums.length <= 10^5
- 0 <= nums[i] <= 10^9
- The answer is guaranteed to fit in a 32-bit integer.
Optimal Approach & Strategy
Use a sliding window with a hashmap to track frequencies of at most two consecutive values, expanding the right pointer and shrinking the left pointer only when the window violates the max‑min = 1 rule; this yields O(N) time.
Brute Force Approach
Enumerate every possible subarray, compute its min and max, and check if max‑min equals 1, updating the best length; this is O(N^2).
Verified Code Solutions
/**
* @param {number[]} nums
* @return {number}
*/
var longestRepeatingValidation = function(nums) {
let n = nums.length;
if (n === 0) return 0;
let left = 0;
let maxLen = 0;
let freq = new Map();
for (let right = 0; right < n; right++) {
freq.set(nums[right], (freq.get(nums[right]) || 0) + 1);
while (freq.size > 2) {
let leftVal = nums[left];
freq.set(leftVal, freq.get(leftVal) - 1);
if (freq.get(leftVal) === 0) {
freq.delete(leftVal);
}
left++;
}
if (freq.size === 2) {
let keys = Array.from(freq.keys());
if (Math.abs(keys[0] - keys[1]) === 1) {
maxLen = Math.max(maxLen, right - left + 1);
}
} else if (freq.size === 1) {
maxLen = Math.max(maxLen, right - left + 1);
}
}
return maxLen;
};class Solution {
public:
int longestRepeatingValidation(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
int left = 0;
int maxLen = 0;
unordered_map<int, int> freq;
for (int right = 0; right < n; ++right) {
freq[nums[right]]++;
while (freq.size() > 2) {
freq[nums[left]]--;
if (freq[nums[left]] == 0) {
freq.erase(nums[left]);
}
left++;
}
if (freq.size() == 2) {
auto it1 = freq.begin();
auto it2 = next(it1);
if (abs(it1->first - it2->first) == 1) {
maxLen = max(maxLen, right - left + 1);
}
} else if (freq.size() == 1) {
maxLen = max(maxLen, right - left + 1);
}
}
return maxLen;
}
};class Solution {
public int longestRepeatingValidation(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int left = 0;
int maxLen = 0;
Map<Integer, Integer> freq = new HashMap<>();
for (int right = 0; right < n; right++) {
freq.put(nums[right], freq.getOrDefault(nums[right], 0) + 1);
while (freq.size() > 2) {
int leftVal = nums[left];
freq.put(leftVal, freq.get(leftVal) - 1);
if (freq.get(leftVal) == 0) {
freq.remove(leftVal);
}
left++;
}
if (freq.size() == 2) {
int[] keys = new int[2];
int idx = 0;
for (int key : freq.keySet()) {
keys[idx++] = key;
}
if (Math.abs(keys[0] - keys[1]) == 1) {
maxLen = Math.max(maxLen, right - left + 1);
}
} else if (freq.size() == 1) {
maxLen = Math.max(maxLen, right - left + 1);
}
}
return maxLen;
}
}class Solution:
def longestRepeatingValidation(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0
left = 0
max_len = 0
freq = {}
for right in range(n):
freq[nums[right]] = freq.get(nums[right], 0) + 1
while len(freq) > 2:
left_val = nums[left]
freq[left_val] -= 1
if freq[left_val] == 0:
del freq[left_val]
left += 1
if len(freq) == 2:
keys = list(freq.keys())
if abs(keys[0] - keys[1]) == 1:
max_len = max(max_len, right - left + 1)
elif len(freq) == 1:
max_len = max(max_len, right - left + 1)
return max_len/**
* @param {number[]} nums
* @return {number}
*/
var longestRepeatingValidation = function(nums) {
let n = nums.length;
if (n === 0) return 0;
let left = 0;
let maxLen = 0;
let freq = new Map();
for (let right = 0; right < n; right++) {
freq.set(nums[right], (freq.get(nums[right]) || 0) + 1);
while (freq.size > 2) {
let leftVal = nums[left];
freq.set(leftVal, freq.get(leftVal) - 1);
if (freq.get(leftVal) === 0) {
freq.delete(leftVal);
}
left++;
}
if (freq.size === 2) {
let keys = Array.from(freq.keys());
if (Math.abs(keys[0] - keys[1]) === 1) {
maxLen = Math.max(maxLen, right - left + 1);
}
} else if (freq.size === 1) {
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.