☕ DSA Java Articles

Topics › Arrays › Easy

Largest Subarray with K sum

Medium TUF ID 2837 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array of integers nums, which may contain positive numbers, negative numbers and zeros, and an integer k. Return the length of the longest contiguous subarray whose elements add up to exactly k. If no such subarray exists, return 0.

The sheet’s older wording, “largest subarray with 0 sum”, is the special case k = 0; everything below handles it unchanged.

Constraints: 0 ≤ n ≤ 10^5, every value and k fit in a 32-bit signed integer. Sums of many elements do not necessarily fit, so they are kept in a long.

Example 1

nums = [10, 5, 2, 7, 1, 9], k = 15
answer = 4          // [5, 2, 7, 1]; [10, 5] also sums to 15 but is shorter

Example 2

nums = [1, -1, 5, -2, 3], k = 3
answer = 4          // [1, -1, 5, -2]; the single element [3] also works but is shorter

Example 3

nums = [1, 2, 3], k = 7
answer = 0          // no contiguous block sums to 7

Approach 1: Brute force

Intuition. A subarray is fixed by its first index i and last index j. Enumerate every pair i ≤ j, add up the elements between them, and remember the longest pair whose sum is k. It is obviously correct because it looks at every candidate.

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, update best with j - i + 1.
  4. Return best.
static int bruteForce(int[] nums, int 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): there are about n^2 / 2 subarrays and summing one takes up to n steps. Space O(1).

The innermost loop is pure waste: the sum of nums[i..j] is just the sum of nums[i..j-1] plus nums[j], which we computed one iteration earlier.

Approach 2: Better, running sum per start

Intuition. Fix the start i and move the end j forward one step at a time, adding nums[j] to a running sum. Each subarray’s sum now costs O(1) instead of O(n).

It is tempting to break as soon as the running sum exceeds k. Do not. With negative numbers the sum can fall back to k later: in [1, -1, 5, -2] with k = 3, the sum from index 0 goes 1, 0, 5, 3, passing above 3 before landing on it.

Algorithm.

  1. For every start i: set sum = 0.
  2. For every end j from i to n - 1: add nums[j] to sum; if sum == k, update best with j - i + 1.
  3. Return best.
static int better(int[] nums, int 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): still every subarray, but each in constant time. Space O(1). For n = 10^5 that is 5 × 10^9 steps, too slow.

Approach 3: Optimal, prefix sums with a hash map

Intuition. Define the prefix sum P[j] = nums[0] + ... + nums[j], with P[-1] = 0 for the empty prefix. Then the sum of the subarray from i + 1 to j is a difference of two prefix sums:

sum(i+1 .. j) = P[j] - P[i].

So a subarray ending at j sums to k exactly when some earlier prefix has the value P[j] - k. That turns “search over all starts” into “look up one value”, which a hash map does in O(1).

We want the longest subarray ending at j, which means the smallest index i with P[i] = P[j] - k. So the map stores, for each prefix value, the first index where it occurred, and later occurrences of the same value never overwrite it (putIfAbsent). The entry 0 → -1 represents the empty prefix; without it, subarrays that begin at index 0 would be missed.

Algorithm.

  1. Create a map first with the single entry 0 → -1. Set prefix = 0 (a long), best = 0.
  2. For each index j:
    • Add nums[j] to prefix.
    • If prefix - k is in the map at index i, update best with j - i.
    • Insert prefix → j only if prefix is not already a key.
  3. Return best.
static int optimal(int[] nums, int k) {
    Map<Long, Integer> first = new HashMap<>();
    first.put(0L, -1);                           // empty prefix, so a subarray may start at index 0
    long prefix = 0;
    int best = 0;
    for (int j = 0; j < nums.length; j++) {
        prefix += nums[j];
        Integer i = first.get(prefix - k);       // sum(i+1..j) == k  <=>  prefix[i] == prefix[j] - k
        if (i != null) best = Math.max(best, j - i);
        first.putIfAbsent(prefix, j);            // keep the earliest index: it gives the longest subarray
    }
    return best;
}

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

j nums[j] prefix prefix - k found at length best map after
0 1 1 -2 - - 0 {0→-1, 1→0}
1 -1 0 -3 - - 0 unchanged: 0 already stored at -1
2 5 5 2 - - 0 adds 5→2
3 -2 3 0 -1 4 4 adds 3→3
4 3 6 3 3 1 4 adds 6→4

Row j = 1 is the crucial one. The prefix 0 appears again, and if we overwrote 0 → -1 with 0 → 1, the lookup at j = 3 would return index 1 and report length 2 instead of 4.

Complexity. Time O(n) on average: one pass, each map operation O(1) expected. Space O(n) for the map, which can hold up to n + 1 distinct prefix sums. A TreeMap would give a guaranteed O(n log n) instead of an expected O(n).

Why not a sliding window? When every element is positive, growing a window always increases its sum and shrinking always decreases it, so two pointers solve the problem in O(n) time and O(1) space. Negative numbers and zeros destroy that monotonic behaviour. For [3, -2, 1] with k = 1, the window shrinks past 3 as soon as the sum exceeds 1, and it never sees [3, -2], a valid subarray of length 2. The prefix-sum map makes no assumption about signs, which is why it is the general solution.

Edge cases and pitfalls