Find All Subarrays with a Given Sum

Title: Find All Subarrays with a Given Sum

Given an array of integers and a target sum, the task is to find every contiguous subarray whose elements add up exactly to that target. This is not the same as checking whether one such subarray exists; you need to report every matching start and end index, and the array may contain negative numbers.

In this guide, you’ll learn how to solve this problem in a single pass using a running prefix sum and a HashMap, walk through a step-by-step trace on a concrete input, and look at the common mistakes, edge cases, and interview follow-up questions that come up around this problem.

Understanding the Problem

The brute-force way to solve this is to check the sum of every possible subarray using two nested loops, which costs O(n^2) time. The faster approach relies on a simple identity: the sum of the subarray from index start to index end equals the prefix sum ending at end minus the prefix sum ending at start - 1.

If you record every prefix sum you have already seen along with the indices where it occurred, you can answer ‘does an earlier prefix sum exist that would make this subarray equal the target’ in constant time per index, using a hashmap lookup instead of a nested loop. This works even when the array has negative numbers, which rules out a plain sliding window.

Approach

The algorithm scans the array once, maintaining a running prefixSum and a map from each prefix sum value to the list of indices that produced it. At every index, it checks whether prefixSum - targetSum has occurred before; every index stored under that value marks the end of an earlier subarray that completes a match.

1. Initialize an empty result list to hold the matching (start, end) index pairs.
2. Create a Map<Integer, List<Integer>> named prefixSumIndices and seed it with 0 mapped to a list containing -1, representing the empty prefix before the array starts.
3. Walk through the array once, maintaining a running prefixSum that adds arr[i] at every step.
4. At each index i, compute needed = prefixSum - targetSum. If needed is a key in the map, every index stored under it marks the end of a subarray that sums to targetSum.
5. For every startIndex found under needed, record the pair (startIndex + 1, i) as a matching subarray.
6. Add the current prefixSum to the map, appending index i to its list of indices (creating the list on first occurrence).
7. Repeat until every index has been processed, then return the full list of matching subarrays.

Java Program

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FindSubarraysWithGivenSum {

    public static List<int[]> findSubarrays(int[] arr, int targetSum) {
        List<int[]> result = new ArrayList<>();
        Map<Integer, List<Integer>> prefixSumIndices = new HashMap<>();

        List<Integer> seed = new ArrayList<>();
        seed.add(-1);
        prefixSumIndices.put(0, seed);

        int prefixSum = 0;
        for (int i = 0; i < arr.length; i++) {
            prefixSum += arr[i];
            int needed = prefixSum - targetSum;

            if (prefixSumIndices.containsKey(needed)) {
                for (int startIndex : prefixSumIndices.get(needed)) {
                    result.add(new int[]{startIndex + 1, i});
                }
            }

            prefixSumIndices.computeIfAbsent(prefixSum, key -> new ArrayList<>()).add(i);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, -2, 6, 1, -3, 5};
        int targetSum = 6;

        List<int[]> subarrays = findSubarrays(arr, targetSum);

        System.out.println("Subarrays with sum " + targetSum + ":");
        for (int[] range : subarrays) {
            int start = range[0];
            int end = range[1];
            StringBuilder sb = new StringBuilder("[");
            for (int i = start; i <= end; i++) {
                sb.append(arr[i]);
                if (i < end) {
                    sb.append(", ");
                }
            }
            sb.append("]");
            System.out.println("Indices " + start + " to " + end + " -> " + sb);
        }
    }
}

Explanation of the Program

The findSubarrays method takes the input array and the target sum, then builds a prefixSumIndices map. It seeds the map with 0 mapped to [-1] before the loop starts; without this seed, subarrays that begin at index 0 would never be found, since there would be no ’empty prefix’ entry to match against.

Inside the loop, prefixSum accumulates arr[i] on every iteration. The method then checks whether needed = prefixSum - targetSum already exists as a key. If it does, every index stored under that key is the end of an earlier prefix, so the subarray starting right after that index and ending at i sums to exactly targetSum.

After checking for matches, the method records the current prefixSum using computeIfAbsent, which creates a new list the first time a prefix sum is seen and simply appends to it on repeat occurrences. The main method then prints each matching subarray by slicing arr between the recorded start and end indices.

Step-by-Step Trace

For arr = {1, 2, 3, -2, 5} with targetSum = 5, the trace below shows prefixSum and the map lookup at every index.

At the end of each iteration, prefixSumIndices holds every prefix sum computed so far mapped to all indices that produced it, so whenever prefixSum - targetSum is present as a key, it always identifies the end of a valid subarray summing to targetSum.

Examples

Example 1: Positive and Negative Numbers

This is the array used in the main method above. It mixes positive and negative values and produces three matching subarrays.

