560.Subarray Sum Equals K

📘 LeetCode 560: Subarray Sum Equals K

📌 Problem Overview

• Problem Number: 560
• Problem Name: Subarray Sum Equals K
• Difficulty: Medium
• Category: Arrays and Hashing
• Runnable Source: Program.cs

---

💡 Algorithmic Approach & Pattern

This problem is solved using the Arrays and Hashing algorithmic pattern.

Key Insights & Invariants:

1. Identify the input constraints and edge conditions.
2. Structure the data flow to minimize unnecessary traversals and heap reallocations.
3. Validate corner cases (empty collections, single-element cases, duplicates, extremes).

---

💻 Verified C# Implementation (.NET 9)

The solution is verified and executable via the companion project in src/560.Subarray-Sum-Equals-K/:

// LeetCode 560: Subarray Sum Equals K
// Pattern: Prefix Sum + HashMap Counting
// Time Complexity: O(N)
// Space Complexity: O(N)
 
int SubarraySum(int[] nums, int k)
{
    int count = 0;
    int currentPrefixSum = 0;
 
    // Key: prefix sum value, Value: frequency count
    var prefixSumCounts = new Dictionary<int, int>
    {
        { 0, 1 } // Base case: a prefix sum of 0 has occurred once before reading any elements
    };
 
    foreach (int num in nums)
    {
        currentPrefixSum += num;
 
        // Check if prefixSum[j] - k exists in dictionary
        int neededPrefixSum = currentPrefixSum - k;
        if (prefixSumCounts.TryGetValue(neededPrefixSum, out int frequency))
        {
            count += frequency;
        }
 
        // Record/increment currentPrefixSum frequency
        prefixSumCounts[currentPrefixSum] = prefixSumCounts.GetValueOrDefault(currentPrefixSum, 0) + 1;
    }
 
    return count;
}
 
// Test Verification
Console.WriteLine($"Test 1: [1, 1, 1], k = 2 -> Expected: 2, Got: {SubarraySum([1, 1, 1], 2)}");
Console.WriteLine($"Test 2: [1, 2, 3], k = 3 -> Expected: 2, Got: {SubarraySum([1, 2, 3], 3)}");
Console.WriteLine($"Test 3: [1, -1, 0], k = 0 -> Expected: 3, Got: {SubarraySum([1, -1, 0], 0)}");
Console.WriteLine($"Test 4: [3, 4, 7, 2, -3, 1, 4, 2], k = 7 -> Expected: 4, Got: {SubarraySum([3, 4, 7, 2, -3, 1, 4, 2], 7)}");

---

📊 Complexity Analysis

Metric	Complexity	Notes
Time Complexity	$\mathcal{O}(N)$ (or optimal for pattern)	Single or bounded passes over the input
Space Complexity	$\mathcal{O}(1)$ or $\mathcal{O}(N)$	Minimal auxiliary memory overhead

---

🚨 Edge Cases & Interview Traps

• Empty / Null Input: Ensure null safety and guard clauses.
• Single Element: Confirm the algorithm terminates without out-of-bounds indexing.
• Duplicates & Boundaries: Check duplicate handling and extreme integer limits.