Longest Subarray with Sum K

Time: O(n)

Space: O(n)

Intuition

Find longest subarray with sum exactly k. Use prefix sum hash map: if prefix[i]-k seen before, subarray from that index+1 to i has sum k.

Algorithm

1Map: prefix_sum -> first index. Initialize {0: -1}.
2For each i: if (prefix[i]-k) in map: candidate length = i - map[prefix[i]-k]. Update max.
3If prefix[i] not in map: map[prefix[i]] = i.

Common Pitfalls

•Store first occurrence of each prefix sum (don't overwrite). Works for both positive and negative integers.

Longest Subarray with Sum K.java

Java

// Approach: Prefix sum with HashMap. Store first occurrence of each prefix sum; check for sum = prefixSum - k.
// Time: O(n) Space: O(n)
class Solution {
    public int longestSubarray(int[] arr, int k) {
        Map<Integer, Integer> list = new HashMap<>();
        list.put(0, -1);
        int max_length = 0;
        int prefix_sum = 0;

        for (int i = 0; i < arr.length; i++) {
            prefix_sum += arr[i];

            if (list.containsKey(prefix_sum - k))
                max_length = Math.max(max_length, i - list.get(prefix_sum - k));

            list.putIfAbsent(prefix_sum, i);
        }

        return max_length;
    }
}

Was this solution helpful?