Implement longest subarray summing to k
Company: Google
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an integer array nums (length ≤ 200,000; values may be negative) and integer k, return the maximum length and the [l, r] indices of a contiguous subarray whose sum is exactly k. If multiple answers tie for length, choose the smallest l; if still tied, choose the smallest r.
- First outline a correct O(n^2) brute‑force solution.
- Then design an O(n) algorithm using prefix sums and a hash map. Prove correctness and explain how you ensure earliest indices under ties.
- State time/space complexity and handle edge cases: k=0, all negatives, all zeros, duplicates, and empty or no‑solution cases.
Quick Answer: This question evaluates proficiency in array algorithms, prefix-sum reasoning, hash-based lookup patterns, and careful handling of edge cases and deterministic tie-breaking.
Given an integer array nums and an integer k, return [max_len, l, r], where nums[l:r+1] is a non-empty contiguous subarray whose sum is exactly k and max_len is its length.
Tie-breaking:
- If multiple valid subarrays have the same maximum length, choose the one with the smallest l.
- If l is also tied, choose the one with the smallest r.
If no such subarray exists, return [0, -1, -1].
Interview discussion expectations:
1) First outline a correct O(n^2) brute-force approach. A clean way is to build prefix sums so each subarray sum can be checked in O(1), then test all pairs (l, r) and keep the best answer under the tie rules.
2) Then implement an O(n) solution using prefix sums and a hash map.
Why the O(n) idea works: a subarray l..r sums to k iff prefix[r] - prefix[l-1] = k, so for each r you need a previous prefix sum equal to prefix[r] - k. Storing the first index where each prefix sum appears gives the longest valid subarray ending at r. Scanning left to right and updating the best answer with the tie rules ensures the final answer has maximum length and the earliest valid indices among ties.
Your implementation must handle negative numbers, zeros, duplicates, empty input, and no-solution cases.
Constraints
- 0 <= len(nums) <= 200000
- -10^9 <= nums[i], k <= 10^9
- nums may contain negative numbers, zeros, and duplicates
- In languages with fixed-width integers, use 64-bit arithmetic for prefix sums
Examples
Input: ([1, -1, 5, -2, 3], 3)
Expected Output: [4, 0, 3]
Explanation: The subarray [1, -1, 5, -2] sums to 3 and has length 4, which is the longest.
Input: ([-2, -1, 2, 1], 1)
Expected Output: [2, 1, 2]
Explanation: The longest valid subarray is [-1, 2], from index 1 to 2.
Hints
- A correct brute-force approach can be made O(n^2) by using prefix sums, so any subarray sum from l to r is prefix[r + 1] - prefix[l].
- For the O(n) solution, store the first time each prefix sum appears. For index r, if prefix[r] - k was seen before at index j, then subarray (j + 1) to r sums to k.