Zero Sum Subarrays - Problem with Solution

Posted 2 years ago in EDUCATION.

Zero Sum Subarrays is the famous Data Structure and Algorithm problem asked in different interviews.

Zero Sum Subarrays - Problem with Solution

Introduction

A component or section of an array is frequently referred to as a subarray. An array is a collection of variables defined by a programmer. Rather than generating several variables, the programmer might define a single array with multiple labels. Zero Sum Subarrays is the famous Data Structure and Algorithm problem asked in different interviews. 

Problem Statement

You have given an array, you have to find all the subarrays whose sum is equal to zero (0). 

For Example:

Input:  { 3, 4, -7, 3, 1, 3, 1, -4, -2}

Output:

Subarray starts from index 1 to 3.

Subarray starts from index 2 to 4.

Subarray starts from index 3 to 6.

Subarray starts from index 6 to 8.

Approach 1: Using Brute Force

A naive solution is to consider all subarrays and find their sum. If the subarray sum is equal to 0, print it.

Following code is implemented in C++.


#include <bits/stdc++.h>

using namespace std;

 

// Function to print all subarrays with a zero-sum

// in a given array

void printAllSubarrays(int nums[], int n)

{

    // consider all subarrays starting from `i`

    for (int i = 0; i < n; i++)

    {

        int sum = 0;

 

        // consider all subarrays ending at `j`

        for (int j = i; j < n; j++)

        {

            sum += nums[j];

 

            // if the sum is seen before, we have found a subarray with zero sum

            if (sum == 0) {

                cout << "Subarray starts from index " << i << " to " << j << ".\";

            }

        }

    }

}

 

int main()

{

    int nums[] = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 };


    int n = sizeof(nums)/sizeof(nums[0]);

 

    printAllSubarrays(nums, n);

 

    return 0;

}

Output:

Time Complexity: O(n3)

Space Complexity: O(1)

Approach 2: Using Multimap

We can use multimap to display all subarrays in the supplied array that have a zero-sum. The idea is to create an empty multimap to record the ending index of all subarrays with a certain amount. Traverse the array, keeping track of the total number of elements viewed so far. If the sum has been seen before, at least one subarray with zero-sum ends at the current index. Finally, print all subarrays of this kind.

Following is a C++ code implementation.

#include <bits/stdc++.h>

using namespace std;

 

// Function to print all subarrays with a zero-sum in a given array

void printAllSubarrays(int nums[ ], int n)

{

    unordered_multimap<int, int> map;

 

    // insert (0, -1) pair into the map to handle the case when

    // subarray with zero-sum starts from index 0

    map.insert(pair<int, int>(0, -1));

 

    int sum = 0;

 

    for (int i = 0; i < n; i++)

    {

        sum += nums[i];

 

        // if the sum is seen before, there exists at least one subarray with sum zero.

        if (map.find(sum) != map.end())

        {

            auto it = map.find(sum);

 

            // find all subarrays with the same sum

            while (it != map.end() && it->first == sum)

            {

                cout << "Subarray starts from index " << it->second + 1 << " to " << i << ".\";

                it++;

            }

        }

 

        // insert (sum so far, current index) pair into multimap

        map.insert(pair<int, int>(sum, i));

    }

}

 

int main()

{

    int nums[ ] = { 6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7 };

    int n = sizeof(nums)/sizeof(nums[0]);

 

    printAllSubarrays(nums, n);

 

    return 0;

}

 

Output:

Time Complexity: O(n2)

Space Complexity: O(n)

Frequently Asked Questions

What is a contiguous subsequence?

A contiguous subsequence of a list S is one that consists of S's consecutive entries. 15 -30, 10 is a continuous subsequence if S is {5, 15, -30, 10, -5, 40, 10}.

What is Subarray?

 A component or section of an array is frequently referred to as a subarray. An array is a collection of variables defined by a programmer.

Is Subsequence and Subarray the same?

A subarray or substring must be contiguous, while a subsequence does not have to be. That is, subsequences do not have to appear in the same order as the main sequences.

Can an array be Subarray of itself?

The full array itself is a subarray of itself. An empty array is a subarray of any array.

Conclusion

In this article we had discussed the entire detailed explanation of Zero Sum Subarray. We had solved the problem in 2 different approaches. We also learnt the time and space complexity of both the approaches.

Tags: array, subarray,
135 Views

Comments

Picture


EXPLORE MORE INTEREST