Find subarrays with sum equal to zero

February 15, 2024

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) {
                        subarray.add(nums[j]);
                        j++;
                    }
                    subarrays.add(subarray);
                }
                zeroSumSubarrays.addAll(subarrays);
            }

            // Update the prefix sums map with the current prefix sum
            List<Integer> startIndices = prefixSumsMap.getOrDefault(prefixSum, new ArrayList<>());
            startIndices.add(i);
            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

We start by importing the necessary Java utilities, including List and Map from the java.util package.
The findAllZeroSumSubarrays method takes an integer array nums as input and returns a list of lists of integers, representing the zero sum subarrays.
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.
We initialize prefixSum to track the cumulative sum as we iterate through the array.
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).
We iterate over the elements of the input array nums using a for loop.
For each element, we update prefixSum by adding the current element’s value.
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.
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.
We add all the subarrays found in step 9 to the zeroSumSubarrays list.
We update prefixSumsMap with the current prefixSum and the current index i.
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]

Learn more about array implementation: Array

Conclusion:

Armed with the knowledge gained from this guide and armed with our robust Java implementation, you’re now equipped to tackle the challenge of identifying subarrays with 0 sum like a seasoned programmer. Embrace the journey, embrace the challenge, and let your Java prowess shine bright.

Latest Posts: