Largest Subarray with 0 Sum – GeeksforGeeks Solution Explained

Are you stuck on the “Largest subarray with 0 sum” problem from GeeksforGeeks? Don’t worry! In this blog, we’ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with comments, dry runs, and clear explanations.

Here’s the [Problem Link] to begin with.

What Does the Problem Say?

You are given an array of integers. Your task is to find the length of the largest subarray (continuous part of the array) whose elements sum up to 0.

Example 1

Input:
arr = [15, -2, 2, -8, 1, 7, 10, 23]

Output:
5

Explanation:
The largest subarray with sum 0 is [-2, 2, -8, 1, 7] (from index 1 to 5).

Example 2

Input:
arr = [1]

Output:
0

Explanation:
There is no subarray with sum 0.

Brute Force Solution

Intuition and Approach

Let’s solve the problem step by step in the simplest way:

1. Try Every Subarray:
   For every possible starting index, check every possible ending index and calculate the sum of the subarray from start to end.
2. Check for Zero Sum:
   If the sum is zero, update the maximum length found so far.
3. Why does this work?
   We are checking every possible subarray, so we won’t miss any that sum to zero.

This approach is easy to understand but not efficient for large arrays.

Code Implementation

class Solution:
    def maxLen(self, n, arr):
        max_length = 0
        n = len(arr)
        for i in range(n):
            sum = 0
            for j in range(i, n):
                sum += arr[j]  # Add current element to sum
                if sum == 0:
                    max_length = max(max_length, j - i + 1)  # Update max_length if sum is zero
        return max_length

Code Explanation

• We use two loops: the outer loop picks the start index, and the inner loop picks the end index.
• For each subarray, we calculate the sum.
• If the sum is zero, we check if the length is the largest found so far.

Dry Run

Input:
arr = [15, -2, 2, -8, 1, 7, 10, 23]

• Start at index 0:
  • Sum from 0 to 0: 15 (not zero)
  • Sum from 0 to 1: 13 (not zero)
  • …
• Start at index 1:
  • Sum from 1 to 1: -2 (not zero)
  • Sum from 1 to 2: 0 → length = 2
  • Sum from 1 to 5: 0 → length = 5 (update max_length)
• Continue for all start indices.

Final Output:
max_length = 5

Time and Space Complexity

• Time Complexity: O(N^2)
  Two nested loops for all subarrays.
• Space Complexity: O(1)
  Only a few variables are used.

Conclusion

The brute force approach is very simple and good for understanding, but it’s too slow for large arrays.

Optimal Solution

Intuition and Approach

We can solve this problem much faster using a hash map (dictionary):

1. Use Prefix Sums:
   As we go through the array, keep track of the sum of elements from the start to the current index (prefix sum).
2. Store Sums in a Map:
   If the same prefix sum appears again, it means the elements between the two indices sum to 0.
3. Check for Zero Sum:
   • If the prefix sum is zero at any index, the subarray from the start to that index sums to zero.
   • If we have seen the prefix sum before, the subarray between the previous index and the current index sums to zero.

Why does this work?
If the sum from index 0 to i is S, and the sum from 0 to j is also S, then the sum from i+1 to j must be zero.

Code Implementation

class Solution:
    def maxLen(self, n, arr):
        n = len(arr)
        prefix_sum = {}  # Dictionary to store first occurrence of each prefix sum
        maxi = 0  # To keep track of maximum length found
        sum = 0  # To store the current prefix sum
        for i in range(n):
            sum += arr[i]  # Update prefix sum
            if sum == 0:
                maxi = i + 1  # If prefix sum is zero, update maxi
            else:
                if sum in prefix_sum:
                    maxi = max(maxi, i - prefix_sum[sum])  # Update maxi if sum seen before
                else:
                    prefix_sum[sum] = i  # Store first occurrence of this sum
        return maxi

Code Explanation

• We keep a running sum (sum) as we go through the array.
• If sum is zero, it means the subarray from the start to the current index sums to zero.
• We use a dictionary (prefix_sum) to store the first index where each sum occurs.
• If we see the same sum again, the subarray between the previous index and the current index sums to zero.
• We update the maximum length whenever we find a longer subarray.

Dry Run

Input:
arr = [15, -2, 2, -8, 1, 7, 10, 23]

• i = 0: sum = 15, store 15:0
• i = 1: sum = 13, store 13:1
• i = 2: sum = 15, seen before at 0 → length = 2 (update maxi)
• i = 3: sum = 7, store 7:3
• i = 4: sum = 8, store 8:4
• i = 5: sum = 15, seen before at 0 → length = 5 (update maxi)
• Continue for all indices.

Final Output:
maxi = 5

Time and Space Complexity

• Time Complexity: O(N)
  Only one pass through the array.
• Space Complexity: O(N)
  For storing prefix sums in the dictionary.

Conclusion

The optimal solution is fast and efficient. It uses a hash map to keep track of prefix sums and finds the answer in a single pass.

Final Thoughts

The “Largest subarray with 0 sum” problem is a great example of how to improve your solution from brute force to optimal. Start with the simple approach to build understanding, then use prefix sums and hashing for the best performance.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.