Approach
Considering each subarray individually and verifying the total of each subarray is a straightforward method. The inner loop attempts all subarrays starting from i, and the outer loop chooses a starting point i. (See this for implementation). This approach has an O time complexity (n^2).
Hashing makes it simple for us to tackle this issue in linear time. The goal is to utilise a set to determine whether or not the provided array contains a subarray with a zero-sum. Maintain the total number of elements seen thus far while traversing the array. There is at least one subarray with a zero-sum that terminates at the current index, so if the sum has been seen previously (i.e., it exists in the set), return true; otherwise, add the sum to the set.
Algorithm
-
First, we initialise the unordered set.
-
Iterate for each element in the array.
-
Add up all the items in the range of 0 to i.
-
​​There is a zero-sum array if the current sum has been observed.
- If we do not find the sum as zero, we will return false.
Implementation in C++
#include <iostream>
#include <unordered_set>
using namespace std;
// Function to determine whether or not a given array contains a subarray with a zero-sum
bool ZeroSumFind(int array[], int n)
{
// To store the total of the items of each, build an empty set.
unordered_set<int> set;
/* To handle the situation where a subarray with zero-sum begins at index 0, insert 0 into the set.*/
set.insert(0);
int total_sum = 0;
// Iterate the provided array
for (int i = 0; i < n; i++)
{
total_sum += array[i];
/* We have discovered a subarray with zero-sum if the sum has been observed before.*/
if (set.find(total_sum) != set.end()) {
return true;
}
else {
//Add the total to the set so far.
set.insert(total_sum);
}
}
// When there is no subarray with zero-sum, we arrive at this.
return false;
}
int main()
{
int array[] = {4,2,-3,-1,0,4 };
int x = sizeof(array)/sizeof(array[0]);
ZeroSumFind(array, x) ? cout << "True": cout << "False";
return 0;
}
Input
4,2,-3,-1,0,4
Output
true
Implementation in java
// A Java application that determines whether a zero sum subarray exists
import java.util.HashSet;
import java.util.Set;
class CodingNinja
{
// if array has a subarray with zero sum, then true is returned.
static Boolean zeroSumArray(int array[])
{
// creating a hashset that is empty.
Set<Integer> hast = new HashSet<Integer>();
// variable total sum
int sum = 0;
// Iterate through the given array
for (int i = 0; i < array.length; i++)
{
sum += array[i];
/*
(1)The total of the elements from 0 to i is 0.
(2) The current element is 0.
(3) The sum is already present in the hash set
*/
if (array[i] == 0
|| sum == 0
|| hast.contains(sum))
return true;
hast.add(sum);
}
/* Only when there isn't a subarray with a sum of 0 do we arrive here.*/
return false;
}
public static void main(String arg[])
{
int array[] = { -3, 2, 3, 1, 6 };
if (zeroSumArray(array))
System.out.println(
"True");
else
System.out.println("False");
}
}
Input
-3, 2, 3, 1, 6
Output
False
Complexity
Time Complexity:
O(N), Where ‘N’ stands for the length of the array.
Reason: Time If we assume that we have a suitable hashing algorithm that enables insertion and retrieval operations in O(1) time, then the complexity of this solution can be deemed to be O(n). Where N is the size of the array.
Space Complexity:
O(N), Where ‘N’ stands for the length of the array.
Reason: The space complexity is O(n), where n is the number of elements. Here, additional space was needed so that the unordered set could insert array elements.
Also See, Hash Function in Data Structure.
Check out this problem - Subarray With 0 Sum
Frequently asked questions
Contiguous Subarrays: What are they?
A contiguous subarray is just a subarray of an array with the requirement that the subarray's contents be in the same exact order as the items in the parent array.
What does an array segment mean?
As it relates to your issue, specify the subsegment. Depending on how you described it, the answer to the question "How many ways can you split up an array of size N?" is either the permutations or combinations, which is a direct computation of O. (1).
What is an example of FIFO?
Consider what would happen if a corporation bought 100 products for $10 each, then bought 100 more for $15 each. The firm then sold 60 goods. Because the first goods acquired are the first goods sold, the cost of goods sold for each of the 60 items is $10/unit using the FIFO technique.
What is an example of a linked list in practice?
A line for a cashier is the archetypal real-life example. A stack can also be implemented using a linked list. One of those plate dispensers at a buffet restaurant that pulls the top plate off the top of the stack would be a good analogy.
Should Subarray be contiguous?
A subsequence need not be contiguous, however, a subarray or substring will always be contiguous. Therefore, it is not necessary for subsequences to occupy adjacent locations inside the parent sequences. Contiguous subsequence and subarray, however, are equivalent.
Conclusion
This article has gone through a problem related to the subarray. If you identify any errors or would want to add more details about the subject matter covered above, kindly leave a comment.
Want to learn more about the Data Structure in java? Click here.
Recommended problems -
Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more?
Please go check out our Operating system course.
Attempt our Online Mock Test Series on Coding Ninjas Studio now!
Ninja, have a great time learning.
117+ registered 