Longest Subarray with Sum K
Prefix Sum + HashMap Explained

👋 Introduction

Imagine you're tracking your monthly expenses. You have a list of daily amounts — some days you spend money, some days you get cashback (negative). At the end, you want to find the longest streak of consecutive days where your net spending was exactly ₹15,000. That's precisely the Longest Subarray with Sum K problem.

This problem shows up at companies like Google, Amazon, and Flipkart. It sounds simple but hides a trap that trips up a huge number of students: they reach for the sliding window technique without thinking, and it breaks entirely when negative numbers are in the array.

In this guide, you'll understand exactly why sliding window fails here, when the prefix sum approach works, and how to implement it cleanly in Python with full confidence.

📋 Problem Statement

Given an array arr[] of integers (which may include negative numbers, zeros, and positives) and an integer k, find the length of the longest subarray whose elements sum to exactly k. Return 0 if no such subarray exists.

📥 Input / Output Format

📐 Constraints

• Array can have negative numbers, zeros, and positive numbers
• Array length: 1 ≤ n ≤ 10⁵
• Element values: -10⁴ ≤ arr[i] ≤ 10⁴
• k can be any integer (negative, zero, or positive)

🐢 Naive Approach — O(n²)

The brute force idea is simple: try every possible subarray, compute its sum, and track the longest one that equals k.

def longest_subarray_brute(arr, k):
    n = len(arr)
    max_len = 0
    for i in range(n):
        curr_sum = 0
        for j in range(i, n):
            curr_sum += arr[j]
            if curr_sum == k:
                max_len = max(max_len, j - i + 1)
    return max_len

Problem: This is O(n²) time. For an array of 10⁵ elements, that's 10¹⁰ operations — way too slow for any real interview or test.

🚨 Sliding Window DOES NOT Work Here

Concrete Failure Example

Consider: arr = [2, -1, 2], k = 3

The correct answer is 3 (entire array: 2 + (-1) + 2 = 3).

With a sliding window: when the sum exceeds k, you shrink from the left. But after removing 2 from the left, your window becomes [-1, 2] with sum = 1. You then expand — missing the correct answer entirely.

⚡ Optimal Approach — Prefix Sum + HashMap

The key insight is to use a running prefix sum and store the first time each prefix sum value was seen in a HashMap.

Core Idea

If the sum from index 0 to j is curr_sum, and you want sum from some index i to j to be exactly k, then:

So at every index, you just check: has the value (curr_sum − k) appeared before as a prefix sum? If yes, you've found a subarray with sum k — and its length is (current_index − index_where_that_prefix_sum_was_seen).

Algorithm Steps

💡 Key Intuition — Why This Works

📊 Prefix Sum Visualization

Let's visualize how the prefix sum and HashMap evolve for arr = [10, 5, 2, 7, 1, 9], k = 15:

Array

Purple cells = the longest subarray [5, 2, 7, 1] with sum 15

Step-by-Step Prefix Sums

Answer: 4 (maximum length tracked at index 4)

🔄 Flowchart

📝 Pseudocode

function longest_subarray_sum_k(arr, k):
    hashmap = {0: -1}
    curr_sum = 0
    max_len = 0

    for i from 0 to len(arr) - 1:
        curr_sum = curr_sum + arr[i]

        if (curr_sum - k) exists in hashmap:
            length = i - hashmap[curr_sum - k]
            max_len = max(max_len, length)

        if curr_sum NOT in hashmap:
            hashmap[curr_sum] = i

    return max_len

🐍 Python Program

# ============================================================
# Longest Subarray with Sum K
# Approach: Prefix Sum + HashMap | O(n) time, O(n) space
# Author: TechNaga | pro.technaga.com
# ============================================================

def longest_subarray_sum_k(arr, k):
    # Store first occurrence of each prefix sum
    # {0: -1} handles the case where subarray starts at index 0
    prefix_map = {0: -1}

    curr_sum = 0     # Running prefix sum
    max_len  = 0     # Track the longest valid subarray

    for i, val in enumerate(arr):
        curr_sum += val   # Add current element to running sum

        # If (curr_sum - k) was seen before,
        # then arr[prev_index+1 .. i] has sum = k
        if (curr_sum - k) in prefix_map:
            length = i - prefix_map[curr_sum - k]
            max_len = max(max_len, length)

        # Only store first occurrence (for maximum length)
        if curr_sum not in prefix_map:
            prefix_map[curr_sum] = i

    return max_len


# ——— Input Handling ———
if __name__ == "__main__":
    arr = list(map(int, input("Enter array elements: ").split()))
    k   = int(input("Enter target sum k: "))
    result = longest_subarray_sum_k(arr, k)
    print(f"Longest subarray with sum {k} has length: {result}")

🔬 Dry Run

Input: arr = [10, 5, 2, 7, 1, 9], k = 15

Initial State: prefix_map = {0: -1}, curr_sum = 0, max_len = 0

Final Answer: 4 — The subarray [5, 2, 7, 1] (indices 1 to 4) sums to 15.

🔍 Line-by-Line Explanation

📈 Time & Space Complexity

🧪 Test Cases

⚠️ Edge Cases

🎯 Common Interview Questions

1. Why doesn't sliding window work for this problem when negatives are present? — Because shrinking the window doesn't guarantee a smaller sum when negatives exist. The monotonic assumption breaks.
2. Why do you initialize the HashMap with {0: -1}? — To handle subarrays that start from index 0. Without it, we'd miss the case where the prefix sum itself equals k.
3. Why store only the first occurrence of each prefix sum? — We want the maximum length. Using a later occurrence of the same prefix sum would give a shorter subarray.
4. What is the time complexity, and why? — O(n). We make one pass through the array, and each HashMap operation is O(1) average case.
5. What happens if the same prefix sum appears multiple times? — We skip updating the HashMap after the first occurrence. The first index gives the longest possible subarray ending at any future index.
6. How would you modify this to return the subarray itself instead of just the length? — Track start and end indices: when you find a match, compute start = prefix_map[curr_sum - k] + 1 and end = i. Return arr[start:end+1].

🌍 Real-World Applications

❌ Mistakes Beginners Make

• Using sliding window on arrays with negative numbers. It will produce wrong answers without any error — the most dangerous type of bug.
• Not initializing the HashMap with {0: -1}. This causes the algorithm to miss subarrays that start from index 0.
• Overwriting the HashMap when a prefix sum repeats. If you store the latest index instead of the first, you get shorter subarrays — wrong answer for "longest."
• Checking if curr_sum (not curr_sum − k) is in the map. The key check is always curr_sum - k, not curr_sum.
• Computing length as i − prefix_map[curr_sum − k] − 1. The correct formula is i − prefix_map[curr_sum − k] (no −1). The prefix sum at index j was the sum of elements 0..j, so the next element starts at j+1.

⚖️ Approach Comparison

✅ Conclusion

❓ Frequently Asked Questions