DSA 450 Notes

Problem Statement

Given an array of integers, determine if there exists a subarray (contiguous elements) whose sum equals zero.

Example:

Input: [4, 2, -3, 1, 6]
Output: true
Explanation: Subarray [2, -3, 1] has sum = 0

Approach 1: Brute Force

Intuition

Check all possible subarrays and calculate their sums. If any sum equals zero, return true.

Algorithm

For each starting index i
For each ending index j >= i
Calculate sum of subarray [i, j]
If sum is 0, return true

java

public class Solution {
    public boolean hasZeroSumSubarrayBruteForce(int[] arr) {
        int n = arr.length;
        
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += arr[j];
                if (sum == 0) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    // Also return the subarray indices
    public int[] findZeroSumSubarray(int[] arr) {
        int n = arr.length;
        
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += arr[j];
                if (sum == 0) {
                    return new int[]{i, j};  // Return start and end indices
                }
            }
        }
        
        return new int[]{-1, -1};  // No subarray found
    }
}

Complexity Analysis

Time Complexity: O(n²) - Checking all subarrays
Space Complexity: O(1) - No extra space used

Approach 2: Using Prefix Sum + HashSet (Optimal)

Intuition

If the prefix sum at index i equals the prefix sum at index j (where j > i), then the subarray [i+1, j] has sum = 0. Also, if any prefix sum is 0, then subarray [0, i] has sum = 0.

Algorithm

Compute prefix sums while traversing
If prefix sum becomes 0, we found a zero-sum subarray
If prefix sum was seen before, we found a zero-sum subarray
Store each prefix sum in a HashSet

java

import java.util.*;

public class Solution {
    public boolean hasZeroSumSubarray(int[] arr) {
        Set<Integer> prefixSums = new HashSet<>();
        int sum = 0;
        
        for (int num : arr) {
            sum += num;
            
            // Case 1: Prefix sum is 0 (subarray from start)
            if (sum == 0) {
                return true;
            }
            
            // Case 2: Same prefix sum seen before
            if (prefixSums.contains(sum)) {
                return true;
            }
            
            prefixSums.add(sum);
        }
        
        return false;
    }
    
    // Return the subarray with sum 0
    public int[] findZeroSumSubarray(int[] arr) {
        Map<Integer, Integer> prefixSumIndex = new HashMap<>();
        int sum = 0;
        
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            
            // Case 1: Prefix sum is 0
            if (sum == 0) {
                return new int[]{0, i};
            }
            
            // Case 2: Same prefix sum seen before
            if (prefixSumIndex.containsKey(sum)) {
                return new int[]{prefixSumIndex.get(sum) + 1, i};
            }
            
            prefixSumIndex.put(sum, i);
        }
        
        return new int[]{-1, -1};
    }
}

Complexity Analysis

Time Complexity: O(n) - Single pass with O(1) lookups
Space Complexity: O(n) - HashSet to store prefix sums

Visual Example

For array [4, 2, -3, 1, 6]:

Index:     0    1    2    3    4
Array:     4    2   -3    1    6

Prefix sums:
Index 0: sum = 4
  Not 0, not seen before, add to set: {4}

Index 1: sum = 4 + 2 = 6
  Not 0, not seen before, add to set: {4, 6}

Index 2: sum = 6 + (-3) = 3
  Not 0, not seen before, add to set: {4, 6, 3}

Index 3: sum = 3 + 1 = 4
  Not 0, but 4 is already in set!
  Subarray from (index of 4) + 1 to current index
  = index 1 to 3 = [2, -3, 1]
  
Result: true (zero-sum subarray exists)

Extension: Find All Zero-Sum Subarrays

Key Takeaways

Prefix sum technique transforms the problem: zero-sum subarray ↔ repeated prefix sum
If prefixSum[j] == prefixSum[i], then sum(arr[i+1...j]) = 0
HashSet for existence check, HashMap for finding indices
Always check if prefix sum itself is 0 (subarray from start)
This technique extends to "subarray with sum K" problems
Applications: Finding subarrays with given sum, counting subarrays with sum K

Find if there is any subarray with sum equal to 0

Problem Statement

Approach 1: Brute Force

Intuition

Algorithm

Complexity Analysis

Approach 2: Using Prefix Sum + HashSet (Optimal)

Intuition

Algorithm

Complexity Analysis

Visual Example

Extension: Find All Zero-Sum Subarrays

Key Takeaways