Subarray Sum Hackerrank Solution

The Brute Force Trap Most People Fall Into

I ran into this problem early on when I was prepping for coding interviews. You get an array and a target sum, and you need to figure out if any contiguous subarray adds up to that number. The first instinct is to nest two loops, check every possible subarray, and see if the sum matches. It works for small inputs. For HackerRank's constraints, it fails within a second or two and leaves you staring at a timeout error. The trick isn't in math. It's in prefix sums and a hash map. I still see people write O(n squared) solutions at interviews and wonder why they don't pass.

Subarray Sum Hackerrank Solution

Here's the approach. Walk through the array once, keeping a running total of every element you've seen so far. At each position, check whether that running total minus the target sum already exists in a set of previously seen prefix sums. If it does, then a subarray between that earlier point and your current position adds up exactly to the target. The logic sounds abstract until you see it with actual numbers. Let me walk through it. Say the array is [1, 2, 3, 4, 5] and the target is 9. The prefix sums go like this: after the first element you have 1, after the second you have 3, then 6, then 10, then 15. When you reach 10, you check if 10 minus 9 equals 1. That value 1 was indeed seen before at the start. So the subarray from index 1 to index 3, which is [2, 3, 4], sums to 9. The algorithm catches it in a single pass.

The empty prefix sum, zero, has to exist in the map from the beginning. That's the part people forget. If the subarray starts right at index zero, you need that baseline to exist so the math works out correctly.

Implementation Details

In Python, the implementation is straightforward. Initialize a set containing zero, then iterate through the array while updating a running prefix sum. Check the condition at each step. In Java or C#, you'd use a HashSet instead. The time complexity is O(n) and the space complexity is also O(n) because of the set storage. I usually write it like this in Python: def subarraySum(nums, k):
prefix_sums = {0}
current_sum = 0
for num in nums:
current_sum += num
if current_sum - k in prefix_sums:
return True
prefix_sums.add(current_sum)
return False

For HackerRank specifically, the input format typically gives you the array on one line and the target sum on another. Read both, call the function, print the result. The platform expects either "Yes" or "No" in some variations, so check the exact output specification for the problem version you're solving. It's easy to waste points on a formatting mismatch when the logic itself is correct.

Edge Cases That Bite People

One case I consistently see trip up candidates: negative numbers in the array. The prefix sum approach still works with negatives, which surprises a lot of people. The sliding window method that works for arrays with only positive numbers falls apart here because removing an element from the left no longer guarantees a smaller sum. The hash map approach doesn't care whether values are positive, negative, or zero. It just tracks what it has seen. Another edge case is an empty array. If the input can be empty, return False immediately rather than letting the loop run over nothing and then returning False anyway. It saves a trivial amount of computation but signals that you considered it. Zero-length subarrays are technically valid in some variations of this problem, but HackerRank's version almost always requires at least one element. If you're not sure, read the problem statement twice. I once submitted a solution that treated the empty subarray as valid and got a partial failure on a hidden test case because my interpretation was off by one requirement.

Common Pitfalls

People often add the current prefix sum to the set before checking whether current_sum minus k exists. That's backwards. You need to check first, then add, otherwise you're comparing the current position against itself and getting a false positive on zero-length matches. Another mistake is initializing the set with the first prefix sum instead of with zero. If the entire array from index zero equals the target, you need that initial zero in the set to trigger the match correctly. A third one: using a list instead of a set for tracking seen prefix sums. A list makes the lookup O(n) again, which defeats the whole purpose and brings you back to O(n squared) performance. Sets give you O(1) average lookups in Python and Java. Use them.

When This Approach Fails

The hash map method is solid for the standard version of this problem, but it has limits. If the input array is enormous, say millions of elements, the set can grow large enough to cause memory pressure. In those cases, you're better off checking whether the problem constraints actually require an O(n) space solution or if there's a different angle, like sorting with a two-pointer technique, though that only works when negatives aren't present. Also, if you need to count the number of valid subarrays instead of just returning a yes or no, the logic changes slightly. You'd store frequency counts in a hashmap rather than a set, and accumulate the count as you go. That's a related but distinct problem, and the same interview platform often asks for it next. The Subarray Sum Hackerrank Solution is straightforward once you see the prefix sum pattern. It's one of those problems where the insight takes five minutes to understand but another five minutes to implement correctly because of the small details I mentioned above.