Johnnn

Let's go

Find largest subarray with sum 0 in an array, algorithm and time complexity, with example in C,C++,Python and java

by · Published · Updated

One common problem in programming is finding the largest subarray with a sum of 0 within a given array. In this blog post, we will explore an algorithm that efficiently solves this problem. Additionally, we will provide code examples in four popular programming languages: C, C++, Python, and Java.

Algorithm:
The algorithm we will discuss to find the largest subarray with a sum of 0 is based on the concept of a cumulative sum array and hashing. It involves creating a cumulative sum array where each element represents the sum of all elements from the beginning of the array up to that index. We iterate through the cumulative sum array and store the index of the first occurrence of each sum in a hash table. If we encounter a sum that already exists in the hash table, it means there is a subarray with a sum of 0. We calculate the length of this subarray and keep track of the maximum length encountered so far.

Time Complexity:
The time complexity of this algorithm is O(n), where n is the size of the array. The algorithm performs a single pass through the array, and each element is visited only once. The hash table operations also take constant time on average.

Code Examples:

  1. C:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int findLargestSubarrayWithSumZero(int arr[], int n) {
    int maxLen = 0;
    int sum = 0;
    int lastIndex = -1;

    // Create a hash table to store the sum and its corresponding index
    int* hashTable = (int*)calloc(2 * n + 1, sizeof(int));

    for (int i = 0; i < n; i++) {
        sum += arr[i];

        // If the current sum is 0, update the maximum length
        if (sum == 0)
            maxLen = i + 1;

        // If the current sum has been seen before, update the maximum length
        if (hashTable[sum + n] != 0)
            maxLen = (i - hashTable[sum + n] > maxLen) ? i - hashTable[sum + n] : maxLen;
        else
            hashTable[sum + n] = i;
    }

    free(hashTable);

    return maxLen;
}

int main() {
    int arr[] = {15, -2, 2, -8, 1, 7, 10, 23};
    int n = sizeof(arr) / sizeof(arr[0]);

    int largestSubarrayLength = findLargestSubarrayWithSumZero(arr, n);

    printf("The length of the largest subarray with sum 0 is: %dn", largestSubarrayLength);

    return 0;
}
  1. C++:
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

int findLargestSubarrayWithSumZero(vector<int>& arr) {
    int maxLen = 0;
    int sum = 0;
    int lastIndex = -1;

    unordered_map<int, int> hashTable;

    for (int i = 0; i < arr.size(); i++) {
        sum += arr[i];

        if (sum == 0)
            maxLen = i + 1;

        if (hashTable.find(sum) != hashTable.end())
            maxLen = max(maxLen, i - hashTable[sum]);
        else
            hashTable[sum] = i;
    }

    return maxLen;
}

int main() {
    vector<int> arr = {15, -2, 2, -8, 1, 7, 10, 23};

    int largestSubarrayLength = findLargestSubarrayWithSumZero(arr);

    cout << "The length of the largest subarray with sum 0 is: " << largestSubarrayLength << endl;

    return 0;
}
  1. Python:
def find_largest_subarray_with_sum_zero(arr):
    max_len = 0
    sum = 0
    hash_table = {}

    for i in range(len(arr)):
        sum += arr[i]

        if sum == 0:
            max_len = i + 1

        if sum in hash_table:
            max_len = max(max_len, i - hash_table[sum])
        else:
            hash_table[sum] = i

    return max_len

arr = [15, -2, 2, -8, 1, 7, 10, 23]
largest_subarray_length = find_largest_subarray_with_sum_zero(arr)
print("The length of the largest subarray with sum 0 is:", largest_subarray_length)
  1. Java:
import java.util.HashMap;

class Main {
    static int findLargestSubarrayWithSumZero(int[] arr) {
        int maxLen = 0;
        int sum = 0;
        int lastIndex = -1;

        HashMap<Integer, Integer> hashMap = new HashMap<>();

        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];

            if (sum == 0)
                maxLen = i + 1;

            if (hashMap.containsKey(sum))
                maxLen = Math.max(maxLen, i - hashMap.get(sum));
            else
                hashMap.put(sum, i);
        }

        return maxLen;
    }

    public static void main(String[] args) {
        int[] arr = {15, -2, 2, -8, 1, 7, 10, 23};

        int largestSubarrayLength = findLargestSubarrayWithSumZero(arr);

        System.out.println("The length of the largest subarray with sum 0 is: " + largestSubarrayLength);
    }
}

Conclusion:
In this blog post, we explored an efficient algorithm for finding the largest subarray with a sum of 0 in a given array. By utilizing a cumulative sum array and hashing, we were able to solve the problem in a single pass through the array. We provided code examples in C, C++, Python, and Java, along with step-by-step explanations of the algorithm. Next time you encounter a similar problem, you can confidently apply this algorithm as a solution. Happy coding!

You may also like...