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
-
Check the total of each sub-array as you take each one into consideration.
- 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
-
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.
-
From the beginning to the end of the input array, move.
-
Update the sum value at sum = sum + array[i] for each index.
-
To see if the current total is in the hash map, check each index.
-
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.
-
Otherwise, add the value (sum), with the index as a key-value pair, to the hash map.
- 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.
117+ registered 