GeeksforGeeks App
Open App
Browser
Continue

Java Program to Find if there is a subarray with 0 sum

Given an array of positive and negative numbers, find if there is a subarray (of size at-least one) with 0 sum.

Examples :

Input: {4, 2, -3, 1, 6}
Output: true
Explanation:
There is a subarray with zero sum from index 1 to 3.

Input: {4, 2, 0, 1, 6}
Output: true
Explanation:
There is a subarray with zero sum from index 2 to 2.

Input: {-3, 2, 3, 1, 6}
Output: false

A simple solution is to consider all subarrays one by one and check the sum of every subarray. We can run two loops: the outer loop picks a starting point i and the inner loop tries all subarrays starting from i (See this for implementation). The time complexity of this method is O(n2).
We can also use hashing. The idea is to iterate through the array and for every element arr[i], calculate the sum of elements from 0 to i (this can simply be done as sum += arr[i]). If the current sum has been seen before, then there is a zero-sum array. Hashing is used to store the sum values so that we can quickly store sum and find out whether the current sum is seen before or not.
Example :

```arr[] = {1, 4, -2, -2, 5, -4, 3}

If we consider all prefix sums, we can
notice that there is a subarray with 0
sum when :
1) Either a prefix sum repeats or
2) Or prefix sum becomes 0.

Prefix sums for above array are:
1, 5, 3, 1, 6, 2, 5

Since prefix sum 1 repeats, we have a subarray
with 0 sum. ```

Following is implementation of the above approach.

Java

 `// A Java program to find ``// if there is a zero sum subarray``import` `java.util.HashSet;``import` `java.util.Set;`` ` `class` `ZeroSumSubarray ``{``    ``// Returns true if arr[] ``    ``// has a subarray with sero sum``    ``static` `Boolean subArrayExists(``int` `arr[])``    ``{``        ``// Creates an empty hashset hs``        ``Set hs = ``new` `HashSet();`` ` `        ``// Initialize sum of elements``        ``int` `sum = ``0``;`` ` `        ``// Traverse through the given array``        ``for` `(``int` `i = ``0``; i < arr.length; i++) ``        ``{``            ``// Add current element to sum``            ``sum += arr[i];`` ` `            ``// Return true in following cases``            ``// a) Current element is 0``            ``// b) sum of elements from 0 to i is 0``            ``// c) sum is already present in hash map``            ``if` `(arr[i] == ``0` `                ``|| sum == ``0` `                ``|| hs.contains(sum))``                ``return` `true``;`` ` `            ``// Add sum to hash set``            ``hs.add(sum);``        ``}`` ` `        ``// We reach here only when there is``        ``// no subarray with 0 sum``        ``return` `false``;``    ``}`` ` `    ``// Driver code``    ``public` `static` `void` `main(String arg[])``    ``{``        ``int` `arr[] = { -``3``, ``2``, ``3``, ``1``, ``6` `};``        ``if` `(subArrayExists(arr))``            ``System.out.println(``                ``"Found a subarray with 0 sum"``);``        ``else``            ``System.out.println(``"No Such Sub Array Exists!"``);``    ``}``}`

Output

`No Such Sub Array Exists!`

Time Complexity of this solution can be considered as O(n) under the assumption that we have good hashing function that allows insertion and retrieval operations in O(1) time.
Space Complexity: O(n) .Here we required extra space for unordered_set to insert array elements.

Please refer complete article on Find if there is a subarray with 0 sum for more details!

My Personal Notes arrow_drop_up
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}