Given an array of integers, find any non-empty subarray whose elements sum up to zero.
Input: [5, 1, 2, -3, 7, -4]
Output: [1, 3]
Sum of [1, 2, -3] subarray is zero. It starts at index 1 and ends at index 3 of the given array, so [1, 3] is a correct answer. [3, 5] is another correct answer.
Input: [1, 2, 3, 5, -9]
Output: [-1]
There is no non-empty subarray with sum zero.
Input Format: Function has one parameter, an integer array.
Output: Return an array of integers. If no zero sum subarray is found, return [-1]. Otherwise return [start_index, end_index] of a non-empty zero sum subarray; zero-based indices; both start_index and end_index are included in the subarray. If there are multiple such subarrays, any one is a correct answer.
● 1 <= n <= 5*10^5
● -10^9 <= arr[i] <= 10^9, (i = 0,1,...,(n-1))
We provided two solutions.
A naive approach would be to iterate over all possible subarrays of input array arr, such that while on subarray [i,j], i.e. subarray starting from i-th index and ending at jth index, find sum of elements in it and if it's zero, return [i,j]. If no such subarray is found, return [-1].
O(n*n) where n is length of input arr.
As we are iterating over all possible subarrays of input array arr, time complexity will be O(n*n).
O(1).
We are not storing anything extra.
O(n) where n is length of input arr.
To store input it takes O(n) and as auxiliary space used is O(1).
Hence, O(n) + O(1) → O(n).
Notice that if there exists a zero sum subarray [i,j] in a given input array arr, then prefix sum (denote it as prefix where prefix[k] = arr[0] + arr[1] + arr[2] + ... + arr[k]) prefix[j] should be equal to prefix[i-1], as prefix[j] = prefix[i-1] + (arr[i] + arr[i+1] + ... + arr[j]), where the term in bracket is sum of subarray [i,j], which is 0.
Considering this fact, build prefix sum array prefix. If for some i, j, 0 <= i <= j < n, prefix[i-1] = prefix[j], then subarray [i,j] is the zero sum subarray.
O(n) where n is length of input arr.
To find out if any two sums of subarrays are equal or not we will store them in HashMap as prefix[k] (i.e. sum) as key and k as value. To maintain a hashmap it will take O(n) time complexity in the worst case to get and store n sums.
O(n) where n is length of input arr.
We are using hashmap to store sums. It will take O(n) of space.
O(n) where n is length of input arr.
To store input it takes O(n) and as auxiliary space used is O(n).
Hence, O(n) + O(n) → O(n).