Longest Subarray With Sum K

Problem Overview

Given an array of integers (negative values allowed) and a target k, return the length of the longest contiguous subarray that sums to exactly k.

Why solve this?

Reuses Subarray Sum Equals K's prefix-sum-plus-hashmap machinery for a different question — not how many subarrays qualify, but the longest one — which changes exactly one detail: what the hash map should store at each prefix sum.

Pattern Recognition

Whenever a prefix-sum hashmap problem shifts from counting subarrays to maximizing a subarray's length, store the earliest index each prefix sum was seen at (not the count, and never overwrite it) — length is maximized by pairing the current index with the oldest possible match.

Prerequisites

• Subarray Sum Equals K — the same prefix-sum/hashmap technique, retargeted from counting to maximizing length.

Hints

1. A subarray from index j+1 to i sums to k exactly when prefixSum[i] - prefixSum[j] = k, same as the counting version — but now the goal is to maximize i - j.
2. To maximize length for a fixed current index i, you want the smallest possible j, meaning the earliest index where that prefix-sum value first appeared.
3. Store only the first index at which each prefix-sum value occurs — if that value reappears later, do not overwrite the stored (earlier) index.

Approach

This distinguishes itself from Subarray Sum Equals K in exactly one place: that problem counts every valid (i, j) pair for a given ending index i, so its hash map stores frequencies. This problem instead wants the single longest valid subarray, so its hash map stores the earliest index at which each prefix-sum value was first seen — critically, if a prefix-sum value is seen again later, the stored index must NOT be overwritten, because keeping the earliest occurrence gives the largest possible i - j gap (the longest length) whenever that prefix sum is matched again. Scan the array while maintaining a running prefix sum. At each index i, check whether prefixSum - k has been seen before; if so, the subarray from just after that earliest index to i sums to k, and its length (i minus that earliest index) is a candidate for the answer. Then, only if the current prefix sum has never been seen before, record the current index as its first occurrence.

Code

class Solution {
    public int longestSubarray(int[] nums, int k) {
        Map<Integer, Integer> firstIndex = new HashMap<>();
        firstIndex.put(0, -1);
        int prefixSum = 0, maxLen = 0;
        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];
            if (firstIndex.containsKey(prefixSum - k)) {
                maxLen = Math.max(maxLen, i - firstIndex.get(prefixSum - k));
            }
            firstIndex.putIfAbsent(prefixSum, i);
        }
        return maxLen;
    }
}

Related Problems

• Reverse an Arrayeasy
• Second Largest Element in an Arrayeasy
• Plus Oneeasy
• Running Sum of 1d Arrayeasy