21. Find if There Is a Subarray With Sum Equal to 0

Given an array, determine whether any contiguous subarray sums to exactly 0. Print 'Yes' or 'No'.

Input: The first line contains an integer n. The second line contains n space-separated integers, which may include negative values. Output: Print 'Yes' if any contiguous subarray sums to exactly 0, otherwise print 'No'.

1 <= n <= 10^5

Don't forget that a prefix sum of exactly 0 at any point (not just a REPEATED value) also means a zero-sum subarray exists - specifically, the subarray from the very beginning up to that point.

Check whether ANY contiguous stretch of an array adds up to exactly zero. Brute force: Check every possible contiguous subarray directly, summing its elements to see if it equals zero - this costs O(n²) or O(n³) depending on how sums are recomputed, too slow for large arrays. Optimised: This is a direct, simpler application of the same 'prefix sum + hash set' technique used for counting ALL zero-sum subarrays (in the Hashing category) - here you only need to detect whether even ONE exists, so you can stop the instant you find a repeated (or zero) prefix sum, without needing to count every occurrence.

For every starting index i, extend a running sum through every ending index j >= i, checking after each extension whether the running sum equals 0. This checks every one of the O(n^2) subarrays directly and is easy to verify correct, but recomputes sums independently for every start, which is wasteful. Time: O(n^2) Space: O(1)

Compute the prefix sum array once, where prefix[i] is the sum of the first i elements (with prefix[0] = 0). A subarray sums to zero exactly when two prefix sums are equal (the elements strictly between them cancel out), or when some prefix sum itself is 0. Sort the prefix sums and scan for any adjacent equal pair (or a zero) to detect this. Sorting replaces the need for a full pairwise comparison, though it costs an O(n log n) sort instead of the O(n) a hash-based check could achieve. Time: O(n log n) Space: O(n)

Walk through the array once, maintaining a running prefix sum and a hash set of every prefix sum seen so far (starting with 0 already in the set to catch a zero-sum prefix directly). At each step, if the current running sum is already in the set, a zero-sum subarray exists (the portion between the previous occurrence and now); otherwise, add the current sum to the set and continue. This finds the answer in a single linear pass using O(1) average-time set lookups, avoiding the sort entirely. Time: O(n) Space: O(n)

1. Scan through the array, keeping a running total (prefix sum) as you go, and remembering every prefix sum value you've seen in a hash set. 2. If the running total ever becomes exactly 0 at some point, the stretch from the very start up to there sums to zero - answer Yes. 3. If the running total ever repeats a value you've seen before, everything between those two points summed to zero - also answer Yes. 4. If you finish the whole scan without either of those happening, no zero-sum subarray exists - answer No.

Time: O(n) - one single pass through the array with instant hash-set lookups. Space: O(n), for the hash set of seen prefix sums.

n = 1 with that single element being 0 versus nonzero; an array with no zero-sum subarray (print 'No'); and n = 10^5 (largest, confirming the hash-set prefix-sum approach is O(n)).

Be ready to connect this directly to the more general 'count ALL zero-sum subarrays' problem - this is the simpler yes/no version of that exact same core technique.