Earliest Longest Bounded-Adjacent Subarray
Reported by candidates from ZipRecruiter's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
ZipRecruiter reported this one in October 2023, and the detail that matters is the rule: every adjacent absolute difference has to be at most difference. That's it. It's a longest-run problem dressed up with a tie-break. The hint says dynamic-programming, but it's really a single pass with a running start index. You return inclusive [start,end] indices of the longest qualifying subarray, earliest start on ties. With up to 100000 elements, it has to be linear. If you blank mid-assessment, StealthCoder runs invisibly on your desktop as a safety net and gives you the pass when you need it.
The problem
A contiguous subarray qualifies when every adjacent absolute difference is at most difference. Return inclusive [start,end] indices of a maximum-length qualifying subarray, breaking ties by earliest start. Function longestBoundedAdjacentSubarray(numbers: int[], difference: int) → int[] Examples Example 1 numbers = [-1,4,6,2,8,4,7] difference = 5 return = [0,3] The earliest maximum qualifying run is returned. Example 2 numbers = [1,10,2,11] difference = 3 return = [0,0] The earliest maximum qualifying run is returned. Constraints 1 <= numbers.length <= 100000 0 <= difference <= 2000000000
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick: a subarray is valid only if each neighboring pair is within difference. So validity breaks only at one place, between i-1 and i. Walk the array once, keep a start index. If abs(numbers[i] - numbers[i-1]) > difference, reset start to i. Otherwise the run continues. After each step, compare i - start + 1 to the best length, and update only when strictly greater. That strict comparison gives you the earliest start on ties for free. The common pitfall is using >= and returning the latest run. Another is overflow: differences can reach about 4 billion, so use 64-bit ints in Java or C++. Example 2 returns [0,0] because every pair breaks. A single element is always valid. If you freeze during the live OA, StealthCoder is the hedge, but this is a ten-line loop.
If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.
You can drill Earliest Longest Bounded-Adjacent Subarray cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass ZipRecruiter's OA.
ZipRecruiter reuses patterns across OAs. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Earliest Longest Bounded-Adjacent Subarray FAQ
What's the trick to this problem?+
Validity only depends on adjacent pairs, so you track one start index. When abs(numbers[i] - numbers[i-1]) exceeds difference, reset start to i. Otherwise extend the run. Record the best length and its indices as you go. One pass, O(n) time, O(1) space.
How do I get the earliest start on ties?+
Only update the best answer when the current run length is strictly greater than the best length. Since you scan left to right, the first run to reach a given length is the earliest one. Using >= would overwrite it with a later run and fail the tie-break.
Do I really need dynamic programming here?+
Not in the table sense. You can think of it as dp[i] = length of the valid run ending at i, but that only depends on dp[i-1], so it collapses to a running start index. Interviewers accept either framing. The loop version is shorter and harder to break.
What edge cases should I test?+
Length 1 array returns [0,0]. A difference of 0 means only equal neighbors qualify. When every pair breaks, return [0,0] as in example 2. Large values can make the subtraction overflow 32-bit ints, so use long. Also check a tie between two runs and confirm the first wins.
How do I prepare for this in 48 hours?+
Practice longest-run problems with a reset condition, like longest subarray with a constraint on neighbors. Write the loop from memory twice, then test your tie-break on a hand-made example. Focus on 64-bit arithmetic and strict comparison. You don't need heavy DP theory for this one.