Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Longest Subarray with Sum K

Use prefix sums and earliest indexes to handle positive and negative values in linear time.

MediumArraysPattern: prefix sum, hashing

Problem statement

Given an integer array and a target k, return the maximum length of a contiguous subarray whose sum is k.

For [1, -1, 5, -2, 3] and k = 3, the answer is 4 because [1, -1, 5, -2] sums to 3.

Constraints & requirements

INPUT
Integers may include negatives
RETURN
Maximum matching subarray length
TARGET
Expected O(n) time

Examples 3 test cases

  1. Example 1 Includes negatives

    Input
    [1, -1, 5, -2, 3], k = 3
    Output
    4

    Checks why a normal sliding window is unsafe.

  2. Example 2 Whole array

    Input
    [2, -2, 2], k = 2
    Output
    3

    Checks the prefix sum from index zero.

  3. Example 3 No match

    Input
    [1, 2], k = 9
    Output
    0

    Checks the missing-range result.

Hints Optional

Hints become more specific one step at a time.
01Describe a range with two prefixes

A subarray ending now has sum k when an earlier prefix equals currentPrefix - k.

02Keep historical lookup fast

Map each prefix sum to an index so you do not scan all earlier positions again.

03Keep the earliest index

The earliest occurrence of a prefix creates the longest possible range ending at the current index.

How to think before coding

For a fixed ending index, write rangeSum=currentPrefix−oldPrefix. Rearranging gives oldPrefix=currentPrefix−k. Since the result is a length, store an index, not a count. To maximize that length, preserve the earliest index for a total. Seed 0 at −1 so a range beginning at zero uses the same formula, then look up before recording the current boundary.

Brute force and the improvement

Choose each start and extend every end with a running sum: O(n²) time, O(1) extra space, valid with negatives too. Recomputing every range from scratch costs O(n³). Earliest-index prefix lookup reduces repeated searches to expected O(n) time with O(n) map storage. Unlike the counting problem, we store an earliest index, not a frequency, because we want maximum length.

Intuition

Let prefix be the sum from the beginning through the current index. A previous prefix of prefix - k means the values between that earlier position and the current position sum to k.

Store the earliest index for each prefix sum because the earliest position produces the longest subarray.

Java solution

Java
import java.util.HashMap;
import java.util.Map;

public static int longestSubarrayWithSum(int[] values, long k) {
    Map<Long, Integer> firstIndex = new HashMap<>();
    firstIndex.put(0L, -1); // Empty prefix supports ranges beginning at index zero.

    long prefix = 0; // Long avoids overflow when many int values are added.
    int longest = 0;

    for (int index = 0; index < values.length; index++) {
        prefix += values[index]; // Sum from index zero through the current index.

        // Remove an earlier prefix so the remaining contiguous range sums to k.
        Integer start = firstIndex.get(prefix - k);
        if (start != null) {
            // The old prefix ends at start; our range begins at start + 1.
            longest = Math.max(longest, index - start);
        }

        firstIndex.putIfAbsent(prefix, index); // Keep the earliest occurrence for maximum length.
    }
    return longest; // Zero remains when no matching nonempty range exists.
}

When a sliding window works

If every value is nonnegative, a sliding window can solve the problem with O(1) extra space. With negative values, the window sum is not monotonic, so prefix sums are safer.

Dry run

Numbered illustrated dry run for Longest Subarray with Sum K; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

For [1, -1, 5, -2, 3], k = 3, initialize the map with 0 → -1.

Index Prefix Need prefix − 3 Earliest matching index Candidate length Best
0 1 -2 absent none 0
1 0 -3 absent none 0
2 5 2 absent none 0
3 3 0 -1 3 − (-1) = 4 4
4 6 3 3 4 − 3 = 1 4

At index 1, prefix zero appears again. Keep its original index -1, not 1. That preserves the longest range starting at index zero. Look up the old boundary before recording the current prefix.

Complexity

Expected time is O(n) and extra space is O(n).

Common mistakes

  • Replacing the earliest index for a prefix sum
  • Using a sliding window when negative values are allowed
  • Using int for prefix sums when the total may overflow

Practice next

Next lessonPrefix Sum pattern

Review range identities and common edge cases.

Back to Arrays →