Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
2.1.1.
Input
2.1.2.
Output
2.1.3.
Explanation
2.1.4.
 
2.1.5.
Input
2.1.6.
Output
2.1.7.
Explanation
2.1.8.
 
2.1.9.
Input
2.1.10.
Output
2.1.11.
Explanation
3.
Approach 1
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Output
3.3.
Implementation in Java
3.3.1.
Output
3.4.
Time Complexity 
3.5.
Auxiliary Space Complexity 
4.
Approach 2
4.1.
Algorithm
4.2.
Implementation in C++
4.2.1.
Output
4.3.
Implementation in Java
4.3.1.
Output
4.4.
Time Complexity 
4.5.
Auxiliary Space Complexity 
5.
Frequently Asked Questions
5.1.
Which continuous sum is the largest? 
5.2.
A Subarray might be empty.  
5.3.
What is the purpose of Kadane's algorithm?
5.4.
Can a Subarray sum be achieved?  
5.5.
What is the definition of a delete operation? 
6.
Conclusion
Last Updated: Mar 27, 2024

Length of the largest subarray with 0 sum

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

A particular data structure called an array can hold a fixed-size sequential collection of identical-type elements. It is essential to think of an array as a collection of variables of the same type even though it is used to store a collection of data.

Problem Statement

Find the length of the largest sub-array with a sum of 0 in an array of integers.

Example

Input

Output

5

Explanation

The longest sub-array containing elements that add to zero is from -2 to 7.

 

Input

Output

0

Explanation

No subarray has a sum of zero.

 

Input

Output

1

Explanation

0 is the longest sub-array with elements that add up to 0.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 1

Considering each subarray individually and verifying the total of each subarray is a straightforward method. The inner loop attempts every subarray starting from i and the outer loop chooses a starting point i.

Algorithm

  1. Check the total of each sub-array as you take each one into consideration.
     
  2. Run two loops: the outer loop chooses beginning point i and the inner loop tests every sub-array starting with i.

Implementation in C++

/* C++ programme to locate the greatest subarray with 0 sum */
#include<bits/stdc++.h> 
using namespace std; 
  
// Returns the greatest subarray's length with a sum of 0. 
int maximum_Length_fun(int arr[], int n) 
{ 
    int maximum_length = 0; // Initialize result 
  
    // starting point 
    for (int i = 0; i < n; i++) 
    { 
        // Initialize starting point 
        int curr_sum = 0; 
  
        for (int j = i; j < n; j++) 
        { 
            curr_sum += arr[j]; 
  
            // update maximum_length 
            if (curr_sum == 0) 
               maximum_length = max(maximum_length, j-i+1); 
        } 
    } 
    return maximum_length; 
} 
  
int main() 
{ 
    int given_array[] = {15, -2, 2, -8, 1, 7, 10, 23}; 
    int n = sizeof(given_array)/sizeof(given_array[0]); 
    cout << "The longest 0 sum subarray's length is" 
         << maximum_Length_fun(given_array, n); 
    return 0; 
}

Output

The longest 0 sum subarray's length is 5

Implementation in Java

// Finding the greatest subarray in Java has a sum of 0.
class CodingNinja 
{ 
// returns the greatest subarray's length with a sum of 0.
static int maximum_Length_fun(int arr[], int n) 
{ 
    int maximum_length = 0;  
  
   starting point 
    for (int i = 0; i < n; i++) 
    { 
        // Initialize starting point 
        int curr_sum = 0; 
  
        for (int j = i; j < n; j++) 
        { 
            curr_sum += arr[j]; 
  
            //update 
            if (curr_sum == 0) 
                maximum_length = Math.max(maximum_length, j-i+1); 
        } 
    } 
    return maximum_length; 
} 
      
public static void main(String args[]) 
{  
    int given_array[] = {15, -2, 2, -8, 1, 7, 10, 23}; 
    int x = given_array.length; 
    System.out.println("The longest 0 sum subarray's length is"+ maximum_Length_fun(given_array, x));      
} 
}

Output

The longest 0 sum subarray's length is 5

Time Complexity 

O(N^2), Where ‘N’ stands for the length of the array.

Reason: As we are using brute force in the above programming, it contains two loops with n iterations.

Auxiliary Space Complexity 

O(1) 

Reason: No extra space is used.

Approach 2

This issue can be resolved in O(n) time using hashing. The goal is to loop through the array and, for each element, arr[i], calculate the sum of the items in the range of 0 to I (this can be done by typing sum += arr[i]). There is a zero-sum array if the current sum has been observed. The values for the aggregate are stored using hashing so that we can rapidly save the sum and determine if the current sum has been seen before or not.

Algorithm

  1. To store the sum-index pair as a key-value pair, create an additional space, an array of length n , a variable , a length , and a hash map.
     
  2. From the beginning to the end of the input array, move.
     
  3. Update the sum value at sum = sum + array[i] for each index.
     
  4. To see if the current total is in the hash map, check each index.
     
  5. Update the value of maximum length to a maximum difference of two indices, the current index and the index in the hash-map, if it is existent.
     
  6. Otherwise, add the value (sum), with the index as a key-value pair, to the hash map.
     
  7. Print the longest possible value maximum length.

