# Find subarrays with sum equal to zero

25

Title: Find subarrays with sum equal to zero

In the realm of Java programming, unravelling complex algorithms is a rite of passage. One such challenge is to Find subarrays with sum equal to zero. In this guide, we’ll embark on a journey to master this problem, equipping you with the knowledge and skills to conquer it with confidence.

## Challenge

At the heart of this endeavor lies the task of detecting contiguous sequences of elements within an array that sum up to zero. While seemingly daunting, armed with the right techniques and strategies, this challenge can be conquered.

## Exploring Techniques

Brute Force:

• A straightforward yet effective approach involves examining all possible subarrays and calculating their sums. While intuitive, this method’s time complexity of O(n^3) makes it impractical for large arrays.

Prefix Sum Technique:

• An efficient alternative lies in leveraging the prefix sum technique. By computing cumulative sums and storing them in a map, we can swiftly identify subarrays with 0 sum.

## Java Implementation

Java Program – Subarray Sum 0
``````import java.util.*;

public class FindArraySum0 {

public static List<List<Integer>> findAllZeroSumSubarrays(int[] nums) {
List<List<Integer>> zeroSumSubarrays = new ArrayList<>();
Map<Integer, List<Integer>> prefixSumsMap = new HashMap<>();
int prefixSum = 0;

// Initialize the prefix sums map with a zero sum at index 0
prefixSumsMap.put(0, new ArrayList<>(Arrays.asList(-1)));

// Iterate over the input array
for (int i = 0; i < nums.length; i++) {
prefixSum += nums[i]; // Calculate prefix sum

// Check if the prefix sum minus a previous sum in the map equals to a sum we encountered before
if (prefixSumsMap.containsKey(prefixSum)) {
// Create subarrays from the start of the current subarray to the previous subarray
List<List<Integer>> subarrays = new ArrayList<>();
for (int startIndex : prefixSumsMap.get(prefixSum)) {
int j = startIndex + 1;
List<Integer> subarray = new ArrayList<>();
// Add elements from the current subarray to the new subarray
while (j <= i) {
j++;
}
}
}

// Update the prefix sums map with the current prefix sum
List<Integer> startIndices = prefixSumsMap.getOrDefault(prefixSum, new ArrayList<>());
prefixSumsMap.put(prefixSum, startIndices);
}
return zeroSumSubarrays;
}

/**
* Main method to test the findAllZeroSumSubarrays method.
*
* @param args Command line arguments (not used).
*/
public static void main(String[] args) {
int[] nums = {4, 2, 4, -6, -4, 1};
List<List<Integer>> allZeroSumSubarrays = findAllZeroSumSubarrays(nums);

// Display zero sum subarrays
for (List<Integer> subarray : allZeroSumSubarrays) {
System.out.println("Zero Sum Subarray: " + subarray);
}
}
}``````

## Explanation

1. We start by importing the necessary Java utilities, including `List` and `Map` from the `java.util` package.
2. The `findAllZeroSumSubarrays` method takes an integer array `nums` as input and returns a list of lists of integers, representing the zero sum subarrays.
3. Inside the method, we initialize an empty list `zeroSumSubarrays` to store the zero sum subarrays and a `HashMap` called `prefixSumsMap` to store the prefix sums encountered while iterating through the array.
4. We initialize `prefixSum` to track the cumulative sum as we iterate through the array.
5. We add an initial entry to `prefixSumsMap` with key 0 and value -1, indicating that a zero sum subarray starts at index -1 (before the array starts).
6. We iterate over the elements of the input array `nums` using a for loop.
7. For each element, we update `prefixSum` by adding the current element’s value.
8. We check if the current `prefixSum` exists in `prefixSumsMap`. If it does, it means that the sum of elements from some index `startIndex + 1` to the current index `i` is zero.
9. We create subarrays starting from each `startIndex` found in `prefixSumsMap` and ending at the current index `i`. We add these subarrays to a list called `subarrays`.
10. We add all the subarrays found in step 9 to the `zeroSumSubarrays` list.
11. We update `prefixSumsMap` with the current `prefixSum` and the current index `i`.
12. Finally, we return the `zeroSumSubarrays` list containing all the zero sum subarrays.

The `main` method demonstrates the usage of the `findAllZeroSumSubarrays` method by passing an example array `{4, 2, 4, -6, -4, 1}`. It then prints out each zero sum subarray found by the method.

### Output

Output – Subarray Sum 0
``````Zero Sum Subarray: [2, 4, -6]
Zero Sum Subarray: [4, 2, 4, -6, -4]``````