Longest Subarray with Sum K

JavaView on GFG

Time: O(n)

Space: O(n)

Problem Overview

Find longest subarray with sum exactly k.

See our study guide for structured GFG and LeetCode practice.

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?