Find Length of Largest Subarray with 0 Sum

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.

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.

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.

#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;
}

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int maxLenZeroSumSubarray(vector<int>& arr) {
    unordered_map<int, int> prefixMap;
    int prefixSum = 0, maxLen = 0;
    for (int i = 0; i < arr.size(); i++) {
        prefixSum += arr[i];
        if (prefixSum == 0) {
            maxLen = i + 1;
        } else if (prefixMap.count(prefixSum)) {
            maxLen = max(maxLen, i - prefixMap[prefixSum]);
        } else {
            prefixMap[prefixSum] = i;
        }
    }
    return maxLen;
}

int main() {
    vector<int> arr = {15, -2, 2, -8, 1, 7, 10, 23};
    cout << "Length of Largest Subarray with 0 Sum: " << maxLenZeroSumSubarray(arr) << endl;
    return 0;
}

def max_len_zero_sum_subarray(arr):
    prefix_sum = 0
    max_len = 0
    prefix_map = {}
    for i, num in enumerate(arr):
        prefix_sum += num
        if prefix_sum == 0:
            max_len = i + 1
        elif prefix_sum in prefix_map:
            max_len = max(max_len, i - prefix_map[prefix_sum])
        else:
            prefix_map[prefix_sum] = i
    return max_len

arr = [15, -2, 2, -8, 1, 7, 10, 23]
print("Length of Largest Subarray with 0 Sum:", max_len_zero_sum_subarray(arr))

import java.util.HashMap;

public class LargestZeroSumSubarray {
    public static int maxLenZeroSumSubarray(int[] arr) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int prefixSum = 0, maxLen = 0;
        for (int i = 0; i < arr.length; i++) {
            prefixSum += arr[i];
            if (prefixSum == 0) {
                maxLen = i + 1;
            } else if (map.containsKey(prefixSum)) {
                maxLen = Math.max(maxLen, i - map.get(prefixSum));
            } else {
                map.put(prefixSum, i);
            }
        }
        return maxLen;
    }
    public static void main(String[] args) {
        int[] arr = {15, -2, 2, -8, 1, 7, 10, 23};
        System.out.println("Length of Largest Subarray with 0 Sum: " + maxLenZeroSumSubarray(arr));
    }
}

function maxLenZeroSumSubarray(arr) {
    let prefixSum = 0;
    let maxLen = 0;
    let prefixMap = new Map();
    for (let i = 0; i < arr.length; i++) {
        prefixSum += arr[i];
        if (prefixSum === 0) {
            maxLen = i + 1;
        } else if (prefixMap.has(prefixSum)) {
            maxLen = Math.max(maxLen, i - prefixMap.get(prefixSum));
        } else {
            prefixMap.set(prefixSum, i);
        }
    }
    return maxLen;
}

const arr = [15, -2, 2, -8, 1, 7, 10, 23];
console.log("Length of Largest Subarray with 0 Sum:", maxLenZeroSumSubarray(arr));

package main

import (
    "fmt"
)

func maxLenZeroSumSubarray(arr []int) int {
    prefixSum := 0
    maxLen := 0
    prefixMap := make(map[int]int)
    for i, num := range arr {
        prefixSum += num
        if prefixSum == 0 {
            maxLen = i + 1
        } else if idx, found := prefixMap[prefixSum]; found {
            if i - idx > maxLen {
                maxLen = i - idx
            }
        } else {
            prefixMap[prefixSum] = i
        }
    }
    return maxLen
}

func main() {
    arr := []int{15, -2, 2, -8, 1, 7, 10, 23}
    fmt.Println("Length of Largest Subarray with 0 Sum:", maxLenZeroSumSubarray(arr))
}

use std::collections::HashMap;

fn max_len_zero_sum_subarray(arr: &[i32]) -> usize {
    let mut prefix_sum = 0;
    let mut max_len = 0;
    let mut prefix_map = HashMap::new();
    for (i, &num) in arr.iter().enumerate() {
        prefix_sum += num;
        if prefix_sum == 0 {
            max_len = i + 1;
        } else if let Some(&prev_index) = prefix_map.get(&prefix_sum) {
            max_len = max_len.max(i - prev_index);
        } else {
            prefix_map.insert(prefix_sum, i);
        }
    }
    max_len
}

fn main() {
    let arr = vec![15, -2, 2, -8, 1, 7, 10, 23];
    println!("Length of Largest Subarray with 0 Sum: {}", max_len_zero_sum_subarray(&arr));
}

fun maxLenZeroSumSubarray(arr: IntArray): Int {
    var prefixSum = 0
    var maxLen = 0
    val prefixMap = mutableMapOf<Int, Int>()
    for (i in arr.indices) {
        prefixSum += arr[i]
        if (prefixSum == 0) {
            maxLen = i + 1
        } else if (prefixMap.containsKey(prefixSum)) {
            maxLen = maxOf(maxLen, i - prefixMap[prefixSum]!!)
        } else {
            prefixMap[prefixSum] = i
        }
    }
    return maxLen
}

fun main() {
    val arr = intArrayOf(15, -2, 2, -8, 1, 7, 10, 23)
    println("Length of Largest Subarray with 0 Sum: ${maxLenZeroSumSubarray(arr)}")
}

func maxLenZeroSumSubarray(_ arr: [Int]) -> Int {
    var prefixSum = 0
    var maxLen = 0
    var prefixMap = [Int: Int]()
    for (i, num) in arr.enumerated() {
        prefixSum += num
        if prefixSum == 0 {
            maxLen = i + 1
        } else if let prevIndex = prefixMap[prefixSum] {
            maxLen = max(maxLen, i - prevIndex)
        } else {
            prefixMap[prefixSum] = i
        }
    }
    return maxLen
}

let arr = [15, -2, 2, -8, 1, 7, 10, 23]
print("Length of Largest Subarray with 0 Sum:", maxLenZeroSumSubarray(arr))

function maxLenZeroSumSubarray(arr: number[]): number {
    let prefixSum = 0;
    let maxLen = 0;
    const prefixMap = new Map<number, number>();
    for (let i = 0; i < arr.length; i++) {
        prefixSum += arr[i];
        if (prefixSum === 0) {
            maxLen = i + 1;
        } else if (prefixMap.has(prefixSum)) {
            maxLen = Math.max(maxLen, i - prefixMap.get(prefixSum)!);
        } else {
            prefixMap.set(prefixSum, i);
        }
    }
    return maxLen;
}

const arr: number[] = [15, -2, 2, -8, 1, 7, 10, 23];
console.log("Length of Largest Subarray with 0 Sum:", maxLenZeroSumSubarray(arr));

Time complexity

Space complexity

O(n)

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