Sub-array with 0 sum

Given an array of integers A, find and return whether the given array contains a non-empty subarray with a sum equal to 0.

If the given array contains a sub-array with sum zero return 1, else return 0.

Problem Constraints

1 <= |A| <= 100000

-10^9 <= A[i] <= 10^9

Example:

[3,-4,1]

output: 0

Brute-Force solution

to find if a subarray with a zero sum exists involves generating every possible contiguous subarray and checking if its elements sum to zero.

Algorithm

1. Use a nested loop structure to iterate through all possible subarrays.

   • The outer loop, with an index i, selects a starting element for the subarray.

   • The inner loop, with an index j, iterates from i to the end of the array, defining the ending element of the subarray.

2. Inside the inner loop, maintain a running current_sum of the subarray from index i to j.

3. If current_sum ever equals 0, a zero-sum subarray has been found. Return true.

4. If the loops complete without finding such a subarray, return false.

Complexity analysis

• Time complexity: O(N²), where N is the number of elements in the array. This is because there are two nested loops that iterate through the array.

• Space complexity: O(1), as this approach does not require any extra storage space.

Optimization of brute force

You can optimize the calculation of the subarray sum to avoid a third nested loop, which would result in an O(N³) solution. By keeping a running sum in the inner loop, you calculate each subarray sum in O(1) time, leading to the overall O(N²) complexity.

Optimal Solution:

the task is to determine if there exists a contiguous subarray within a given array of positive and negative integers that sums to zero. A highly efficient solution uses a hash set to track prefix sums

Intuition behind the prefix sum approach

The key insight is based on prefix sums. A prefix sum at an index i is the sum of all elements from index 0 up to i. Let's say prefix_sum[i] = arr[0] + ... + arr[i].

A subarray from index j+1 to i has a sum of zero if and only if prefix_sum[i] - prefix_sum[j] = 0, which means prefix_sum[i] = prefix_sum[j]. This indicates that a zero-sum subarray exists between the indices where the prefix sums are equal.

There are two main cases for a zero-sum subarray:

1. A prefix sum is 0: If at any point the running sum from the start of the array becomes 0, then the subarray from index 0 to the current index has a sum of zero.

2. A prefix sum repeats: If a prefix sum is seen again, it means the sum of the elements between the first and second occurrences of that prefix sum is zero.

Steps:

1. Initialize sum=0 and a hash set.

2. Traverse the array, updating the running sum.

3. Check if the running sum is 0 or already exists in the hash set, which would imply a subarray with sum zero.

4. if found, return true, indicating the presence of such a subarray.

Complexity analysis

• • Time complexity: O(N), where N is the number of elements in the array. You iterate through the array only once. Hash set operations (insertion and lookup) take an average time of O(1).

    • Space complexity: O(N), in the worst case, to store all the prefix sums in the hash set. This would happen if no prefix sums repeat.

public int solve(int[] A) {  
          long sum=0; 
         HashSet<Long> set =new HashSet<Long>();
         set.add(0L);  
        for(int i=0;i<A.length;i++){
           sum+=A[i];
            if(set.contains(sum) || sum==0){ 
              return 1; 
          } 
          set.add(sum); 
      } 
      return 0; 
  } 
}