int[] arr = {4, 2, -2, 6, 1, -3, 5};
int targetSum = 6;
List<int[]> result = FindSubarraysWithGivenSum.findSubarrays(arr, targetSum);
// Output:
// Indices 0 to 1 -> [4, 2]
// Indices 1 to 3 -> [2, -2, 6]
// Indices 3 to 3 -> [6]

Example 2: All Positive Numbers with Multiple Matches

With only positive numbers, a sliding window would also work, but the prefix-sum approach handles it just as well and still finds every overlapping match.

int[] arr = {5, 3, 2, 8, 1, 4};
int targetSum = 10;
List<int[]> result = FindSubarraysWithGivenSum.findSubarrays(arr, targetSum);
// Output:
// Indices 0 to 2 -> [5, 3, 2]
// Indices 2 to 3 -> [2, 8]

Example 3: No Matching Subarray

When no contiguous run of elements adds up to the target, findSubarrays simply returns an empty list instead of throwing an error.

int[] arr = {1, 2, 3};
int targetSum = 100;
List<int[]> result = FindSubarraysWithGivenSum.findSubarrays(arr, targetSum);
// Output:
// (no matching subarrays, result.isEmpty() is true)

Common Mistakes to Avoid

These are the mistakes learners most often make when implementing this exact algorithm.

• Forgetting to seed the map with prefix sum 0 – without prefixSumIndices.put(0, [-1]) before the loop, subarrays that start at index 0 are silently missed because there is no entry for the empty prefix. Always seed the map before iterating.
• Using a single index instead of a list per prefix sum – storing Map<Integer, Integer> instead of Map<Integer, List<Integer>> overwrites earlier occurrences of a repeated prefix sum, so only the most recent subarray is ever found. Store a list of indices per prefix sum so every match gets reported.
• Reaching for a sliding window when negative numbers are possible – a sliding window only works correctly when every element is positive, since the window sum must grow monotonically as it expands. Use the prefix-sum and hashmap approach whenever the array can contain negative values.
• Recomputing each subarray sum with a nested loop – this still works, but turns the algorithm back into O(n^2) and defeats the purpose of tracking prefix sums. Update prefixSum incrementally instead of resumming from scratch.
• Reporting the start index without the plus-one offset – recording startIndex instead of startIndex + 1 includes one extra element at the front of every reported subarray. Remember the map stores the index immediately before the subarray begins.

Edge Cases to Test

Walking through these cases out loud is exactly what an interviewer wants to see before you start coding.

• Empty array
• Single-element array equal to the target sum
• All negative elements
• Target sum of zero
• Multiple overlapping subarrays with the same sum
• Target sum not achievable by any subarray
• Array containing Integer.MIN_VALUE or Integer.MAX_VALUE
• Duplicate prefix sums occurring at non-adjacent indices

Additional Considerations

The algorithm runs in O(n) time on average, since each index does one map lookup and one map insert, both amortized O(1) operations on a HashMap. This is a significant improvement over the O(n^2) brute-force approach of checking every pair of start and end indices.

Space usage is O(n) in the worst case, since every prefix sum and its indices may need to be stored. If the array contains values near Integer.MIN_VALUE or Integer.MAX_VALUE, accumulating prefixSum as an int can overflow; switching prefixSum to a long removes that risk with a small change to the code.

If the array is known to contain only non-negative numbers, a sliding window avoids the hashmap entirely and uses O(1) extra space, trading generality for a lower memory footprint. The hashmap-based approach is the one to reach for whenever that guarantee does not hold.

Interview Follow-up Questions

Once you can explain the base solution, expect the interviewer to push on these variations.

• What if you only need to know whether any subarray sums to the target, not all of them? – short-circuit and return as soon as the first match is found instead of collecting every pair.
• What if the array is guaranteed to contain only non-negative numbers? – a two-pointer sliding window becomes viable, since expanding the window can only increase the sum, giving O(n) time without a hashmap.
• What if you need the count of matching subarrays rather than their indices? – keep a Map<Integer, Integer> of prefix-sum frequencies instead of a map of index lists, and sum the matching frequencies to get the count in O(n) time with less memory.
• What if the array arrives as a stream and the full input cannot be stored? – maintain the running prefixSum and the frequency map incrementally as elements arrive, since the algorithm only ever looks at sums seen so far.
• What if the input is read-only and you must avoid allocating a list per prefix sum? – reporting every matching subarray fundamentally requires remembering prior prefix sums somewhere, so true constant extra space is only achievable if you need existence or a count, not the full list of subarrays.

Conclusion

Finding all subarrays with a given sum is a good example of how restating a problem in terms of prefix sums turns an O(n^2) brute-force scan into a single O(n) pass. The same prefix-sum and hashmap pattern shows up across many array problems, so it is worth practicing until the seeding step and the plus-one offset feel automatic.

Try adapting the program above to return counts instead of indices, or to work on a stream of integers instead of a fixed array. You can learn more about array-based problems like this one in the Arrays category on this site.