Subarray Sum Equals K Solution for TCS NQT
Company: TCS NQT · Difficulty: Medium · Topics: Array, Hash Table, Prefix Sum
Problem Statement
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.
Examples
Example 1:
Input: nums = [1,1,1], k = 2
Output: 2
Explanation:
- Subarray [1,1] starting at index 0: sum = 1+1 = 2
- Subarray [1,1] starting at index 1: sum = 1+1 = 2
Example 2:
Input: nums = [1,2,3], k = 3
Output: 2
Explanation:
- Subarray [1,2] starting at index 0: sum = 1+2 = 3
- Subarray [3] starting at index 2: sum = 3
Example 3:
Input: nums = [1,-1,0], k = 0
Output: 3
Explanation:
- Subarray [1,-1] starting at index 0: sum = 1+(-1) = 0
- Subarray [0] starting at index 2: sum = 0
- Subarray [-1,0] starting at index 1: sum = (-1)+0 = -1 (not equal to k)
Example 4:
Input: nums = [3,4,7,2,-3,1,4,2], k = 7
Output: 4
Explanation:
- Subarray [3,4] starting at index 0: sum = 3+4 = 7
- Subarray [7] starting at index 2: sum = 7
- Subarray [2,-3,1,4,2] starting at index 3: sum = 2+(-3)+1+4+2 = 6 (not equal to k)
- Subarray [4,2] starting at index 6: sum = 4+2 = 6 (not equal to k)
Intuition
The key insight is to use prefix sums and a hash table. If we have a prefix sum at index i and another prefix sum at index j (where j > i), then the sum of the subarray from index i+1 to j is prefixSum[j] - prefixSum[i].
If we want this sum to equal k, then: prefixSum[j] - prefixSum[i] = k, which means prefixSum[i] = prefixSum[j] - k.
Approach
Approach 1: Prefix Sum with Hash Table (Optimal)
1. Use a hash table to store prefix sums and their frequencies
2. Initialize with prefixSum[0] = 0 and count = 1
3. For each element, calculate the current prefix sum
4. Check if (currentPrefixSum - k) exists in the hash table
5. Add the frequency of (currentPrefixSum - k) to the result
6. Update the hash table with the current prefix sum
Approach 2: Brute Force with Prefix Sums
1. Calculate all prefix sums
2. For each pair of indices (i, j), check if prefixSum[j] - prefixSum[i] == k
3. Count all such pairs
Approach 3: Brute Force
1. For each starting index, calculate the sum of all possible subarrays
2. Count subarrays with sum equal to k
Dry Run
Let's trace through Example 1: nums = [1,1,1], k = 2
Prefix Sum with Hash Table:
Initial: hash = {0: 1}, count = 0, prefixSum = 0
Step 1: i=0, nums[0]=1
- prefixSum = 0 + 1 = 1
- Check if (1 - 2) = -1 exists in hash: No
- Add 1 to hash: hash = {0: 1, 1: 1}
- count = 0
Step 2: i=1, nums[1]=1
- prefixSum = 1 + 1 = 2
- Check if (2 - 2) = 0 exists in hash: Yes, frequency = 1
- Add 1 to count: count = 1
- Add 2 to hash: hash = {0: 1, 1: 1, 2: 1}
- count = 1
Step 3: i=2, nums[2]=1
- prefixSum = 2 + 1 = 3
- Check if (3 - 2) = 1 exists in hash: Yes, frequency = 1
- Add 1 to count: count = 2
- Add 3 to hash: hash = {0: 1, 1: 1, 2: 1, 3: 1}
- count = 2
Result: 2
Brute Force:
All possible subarrays:
- [1]: sum = 1 ≠ 2
- [1,1]: sum = 2 ✓
- [1,1,1]: sum = 3 ≠ 2
- [1]: sum = 1 ≠ 2
- [1,1]: sum = 2 ✓
- [1]: sum = 1 ≠ 2
Result: 2
Key Insights
1. Prefix Sum Property: sum[i,j] = prefixSum[j] - prefixSum[i-1]
2. Hash Table Lookup: Use hash table for O(1) lookup of previous prefix sums
3. Target Calculation: If sum[i,j] = k, then prefixSum[i-1] = prefixSum[j] - k
4. Frequency Counting: Count all occurrences, not just existence
Edge Cases
1. Empty array: Return 0
2. Single element: Check if it equals k
3. All negative numbers: Handle negative prefix sums
4. Multiple occurrences: Count all valid subarrays
5. k = 0: Handle case where target sum is zero
Time and Space Complexity
- Time Complexity: O(n) - Single pass through the array
- Space Complexity: O(n) - Hash table to store prefix sums