Practice › Hashing & Two Pointers
Zero Sum Subarray
Medium · Hashing & Two Pointers · Asked at Amazon, Microsoft, Paytm
Print YES if there is a non-empty contiguous subarray with sum 0, otherwise NO.
Input
First line: n. Second line: n integers.
Output
YES or NO.
Constraints
- 1 ≤ n ≤ 10^5
- -10^5 ≤ a[i] ≤ 10^5
If the same prefix sum appears twice (or a prefix sum is 0), the part between them sums to 0.
Example 1
Input
5 4 2 -3 1 6
Output
YES
Example 2
Input
5 5 3 1 2 7
Output
NO
Hints
- sum(a[i+1..j]) = prefix[j] − prefix[i].
- So a zero-sum subarray exists exactly when some prefix sum repeats (count the empty prefix 0 as already seen).
Approach
Keep a hash set of the prefix sums seen so far, starting with 0 for the empty prefix. Add each element to the running sum. If the sum is already in the set, the elements since that earlier point add up to 0, so answer YES. Otherwise insert it.
Complexity: O(n) average time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
unordered_set<long long> seen = {0};
long long prefix = 0;
bool found = false;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
prefix += x;
if (!seen.insert(prefix).second) found = true;
}
cout << (found ? "YES" : "NO") << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
seen, prefix, found = {0}, 0, False
for x in data[1 : data[0] + 1]:
prefix += x
if prefix in seen:
found = True
break
seen.add(prefix)
print("YES" if found else "NO")Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Set<Long> seen = new HashSet<>();
seen.add(0L);
long prefix = 0;
boolean found = false;
for (int i = 0; i < n; i++) {
prefix += sc.nextLong();
if (!seen.add(prefix)) found = true;
}
System.out.println(found ? "YES" : "NO");
}
}