Find Length of Largest Subarray with 0 Sum using Hash Map Optimal Solution

Arrays

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given an array of integers (which may contain both positive and negative numbers), your task is to find the length of the longest contiguous subarray whose elements sum up to 0.

  • The subarray must consist of consecutive elements.
  • The array may contain positive numbers, negative numbers, and zeros.
  • If no such subarray exists, return 0.

Examples❯

Input Array Output Description
[1, 2, -3, 3, -1, -2] 6 The entire array sums to 0
[15, -2, 2, -8, 1, 7, 10, 23] 5 Subarray [-2, 2, -8, 1, 7] has sum 0
[1, 2, 3] 0 No subarray has 0 sum
[0, 0, 0, 0] 4 All elements are 0, full array is valid
[4, -1, -3, 1, 2] 5 Entire array has sum 0
[1] 0 Single element not equal to 0
[0] 1 Single 0 is a valid subarray
[] 0 Empty array, no subarrays

Solution❯

Understanding the Problem

We are given an array of integers, and we need to find the longest subarray whose sum is exactly zero.

In simple terms, a subarray is a sequence of consecutive elements from the original array. We want to find the longest one such that all its elements add up to 0.

Why is this tricky?

We could try checking every possible subarray and summing its elements, but that would take too much time. So, we need a smarter way.

Our Step-by-Step Plan

Step 1: Use Prefix Sum

As we go through the array, we keep adding elements to a running total. This is called the prefix sum.

If the same prefix sum appears more than once, it means the elements between those two positions cancel each other out and sum to 0.

Step 2: Use a Hash Map

We use a hash map (or dictionary) to remember the first time we saw each prefix sum. This allows us to quickly calculate the length of any 0-sum subarray.

Let’s Understand with an Example

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

Prefix sums as we go:

  • Index 0 → 15
  • Index 1 → 13
  • Index 2 → 15 (again!) → Subarray from index 1 to 2 has sum 0
  • Index 3 → 7
  • Index 4 → 8
  • Index 5 → 15 (again!) → Subarray from index 1 to 5 has sum 0

Longest subarray so far is from index 1 to 5 → length = 5

Covering All Edge Cases

  • Case 1: Prefix sum becomes 0 at index i
    This means the subarray from index 0 to i itself has sum 0, so the length is i + 1.
  • Case 2: Prefix sum repeats
    If we saw the same prefix sum earlier, the subarray in between has sum 0.
  • Case 3: Prefix sum appears for the first time
    We store it in the map with the current index.
  • Case 4: No 0-sum subarray exists
    If prefix sums are always unique and never zero, the answer is 0.
  • Case 5: Entire array sums to 0
    If prefix sum is 0 at the last index, the entire array is the answer.
  • Case 6: All elements are 0
    Each prefix sum is 0, so longest subarray is the entire array.

By using prefix sums and a hash map, we don’t have to check every possible subarray. We just walk through the array once, keeping track of what we’ve seen. This gives us a very efficient O(n) solution that works even for large arrays.

Algorithm Steps❯

  1. Given an array arr of size n.
  2. Initialize an empty Hash Map to store prefix sums and their first occurrence index.
  3. Initialize variables: max_len = 0 and prefix_sum = 0.
  4. Traverse the array:
  5. → Add the current element to prefix_sum.
  6. → If prefix_sum == 0, update max_len = current index + 1.
  7. → If prefix_sum already exists in the map, update max_len as the maximum of current max_len and current index - first occurrence index.
  8. → Else, store prefix_sum with the current index in the map.
  9. Return max_len.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#define MAX 1000

int maxLenZeroSumSubarray(int arr[], int n) {
    int prefixSum = 0, maxLen = 0;
    int prefixMap[MAX];
    for (int i = 0; i < MAX; i++) prefixMap[i] = -1;

    for (int i = 0; i < n; i++) {
        prefixSum += arr[i];
        if (prefixSum == 0) {
            maxLen = i + 1;
        } else if (prefixMap[prefixSum + MAX / 2] != -1) {
            if (i - prefixMap[prefixSum + MAX / 2] > maxLen)
                maxLen = i - prefixMap[prefixSum + MAX / 2];
        } else {
            prefixMap[prefixSum + MAX / 2] = i;
        }
    }
    return maxLen;
}

int main() {
    int arr[] = {15, -2, 2, -8, 1, 7, 10, 23};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Length of Largest Subarray with 0 Sum: %d\n", maxLenZeroSumSubarray(arr, n));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)In the best case, we traverse the array once and find subarrays summing to 0 early, updating the maximum length efficiently.
Average CaseO(n)The algorithm runs in linear time by computing the prefix sum and checking/recording it in the hash map in constant time for each element.
Worst CaseO(n)Even in the worst case, we perform a single pass through the array, and all hash map operations (insertion, lookup) are constant time on average.

Space Complexity❯

O(n)

Explanation: In the worst case, all prefix sums may be unique, requiring storage of each sum and its index in the hash map.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...