Python – Check if Any Subarray Has a Sum Equal to 0

Python – Check if Any Subarray Has a Sum Equal to 0

This tutorial covers a popular DSA interview problem: checking if any subarray within a given array has a sum equal to 0. We will explain the problem, show sample inputs and outputs, describe the solution steps, and provide a complete Python program to solve the problem.

Problem Statement

Given an array arr of integers, determine if there exists a contiguous subarray whose sum is equal to 0. If such a subarray exists, return True; otherwise, return False.

Sample Input and Output

Example 1:

Input: arr = [4, 2, -3, 1, 6]
Output: True
Explanation: The subarray [2, -3, 1] has a sum of 0.

Example 2:

Input: arr = [1, 2, 3]
Output: False
Explanation: No subarray with sum 0 exists.

Solution Approach

We can solve this problem efficiently using the prefix sum technique along with a hash set to track previously seen sums. Here are the steps:

1. Initialize an empty set to store prefix sums.
2. Initialize a variable prefix_sum to 0.
3. Iterate through each element in the array, adding the current element to prefix_sum.
4. If prefix_sum becomes 0 or is already in the set, a subarray with sum 0 exists.
5. If not, add prefix_sum to the set and continue.
6. If the loop ends without finding a duplicate prefix sum or a zero value, no zero-sum subarray exists.

Python Program

# Function to check if a zero-sum subarray exists
def has_zero_sum_subarray(arr):
    prefix_sum = 0
    seen_sums = set()
    
    for num in arr:
        prefix_sum += num
        # If prefix_sum is 0 or already seen, a zero-sum subarray exists
        if prefix_sum == 0 or prefix_sum in seen_sums:
            return True
        seen_sums.add(prefix_sum)
    
    return False

# Sample Input 1
arr1 = [4, 2, -3, 1, 6]
print("Input:", arr1)
print("Output:", has_zero_sum_subarray(arr1))

# Sample Input 2
arr2 = [1, 2, 3]
print("Input:", arr2)
print("Output:", has_zero_sum_subarray(arr2))

This solution uses a single traversal of the array, achieving O(n) time complexity with O(n) additional space, making it efficient for interview scenarios.

Conclusion

In this tutorial, we used the prefix sum technique along with a hash set to check if any subarray within an array has a sum equal to 0.