Orbital Echo Archive
Indices of the earliest longest subarray with at most k equal-value pairs
A spacecraft stores telemetry packets in arrival order. Each packet has a signed integer channel identifier, given in channels.
Mission control wants to download one contiguous block of packets. Within that block, every pair of packets using the same channel requires an echo check. A pair consists of two different packet positions, and each unordered pair is counted once, even if the packets are not adjacent. Thus, a channel appearing four times contributes six echo checks.
The downloaded block may require at most pair_limit echo checks.
Return the inclusive, zero-based indices [start, end] of the longest permitted nonempty block. If several blocks have the same maximum length, return the one with the smallest starting index. If channels is empty, return [-1, -1].
Examples
Example 1
Input: channels = [4,4,9,4], pair_limit = 1 Output: [0,2]
With a budget of one echo check, all four packets cannot be downloaded together because channel 4 appears three times. Each of the two length-three blocks needs only one check, so the earlier block is selected.
Example 2
Input: channels = [8,-2,8,5,6,-2], pair_limit = 0 Output: [1,4]
A zero-check budget forbids repeated channels within the downloaded block. The longest permitted block consists of the final four packets, whose channel identifiers are all different.
Example 3
Input: channels = [7,7,7], pair_limit = 3 Output: [0,2]
Three packets on the same channel create three pairs. This fits the budget, so the entire archive can be downloaded.
Constraints
- 0 <= channels.length <= 10,000
- -1,000,000,000 <= channels[i] <= 1,000,000,000
- 0 <= pair_limit <= 50,000,000
- channels contains integers, and pair_limit is an integer.
The intended solution runs in O(n) time and uses O(d) extra space, where d is the number of distinct channel identifiers in the active window.
Hints
Show hint 1Hint 1
If a channel currently appears c times in a block, how many new pairs are created by adding one more packet on that channel?
Show hint 2Hint 2
Keep a frequency map and a running pair count. When the count exceeds the budget, remove packets from the left until the block is permitted again.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you process packets arriving as a stream while retaining only the active block and the best indices found so far?
- How would the pair-count updates change if each channel had its own nonnegative cost per equal-channel pair?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem