Count contiguous subarrays summing to k
Filed under Flipkart
Free read 2 of 3Confirm whether elements can be negative (ruling out standard sliding window).
The question
Given an array of integers and an integer k, return the total number of continuous subarrays whose sum equals to k.
Constraints
- Array elements can be positive, negative, or zero
- Time complexity should ideally be O(n)
Examples
- Input
- nums = [1, 1, 1], k = 2
- Output
- 2
- Why
- Subarrays [1, 1] (indices 0-1 and 1-2) sum to 2.
Approach
Confirm whether elements can be negative (ruling out standard sliding window).
Check all possible subarrays with nested loops in O(n^2) or O(n^3) time.
Use prefix sums combined with a hash map. Maintain running prefix sums and count how many times (prefix_sum - k) has occurred previously.
Array with single elements matching k, or zero sums.
Solution
O(n) time, O(n) space
def subarraySum(nums: list[int], k: int) -> int:
count = 0
curr_sum = 0
prefix_sums = {0: 1}
for num in nums:
curr_sum += num
if curr_sum - k in prefix_sums:
count += prefix_sums[curr_sum - k]
prefix_sums[curr_sum] = prefix_sums.get(curr_sum, 0) + 1
return count
Tips
- What they are testing: Test with arrays containing negative numbers and zeros.
- Common mistake: Using a sliding window approach when the array contains negative numbers, which breaks monotonicity.
Related Flipkart questions
Collected from public candidate posts and coding forums. Updated Nov 2026.