☕ DSA Java Articles

Topics › Arrays › Easy

Longest subarray with given sum K(positives)

Medium TUF ID 2836 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an array nums of non-negative integers (zeros are allowed, negatives are not) and an integer k. Return the length of the longest contiguous subarray whose elements sum to exactly k. If no subarray has that sum, return 0.

The “positives” in the title is the key restriction: it is what makes the final O(1)-space solution valid. The general version with negative numbers is a separate problem on the sheet (see below).

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

Example 1

nums = [2, 3, 5, 1, 9], k = 10
answer = 3          // [2, 3, 5]; the other subarray with sum 10 is [1, 9], length 2

Example 2

nums = [1, 2, 3, 1, 1, 1, 1, 4, 2, 3], k = 3
answer = 3          // [1, 1, 1]; [1, 2], [3] and [3] at the end also sum to 3 but are shorter

Example 3

nums = [0, 0, 1, 0, 0], k = 1
answer = 5          // zeros do not change the sum, so the whole array counts

Approach 1: Brute force

Intuition. A subarray is determined by its start and end. Fix the start i, then move the end j to the right one step at a time while adding nums[j] to a running sum. Whenever the running sum equals k, the subarray i..j is a candidate. This already avoids the third loop that would re-add the elements of every subarray from scratch.

Algorithm.

  1. For every start i: set sum = 0.
  2. For every end j ≥ i: add nums[j] to sum; if sum == k, record the length j - i + 1.
  3. 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++) {
        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): about n^2 / 2 (start, end) pairs, constant work each. Space O(1).

With non-negative values you could also break out of the inner loop as soon as sum > k, since extending further can only grow the sum. That trims the constant but the worst case (all zeros, large k) is still quadratic.

Approach 2: Better, prefix sums with a hash map

Intuition. Let prefix[i] be the sum of the first i + 1 elements. The sum of the subarray j+1..i is prefix[i] - prefix[j]. We want that difference to equal k, so at position i we are asking: “has the prefix value prefix[i] - k appeared earlier, and if so, where is its earliest occurrence?” A hash map from prefix value to the first index where it occurred answers this in constant time. We want the earliest occurrence because the farther back the start, the longer the subarray.

Seed the map with 0 → -1, the sum of the empty prefix. Then a subarray that starts at index 0 is found by the same lookup without a special case: i - (-1) = i + 1.

Algorithm.

  1. Create firstIndex with the entry {0 → -1}; set prefix = 0 and best = 0.
  2. For every index i: add nums[i] to prefix.
    • If prefix - k is a key in firstIndex with value j, update best with i - j.
    • Insert prefix → i only if prefix is not already a key (keep the earliest index).
  3. Return best.
static int better(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;
}

Complexity. Time O(n) on average, one map lookup and one insertion per element. Space O(n) for the map.

The putIfAbsent is not optional. With zeros in the array the same prefix value repeats, for instance [2, 0, 0, 3] has prefixes 2, 2, 2, 5. For k = 3 the lookup at the last index asks for prefix 2, and only the earliest index 0 gives the correct length 3; overwriting would give 1.

This approach does not use the non-negativity at all, which is why it is also the answer to the general problem. Here, it is the “better” solution because we can still get rid of the map.

Approach 3: Optimal, two pointers (sliding window)

Intuition. Because every element is ≥ 0, adding an element to a window never decreases its sum, and removing one never increases it. That monotonicity means we can keep a window [left, right] and maintain the invariant “the window sum is at most k”: extend right by one, and if the sum went over k, shrink from the left until it is back under. Whenever the sum is exactly k, the window is a candidate.

Why does this find the longest one? Fix the right end r. The loop keeps left at the smallest index such that sum(left..r) ≤ k, because left only moves when the sum is strictly greater than k, and a left that was forced to move for an earlier r stays forced (adding elements on the right never lowers the sum). Now suppose some subarray s..r has sum exactly k. Then sum(s..r) ≤ k, so s ≥ left. If s > left, the window left..r is s..r plus a few extra non-negative elements, so sum(left..r) ≥ k; together with sum(left..r) ≤ k that gives equality. Either way the window at left is a valid subarray at least as long as s..r, so the window is the longest valid subarray ending at r, and taking the maximum over all r covers every possibility. With negative numbers, removing an element could increase the sum, the invariant would be meaningless, and this argument collapses.

Algorithm.

  1. Set left = 0, sum = 0, best = 0.
  2. For right from 0 to n - 1: add nums[right] to sum.
  3. While sum > k and left ≤ right: subtract nums[left] and increment left.
  4. If sum == k, update best with right - left + 1.
  5. Return best.
static int optimal(int[] nums, long k) {
    int n = nums.length, left = 0, best = 0;
    long sum = 0;
    for (int right = 0; right < n; right++) {
        sum += nums[right];
        while (sum > k && left <= right) {
            sum -= nums[left];
            left++;
        }
        if (sum == k) best = Math.max(best, right - left + 1);
    }
    return best;
}

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

right add sum shrink? window sum == k? best
0 2 2 no [0, 0] no 0
1 3 5 no [0, 1] no 0
2 5 10 no [0, 2] yes 3
3 1 11 drop 2 → 9 [1, 3] no 3
4 9 18 drop 3 → 15, drop 5 → 10 [3, 4] yes, length 2 3

Complexity. Time O(n): right moves n times and left moves at most n times in total, so the inner while costs O(n) across the whole run, not per step. Space O(1).

Edge cases and pitfalls