How to Solve Subarray With Given Sum on LeetCode
The Subarray With Given Sum problem (also known as subarray sum equals k) is a common LeetCode question that evaluates your array, hashing, and prefix sum abilities.
Problem Statement
Given an array of integers and an integer k, find the total number of continuous subarrays whose sum equals to k.
Example:
Input: nums = [1,1,1], k = 2
Output: 2
Why This Problem Matters for Interviews
This problem:
- Tests prefix sum technique and hash map mastery
- Checks for brute force vs optimal solutions
- Builds a foundation for advanced array algorithms
Approaches to Subarray With Given Sum
1. Brute Force
Check every subarray’s sum.
Time Complexity: O(n^2)
def subarraySum(nums: list[int], k: int) -> int:
count = 0
for i in range(len(nums)):
sum_ = 0
for j in range(i, len(nums)):
sum_ += nums[j]
if sum_ == k:
count += 1
return count
2. Prefix Sum + Hash Map (Optimal)
Track cumulative sums and their frequencies in a hash map.
Time Complexity: O(n)
Space Complexity: O(n)
def subarraySum(nums: list[int], k: int) -> int:
count = curr = 0
pre_sum = {0: 1}
for n in nums:
curr += n
count += pre_sum.get(curr - k, 0)
pre_sum[curr] = pre_sum.get(curr, 0) + 1
return count
Key Interview Talking Points
- The idea behind prefix sum and hash map
- Why brute force is not scalable
- Handling negative numbers and zero in subarrays
- Discuss sliding window for all-positive inputs
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force | O(n^2) | O(1) |
| Prefix Sum + HashMap | O(n) | O(n) |
Pro Interview Tips
- Explain frequency counting with hash map.
- Walk through prefix sum logic step-by-step.
- Practice with test cases