One of the most frequent hurdles learners face is the subarray with given sum problem. At first glance. If the array contains negative numbers, the standard “sliding window” or “two-pointer” technique fails. Why? This is because adding an element could potentially decrease the total sum, while removing one could potentially increase it. To solve this issue, we need a better strategy using hashing.
What is a Subarray with Given Sum?
A sub array with given sum is a contiguous sequence of elements within an array that, when added together, exactly matches a specified target value. Unlike a subsequence, which allows for skipping elements, a subarray requires an uninterrupted block of data.
How Does Subarray Sum Equals K?
When we talk about a subarray sum equals k, we are looking for a continuous block of elements. For example, the subarray [2, -2, -20, 10] is a valid solution in the array [10, 2, -2, -20, 10] with a target sum of -10.
The Challenge of Negative Numbers
In a purely positive array, as you add elements, the sum only goes up. If the sum exceeds your target, you shrink the window from the left. But with negative numbers, the sum fluctuations are unpredictable. This is why the sub array with given sum problem is a perfect introduction to the power of prefix sums combined with Hash Maps.
Prefix Sum and Hashing Method in Subarray
To solve the problem, we use a simple mathematical logic. Suppose the sum of elements from index 0 to i is curr_sum. If there exists a subarray ending at i with sum k, then the prefix sum at some earlier index j must have been curr_sum – k.
Steps to implement the algorithm:
- Maintain a curr_sum variable as you iterate through the array.
- Use a Hash Map (or Dictionary) to store every curr_sum encountered so far.
- At every step, check if (curr_sum – target) exists in your map.
- If it does, the elements between that previous index and your current index form the subarray with the given sum.
Subarray with Given Sum Example
Let’s trace an example: Array = [3, 4, 7, 2, -3, 1], Target = 7
- Start: curr_sum = 0, Map = {0: -1} (to handle cases where the subarray starts from index 0).
- Index 0 (3): curr_sum = 3. Map = {0: -1, 3: 0}.
- Index 1 (4): curr_sum = 7. Check 7 – 7 = 0. Since 0 is in the map, we found a subarray from index 0 to 1.
- Index 2 (7): curr_sum = 14. Check 14 – 7 = 7. Since 7 is in the map (at index 1), the element at index 2 itself is a subarray!
This subarray with given sum example shows how the map helps us “look back” in time to find the exact point where the target sum was completed.
Subarray with Given Sum Code Implementations
Below are the code examples of subarray with a given sum across different languages:
Subarray with Given Sum in C++
Using std::unordered_map, we can achieve a time complexity of O(n).
#include <iostream>
#include <unordered_map>
#include <vector>
void findSubarray(std::vector<int> arr, int sum) {
std::unordered_map<int, int> map;
int curr_sum = 0;
for (int i = 0; i < arr.size(); i++) {
curr_sum += arr[i];
if (curr_sum == sum) {
std::cout << “Sum found between index 0 to “ << i << std::endl;
return;
}
if (map.find(curr_sum – sum) != map.end()) {
std::cout << “Sum found between index “ << map[curr_sum – sum] + 1 << ” to “ << i << std::endl;
return;
}
map[curr_sum] = i;
}
}
Subarray with Given Sum Python
In Python, dictionaries make this implementation incredibly concise.
def subarray_sum(arr, k):
prefix_sums = {0: –1}
curr_sum = 0
for i, val in enumerate(arr):
curr_sum += val
if (curr_sum – k) in prefix_sums:
return [prefix_sums[curr_sum – k] + 1, i]
prefix_sums[curr_sum] = i
return –1
Subarray with Given Sum Java
The subarray with given sum Java implementation uses the HashMap class to store prefix sums.
import java.util.*;
class Solution {
public void findSubarray(int[] arr, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
int curr_sum = 0;
for (int i = 0; i < arr.length; i++) {
curr_sum += arr[i];
if (curr_sum == k) {
System.out.println(“Found at 0 to “ + i);
return;
}
if (map.containsKey(curr_sum – k)) {
System.out.println(“Found at “ + (map.get(curr_sum – k) + 1) + ” to “ + i);
return;
}
map.put(curr_sum, i);
}
}
}
Subarray with Given Sum Comparison
Refer to the table given below for comparing the various Time and Space complexities:
| Metric | Complexity | Explanation |
| Time Complexity | O(n) | We traverse the array exactly once. Map lookups take O(1) on average. |
| Space Complexity | O(n) | In the worst case, we store every prefix sum in the hash map. |
While O(n) space is required, it is a necessary trade-off for handling negative integers where the O(1) space sliding window approach would fail.
FAQs
Q1: Can I use the sliding window technique if the array has zeros?
Yes, a sliding window works with zeros and positive numbers. However, if there are negative numbers, the window's sum doesn't change monotonically, which breaks the sliding window logic.
Q2: What happens if there are multiple subarrays with the same sum?
The hash map implementation usually returns the first one found. If you need to count all of them, you should store the frequency of each prefix sum in the map instead of just the index.
Q3: Why do we check for (curr_sum - sum) in the map?
If PrefixSum[i] - PrefixSum[j] = Target, then the sum of elements between j and i is exactly the target. Rearranging this gives us PrefixSum[j] = PrefixSum[i] - Target.
Q4: Is this the most optimal way for a subarray with the subarray with given sum java given sum in Java?
For arrays with negative numbers, yes. O(n) time and O(n) space is the industry standards for this specific variation.
Q5: What if the target sum is 0?
The logic remains the same. If curr_sum repeats (meaning curr_sum - 0 is found in the map), it indicates that the elements in between add up to zero.