Search⌘ K

Solution Review: A Subarray with a Sum of 0

Explore how to identify subarrays that sum to zero using iterative hashing in C#. Learn the use of hash tables to check conditions that confirm zero sum subarrays, improving code efficiency with O(n) time complexity methods relevant for coding interviews.

We'll cover the following...

Solution: Iterative hashing

C#
using System;
using System.Collections.Generic;
namespace chapter_9
{
class challenge_6
{
static bool findSubZero(int [] arr, int size)
{
//Use hMap to store Sum as key and index i as value till sum has been calculated.
//Traverse the array and return true if either
//arr[i] == 0 or sum == 0 or hMap already contains the sum
//If you completely traverse the array and haven't found any of the above three
//conditions then simply return false.
Dictionary<int, int> hMap = new Dictionary<int, int>();
int sum = 0;
// Traverse through the given array
for (int i = 0; i < size; i++)
{
sum += arr[i];
if ((arr[i] == 0) || (sum == 0) || (hMap.ContainsKey(sum)))
return true;
hMap[sum] = i;
}
return false;
}
static void Main(string[] args)
{
int []arr = { 6, 4, -7, 3, 12, 9 };
Console.WriteLine( findSubZero(arr, 6));
return;
}
}
}

The naive solution would be to iterate the array in a nested loop, summing each element with all the elements ...