Longest Subarray with Sum K

Longest contiguous subarray summing to k. [1,2,3,1,1,1,1,4,2,3], k=3 → length 3 ([1,1,1]).

Brute force: check every subarray’s sum directly — O(n³), reducible to O(n²) by maintaining a running sum per starting index instead of recomputing it.

Better — prefix sum + hashmap: if the prefix sum at index j minus the prefix sum at index i equals k, the subarray between them sums to k. Store each prefix sum’s earliest index in a map; for each new prefix sum, check whether prefix_sum - k has been seen before.

longest_len = 0;
prefix_sum = 0;
hashmap = {}

for i in range(n):
    prefix_sum += arr[i]

    if prefix_sum == K:
        longest_len = i + 1

    if (prefix_sum - K) in hashmap:
        subarray_len = i - hashmap[prefix_sum - K]
        longest_len = max(longest_len, subarray_len)

    if prefix_sum not in hashmap:
        hashmap[prefix_sum] = i

return longest_len

This works for arrays that may include negative numbers. Time: O(n).

Optimal for positive-only arrays — two pointers / sliding window: expand the window with j, adding to a running sum; whenever sum exceeds K, shrink from the left with i until it’s back within bounds.

public class Solution {
    public static int lenOfLongSubarr(int[] A, int N, int K) {
        int i = 0, j = 0;
        int sum = 0;
        int maxLen = 0;

        while (j < N) {
            sum += A[j];

            while (sum > K && i <= j) {
                sum -= A[i];
                i++;
            }

            if (sum == K) {
                maxLen = Math.max(maxLen, j - i + 1);
            }

            j++;
        }

        return maxLen;
    }
}

Time: O(N) — each element is processed at most twice. Space: O(1).