☕ DSA Java Articles

Topics › Arrays › Easy

Longest subarray with sum K

Medium TUF ID 564 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an integer array nums, whose elements may be negative, zero or positive, and an integer k. Return the length of the longest contiguous subarray whose elements sum to exactly k. If there is none, return 0.

This is the general form of the problem; the version restricted to non-negative numbers has an extra O(1)-space solution that does not carry over here, and understanding why is the main lesson of this article.

Constraints: 0 ≤ n ≤ 10^5, -10^9 ≤ nums[i] ≤ 10^9, |k| ≤ 10^18. Sums can leave the int range, so accumulate in long.

Example 1

nums = [1, -1, 5, -2, 3], k = 3
answer = 4          // [1, -1, 5, -2] sums to 3; [3] and [5, -2] also do, but are shorter

Example 2

nums = [-2, -1, 2, 1], k = 1
answer = 2          // [-1, 2]; [1] alone has length 1

Example 3

nums = [3, -2, 1], k = 2
answer = 3          // the whole array; a sliding window would miss this (see below)

Approach 1: Brute force

Intuition. Enumerate every subarray by its start i and end j, add up the elements between them, and compare the sum with k. This is the literal reading of the statement and is only useful as a correctness reference for the other approaches.

Algorithm.

  1. For every start i and every end j ≥ i:
  2. Compute sum = nums[i] + ... + nums[j] with a third loop.
  3. If sum == k, record j - i + 1.
  4. Return the largest recorded length, or 0.
static int bruteForce(int[] nums, long k) {
    int n = nums.length, best = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            long sum = 0;
            for (int t = i; t <= j; t++) sum += nums[t];
            if (sum == k) best = Math.max(best, j - i + 1);
        }
    }
    return best;
}

Complexity. Time O(n^3): O(n^2) subarrays, each summed in O(n). Space O(1).

Approach 2: Better, running sum per start

Intuition. The third loop recomputes sums that differ from the previous one by a single element. Keep a running sum instead: once the start i is fixed, extending the end from j - 1 to j only requires adding nums[j]. That removes an entire factor of n.

Algorithm.

  1. For every start i: set sum = 0.
  2. For every end j ≥ i: add nums[j] to sum; if sum == k, record j - i + 1.
  3. Return the largest recorded length, or 0.
static int better(int[] nums, long k) {
    int n = nums.length, best = 0;
    for (int i = 0; i < n; i++) {
        long sum = 0;
        for (int j = i; j < n; j++) {
            sum += nums[j];
            if (sum == k) best = Math.max(best, j - i + 1);
        }
    }
    return best;
}

Complexity. Time O(n^2): one constant-time step per (start, end) pair. Space O(1).

Unlike the non-negative version, we cannot break when sum > k: a negative element further right may bring the sum back down to k. For n = 10^5 this is still around 5 × 10^9 steps, too slow.

Why two pointers fail here

With non-negative numbers, the classic trick is a sliding window: extend the right end, and shrink from the left while the sum exceeds k. The argument relies on sums being monotone in the window size. Negative numbers break that. Take example 3, [3, -2, 1] with k = 2: after reading 3 the window sum is 3 > 2, so the window shrinks and throws away the 3. But the only subarray with sum 2 is the whole array, which needs that 3. The window can never recover an element it has dropped, so it returns 0 instead of 3. Any approach for this problem must be able to “look back” at arbitrary earlier positions, which is exactly what a hash map of prefix sums provides.

Approach 3: Optimal, prefix sums with a hash map

Intuition. Let prefix(i) be the sum of nums[0..i]. The sum of a subarray j+1..i is prefix(i) - prefix(j). Rearranged: the subarray ending at i has sum k exactly when some earlier prefix equals prefix(i) - k. So, scanning left to right, we keep a map from each prefix value to the first index where it occurred. At index i we look up prefix(i) - k; if it is present at index j, the subarray j+1..i has length i - j. Using the first occurrence makes the subarray as long as possible.

The empty prefix has sum 0 and “ends” at index -1. Seeding the map with {0 → -1} lets subarrays that start at index 0 be found by the same lookup: their length is i - (-1) = i + 1.

Nothing here assumes anything about the sign of the elements. Prefix sums go up and down freely; the map does not care.

Algorithm.

  1. Create firstIndex containing {0 → -1}; set prefix = 0, best = 0.
  2. For every index i: prefix += nums[i].
    • Look up prefix - k. If found at index j, update best with i - j.
    • If prefix is not yet a key, store prefix → i. Never overwrite an existing key.
  3. Return best.
static int optimal(int[] nums, long k) {
    Map<Long, Integer> firstIndex = new HashMap<>();   // prefix sum -> earliest index where it occurs
    firstIndex.put(0L, -1);                            // the empty prefix, so subarrays starting at 0 are found
    long prefix = 0;
    int best = 0;
    for (int i = 0; i < nums.length; i++) {
        prefix += nums[i];
        Integer j = firstIndex.get(prefix - k);
        if (j != null) best = Math.max(best, i - j);
        firstIndex.putIfAbsent(prefix, i);
    }
    return best;
}

Dry run on nums = [1, -1, 5, -2, 3], k = 3:

i nums[i] prefix look up prefix - k found at best map after
0 1 1 -2 no 0 {0→-1, 1→0}
1 -1 0 -3 no 0 unchanged: 0 already present
2 5 5 2 no 0 {…, 5→2}
3 -2 3 0 -1 4 {…, 3→3}
4 3 6 3 3 4 (1 is not better) {…, 6→4}

At i = 1 the prefix 0 reappears. Keeping the original 0 → -1 is what later produces the length-4 answer at i = 3; overwriting it with 0 → 1 would have given 3 - 1 = 2.

Complexity. Time O(n) on average: one lookup and one conditional insertion per element. Space O(n): the map holds at most n + 1 prefix values.

Edge cases and pitfalls