Implementation in C++

//A C++ programme to determine the greatest subarray's length with sum 0.

 

#include <bits/stdc++.h> 
using namespace std; 
  
// returns the required subarray's length.
int maximum_Length_fun(int arr[], int n) 
{ 
    // initilizing Map 
    unordered_map<int, int> map_sum; 
  
    int sum = 0;       
    int maximum_length = 0;   
 
    for(int i=0; i<n; i++) 
    { 
        sum += arr[i]; 
  
        if (arr[i]==0 && maximum_length==0) 
            maximum_length = 1; 
        if (sum == 0) 
            maximum_length = i+1; 
        if(map_sum.find(sum) != map_sum.end()) 
        { 
            // Update the maximum length if this amount has been observed previously.
            maximum_length = max(maximum_length, i-map_sum[sum]); 
        } 
        else
        { 
            // If not, add this sum and an index to the hash table. 
            map_sum[sum] = i; 
        } 
    } 
  
    return maximum_length; 
} 
  
int main() 
{ 
    int given_array[] = {15, -2, 2, -8, 1, 7, 10, 23}; 
    int n = sizeof(given_array)/sizeof(given_array[0]); 
    cout << "The longest 0 sum subarray's length is" 
         << maximum_Length_fun(given_array, n); 
    return 0; 
}

Output

The longest 0 sum subarray's length is 5

Implementation in Java

// Finding the greatest subarray in Java has a sum of 0.
import java.util.HashMap; 
  
class CodingNinja { 
  
    // returns the length of the largest subarray with a total of 0.
    static int maximum_Length_fun(int checkArray[]) 
    { 
        // empty hash Map 
        HashMap<Integer, Integer> Empty_map = new HashMap<Integer, Integer>(); 
  
        int sum = 0;      
        int maximum_length = 0; 
  
        // Itrate
        for (int i = 0; i < checkArray.length; i++) 
        { 
            
            sum += checkArray[i]; 
  
            if (checkArray[i] == 0 && maximum_length == 0) 
                maximum_length = 1; 
  
            if (sum == 0) 
                maximum_length = i+1; 
  
        
            Integer prev_i = Empty_map.get(sum); 
  
      
            if (prev_i != null) 
              maximum_length = Math.max(maximum_length, i-prev_i); 
            else  // Else put this sum in hash table 
              Empty_map.put(sum, i); 
        } 
  
        return maximum_length; 
    } 
  
    public static void main(String arg[]) 
    { 
        int given_array[] = {15, -2, 2, -8, 1, 7, 10, 23}; 
        System.out.println("The longest 0 sum subarray's length is "
                           + maximum_Length_fun(given_array)); 
    } 
}

Output

The longest 0 sum subarray's length is 5

Time Complexity 

O(N), Where ‘N’ stands for the length of the array.

Reason: Under the premise that we have a decent hashing function that enables insertion and retrieval operations in O(1) time, the time complexity of this solution can be thought of as O(n).

Auxiliary Space Complexity 

O(N), Where ‘N’ stands for the length of the array.

Reason: For the HashMap.


You can also read about the Longest Consecutive Sequence. 

Frequently Asked Questions

Which continuous sum is the largest? 

One of the most typical practice interview questions is this one. Find the greatest continuous sum from an array of positive and negative numbers. If the entire array is positive, the outcome is the sum of all the numbers. The array's negative numbers add a tiny bit of complexity.

A Subarray might be empty.  

Similar to this, a "empty subarray" in computer science is a subarray in which there are no terms. Just the definition is given here. The only thing it is is a subarray whose total evaluates to 0.

What is the purpose of Kadane's algorithm?

There are numerous uses for Kadane's algorithm, some of which are listed below: calculating the largest subarray sum for the given integer array. used as an algorithm for image processing. Problems like "Station Travel in Order" and "Hotels Along the Coast" can be solved using it.

Can a Subarray sum be achieved?  

The aim is to determine the sum of each distinct sub-array sum. The sub-array sum is defined as the total of all components in a specific sub-array. Note that no other sub-array will have the same sum value as the unique sub-array sum.

What is the definition of a delete operation? 

Deletion is the process of eliminating an existing element from an array and reorganizing all of its elements. The delete action can be applied to one or more objects that meet the specified conditional expression. The delete operation can be combined with a list (of any kind), allowing the user to select the object(s) to be erased.

Conclusion

This article has gone through problems related to the sub-array. Typically, the first approach that springs to mind is to add up all possible subarrays and return the one with the highest amount.

 Check out our articles in Library. You may also CheckOut our course on the array.

Recommended problems -

 

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Ninja, have a great time learning.

Previous article
The K Weakest Rows in a Matrix
Next article
Find All Pairs (a, b) In An Array Such That a % b = k
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass