Subarray Sum Equals K

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

For example:

Input: nums = [1,1,1], k = 2 Output: 2

Input: nums = [1,2,3], k = 3 Output: 2

Explain two different approaches to solve this problem. One should be a brute force solution and the other should be an optimized solution. Include code for each implementation. Analyze the time and space complexity of each approach and describe some edge cases to consider.

# Subarray Sum Equals K

## Problem Description

Given an array of integers `nums` and an integer `k`, the task is to find the total number of subarrays whose sum equals `k`. A subarray is a contiguous non-empty sequence of elements within the array.

**Example 1:**

Input: nums = [1,1,1], k = 2 Output: 2

**Example 2:**

Input: nums = [1,2,3], k = 3 Output: 2

## Brute Force Solution

A naive approach would be to consider all possible subarrays and check if their sum equals `k`.  This involves two nested loops to generate all subarrays and an inner loop (or sum function) to calculate the sum of each subarray.

```python
def subarray_sum_brute_force(nums, k):
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i, n):
            subarray_sum = 0
            for l in range(i, j + 1):
                subarray_sum += nums[l]
            if subarray_sum == k:
                count += 1
    return count

Optimal Solution: Using Prefix Sum and Hash Map

An efficient solution uses a hash map to store the cumulative sum up to each index and its frequency. For each index i, we calculate the cumulative sum current_sum. We then check if current_sum - k exists in the hash map. If it does, it means there is a subarray ending at index i with a sum equal to k. We increment the count by the frequency of current_sum - k in the hash map.

def subarray_sum_optimal(nums, k):
    count = 0
    current_sum = 0
    sum_map = {0: 1}
    
    for num in nums:
        current_sum += num
        if current_sum - k in sum_map:
            count += sum_map[current_sum - k]
        
        if current_sum in sum_map:
            sum_map[current_sum] += 1
        else:
            sum_map[current_sum] = 1
            
    return count

Big(O) Time Complexity Analysis

Brute Force

The brute force solution has a time complexity of O(n^3), where n is the length of the input array nums. The outer two loops iterate through all possible subarrays (O(n^2)), and the inner loop calculates the sum of each subarray (O(n)).

Optimal Solution

The optimal solution has a time complexity of O(n), where n is the length of the input array nums. We iterate through the array once to calculate the cumulative sum and update the hash map. Hash map operations (get and put) take O(1) time on average.

Big(O) Space Complexity Analysis

Brute Force

The brute force solution has a space complexity of O(1), as it uses a constant amount of extra space.

Optimal Solution

The optimal solution has a space complexity of O(n), where n is the length of the input array nums. In the worst case, the hash map sum_map may store all cumulative sums up to each index.

Edge Cases

1. Empty Array: If the input array nums is empty, the number of subarrays with sum k is 0. The provided solutions handle this case correctly as the loops won't execute.
2. Array with Zeroes: If the array contains zeroes, it can affect the cumulative sums. The hash map correctly handles multiple occurrences of the same cumulative sum.
3. Negative Numbers: The presence of negative numbers in the array is correctly handled by both solutions.
4. Large Input: For very large input arrays, the optimal solution is preferred due to its linear time complexity.
5. k = 0: The case where k is zero means we want to find the number of subarrays that sum up to zero. The hash map approach gracefully handles this case.

# Example Usage
nums1 = [1, 1, 1]
k1 = 2
print(f"Input: nums = {nums1}, k = {k1}")
print(f"Brute Force Output: {subarray_sum_brute_force(nums1, k1)}")
print(f"Optimal Output: {subarray_sum_optimal(nums1, k1)}")

nums2 = [1, 2, 3]
k2 = 3
print(f"\nInput: nums = {nums2}, k = {k2}")
print(f"Brute Force Output: {subarray_sum_brute_force(nums2, k2)}")
print(f"Optimal Output: {subarray_sum_optimal(nums2, k2)}")

nums3 = [1, -1, 0]
k3 = 0
print(f"\nInput: nums = {nums3}, k = {k3}")
print(f"Brute Force Output: {subarray_sum_brute_force(nums3, k3)}")
print(f"Optimal Output: {subarray_sum_optimal(nums3, k3)}")