Longest Subarray With Sum K
Given an array $A_1, A_2, \ldots, A_n$ of integers (which may be negative) and a target value $K$, find the length of the longest contiguous subarray whose elements sum to exactly $K$.
Constraints: - $1 \leq n \leq 10^5$ - $-10^9 \leq A_i \leq 10^9$ - $-10^{18} \leq K \leq 10^{18}$
Example 1: Input: $A = [1, -1, 5, -2, 3]$, $K = 3$ Output: $4$ Explanation: The subarray $[1, -1, 5, -2]$ sums to $3$ and has length $4$.
Example 2: Input: $A = [-2, -1, 2, 1]$, $K = 1$ Output: $2$ Explanation: The subarray $[-1, 2]$ sums to $1$ and has length $2$.
Design an algorithm that runs in $O(n)$ time and $O(n)$ space. Discuss overflow safeguards when element values can be large.
Hints
- Think about how prefix sums convert a subarray sum condition into a two-index lookup: $P_t - P_s = K$.
- You want the earliest index $s$ where $P_s = P_t - K$. What data structure lets you store and query by prefix sum value in $O(1)$?
- Use a hash map from prefix-sum value to its first occurrence index. Only insert a prefix sum if it has not been seen before -- this ensures you always get the longest subarray.
Worked Solution
How to Think About It: The classic trick for subarray-sum problems is prefix sums. If $P_t = A_1 + A_2 + \cdots + A_t$ (with $P_0 = 0$), then the subarray $A_{s+1} + \cdots + A_t = P_t - P_s$. So finding a subarray with sum $K$ reduces to finding indices $s < t$ where $P_t - P_s = K$, i.e., $P_s = P_t - K$. To maximize the length $t - s$, we want the earliest index $s$ with that prefix sum value. This is the same two-sum pattern but adapted for subarrays.
Algorithm: Walk through the array maintaining a hash map from prefix-sum values to the earliest index where that value occurs. For each position $t$, compute $P_t$ and look up $P_t - K$ in the map. If found at index $s$, then $t - s$ is a candidate answer. If $P_t$ is not already in the map, store it with index $t$. We only store the first occurrence of each prefix sum because we want the longest subarray.
Code: ```python def longest_subarray_sum_k(A, K): prefix_map = {0: -1} # prefix sum -> earliest index prefix = 0 best = 0 for i, val in enumerate(A): prefix += val target = prefix - K if target in prefix_map: best = max(best, i - prefix_map[target]) if prefix not in prefix_map: prefix_map[prefix] = i return best ```
Correctness argument: Every contiguous subarray $A_{s+1}, \ldots, A_t$ with sum $K$ satisfies $P_s = P_t - K$. Our map records the earliest index for each prefix sum, so when we process index $t$ and find $P_t - K$ in the map at index $s$, the length $t - s$ is the longest subarray ending at $t$ with sum $K$. Taking the maximum over all $t$ gives the global answer.
Overflow safeguards: - Prefix sums of $10^5$ elements each up to $10^9$ can reach $10^{14}$, which fits in a 64-bit integer but not a 32-bit one. Use long long in C++ or native Python integers (arbitrary precision). - The target $K$ can be $10^{18}$, so the subtraction $P_t - K$ must also use 64-bit arithmetic. - In languages like Java, use long instead of int.
Complexity: $O(n)$ time and $O(n)$ space.
Answer: Use a prefix sum hash map storing the earliest index for each prefix sum value. For each index $t$, look up $P_t - K$. This gives $O(n)$ time and $O(n)$ space. (Note: the problem statement mentions $O(n \log n)$ with a balanced BST, which also works but is unnecessary -- the hash map approach achieves $O(n)$.)
Intuition
This problem is a direct application of the prefix sum technique, which converts subarray queries into point queries. The key insight is that any contiguous subarray sum $A_{s+1} + \cdots + A_t$ equals $P_t - P_s$, so finding subarrays with sum $K$ reduces to finding pairs of prefix sums that differ by exactly $K$. This is essentially a variant of the two-sum problem on the prefix sum array.
The subtlety is that we want the longest such subarray, not just any. That is why we store only the first occurrence of each prefix sum in our map. If the same prefix sum appears at indices 3, 7, and 12, we only care about index 3 because pairing with it gives the longest subarray. This "earliest occurrence" trick appears constantly in subarray problems -- for example, finding the longest subarray with equal numbers of 0s and 1s is the same pattern with $K = 0$ after replacing 0s with $-1$s.