Longest Subarray Sum K HashMap | Java Fresher Interview

Direct Answer

Use a prefix sum + HashMap. Track a running sum and store, for each prefix sum, the earliest index it occurred. At index i with running sum S, if S - k was seen at index j, then the subarray (j+1..i) sums to k; the longest is i - j. One pass, O(n) time and O(n) space - far better than the O(n^2) double loop.

Deep Dive & Architecture

Let prefix be the sum from index 0 through the current index. A subarray ending here has sum k when an earlier prefix equals prefix - k, because subtracting the earlier total leaves exactly the range in between.

Store the earliest index for every prefix sum. Earlier is better because it produces the longest range. Seed the map with 0 -> -1, which lets a valid subarray begin at index 0.

Worked example: [1, -1, 5, -2, 3], k = 3

The prefix sums are 1, 0, 5, 3, and 6. When zero appears again at index 1, keep its earlier seed index -1. At index 3, prefix - k is 3 - 3 = 0; the earliest zero gives the range from index 0 through 3, [1, -1, 5, -2], with length 4. At index 4, prefix 6 finds prefix 3 at index 3 and gives only length 1, so the best remains 4. Never overwrite an existing prefix index.

Unlike a standard sliding window, this method works with negative values because prefix-sum subtraction stays valid even when sums rise and fall. The scan is O(n) average time and uses O(n) extra space. Use long for prefixes when integer totals may overflow.

Code Example

int longestSubarray(int[] nums, int k) {
    Map<Integer,Integer> first = new HashMap<>();
    first.put(0, -1);                 // empty prefix before index 0
    int sum = 0, best = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (first.containsKey(sum - k))           // earlier prefix gives sum k
            best = Math.max(best, i - first.get(sum - k));
        first.putIfAbsent(sum, i);                // keep EARLIEST index only
    }
    return best;
}

// nums = {1, -1, 5, -2, 3}, k = 3
// prefix: 1,0,5,3,6 ; sum-k seen -> best length 4 (subarray 1,-1,5,-2)

Common Mistakes & Pitfalls

• O(n^2) all-subarrays: trying every start/end; the prefix-sum map makes it O(n).
• Storing latest index: use putIfAbsent to keep the earliest - storing the latest shortens the answer.
• Forgetting the {0:-1} seed: without it, subarrays starting at index 0 are missed.
• Confusing with count: 'count of subarrays' stores frequencies, not earliest index.