.png)
Subarray with Given Sum
Problem Statement
Given an array of integers and a target sum S, find a contiguous subarray whose elements add up to S.
You need to:
- Print the starting and ending indices
OR - Print the subarray itself (as per problem requirement)
If no such subarray exists, print "No subarray found".
Key Difference from Two Sum
| Two Sum | Subarray Sum |
|---|---|
| Elements can be anywhere | Elements must be continuous |
| Uses hashing directly | Uses sliding window / prefix sum |
| Pair of numbers | Range of numbers |
Example 1 (Positive Numbers)
Input
arr = [1, 4, 20, 3, 10, 5]
S = 33
Output
Subarray found from index 2 to 4
Explanation
20 + 3 + 10 = 33
Example 2
Input
arr = [1, 2, 3, 7, 5]
S = 12
Output
Subarray found from index 1 to 3
Important Observation
The approach depends on array type:
- Only Positive Numbers → Sliding Window
- Contains Negative Numbers → Prefix Sum + Hash Map
Approach 1: Sliding Window (For Positive Numbers Only)
Core Idea
- Expand window by moving end
- If sum becomes greater than target, shrink window from start
- Stop when sum equals target
Algorithm
- Initialize:
- start = 0
- currentSum = 0
- Traverse array using end
- Add arr[end] to currentSum
- While currentSum > S, subtract arr[start] and increment start
- If currentSum == S, print indices
Time and Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(1)
Below are the Subarray with Given Sum solutions, given one by one, clearly separated.
C Implementation
#include<stdio.h>
int main() {
int arr[] = {1, 4, 20, 3, 10, 5};
int n = 6;
int S = 33;
int start = 0, currSum = 0;
for (int end = 0; end < n; end++) {
currSum += arr[end];
while (currSum > S && start <= end) {
currSum -= arr[start];
start++;
}
if (currSum == S) {
printf("Subarray found from index %d to %d", start, end);
return 0;
}
}
printf("No subarray found");
return 0;
}
Output
Subarray found from index 2 to 4
C++ Implementation
#include<iostream>
using namespace std;
int main() {
int arr[] = {1, 4, 20, 3, 10, 5};
int n = 6, S = 33;
int start = 0, currSum = 0;
for (int end = 0; end < n; end++) {
currSum += arr[end];
while (currSum > S && start <= end) {
currSum -= arr[start++];
}
if (currSum == S) {
cout << "Subarray found from index " << start << " to " << end;
return 0;
}
}
cout << "No subarray found";
return 0;
}
Output
Subarray found from index 2 to 4
Java Implementation
public class SubarraySlidingWindow {
public static void main(String[] args) {
int[] arr = {1, 4, 20, 3, 10, 5};
int S = 33;
int start = 0, currSum = 0;
for (int end = 0; end < arr.length; end++) {
currSum += arr[end];
while (currSum > S && start <= end) {
currSum -= arr[start++];
}
if (currSum == S) {
System.out.println("Subarray found from index " + start + " to " + end);
return;
}
}
System.out.println("No subarray found");
}
}
Python Implementation
arr = [1, 4, 20, 3, 10, 5]
S = 33
start = 0
curr_sum = 0
for end in range(len(arr)):
curr_sum += arr[end]
while curr_sum > S and start <= end:
curr_sum -= arr[start]
start += 1
if curr_sum == S:
print("Subarray found from index", start, "to", end)
break
JavaScript Implementation
let arr = [1, 4, 20, 3, 10, 5];
let S = 33;
let start = 0, currSum = 0;
for (let end = 0; end < arr.length; end++) {
currSum += arr[end];
while (currSum > S && start <= end) {
currSum -= arr[start++];
}
if (currSum === S) {
console.log("Subarray found from index", start, "to", end);
break;
}
}
.Dry Run (Sliding Window)
arr = [1, 4, 20, 3, 10, 5], S = 33
end=0 → sum=1
end=1 → sum=5
end=2 → sum=25
end=3 → sum=28
end=4 → sum=38 (greater than 33)
Remove arr[0]=1 → sum=37
Remove arr[1]=4 → sum=33 → FOUND
Approach 2: Prefix Sum + Hash Map (Handles Negative Numbers)
When to Use
- Array contains negative numbers
- Sliding window fails because sum may decrease unexpectedly
Core Idea
If:
prefixSum[j] - prefixSum[i] = S
Then:
prefixSum[i] = prefixSum[j] - S
Store prefix sums in a hash map.
Algorithm
- Initialize:
- sum = 0
- Hash map to store prefix sum and index
- Traverse array:
- Add current element to sum
- If sum == S, subarray found from 0 to i
- If (sum - S) exists in map:
- Subarray exists from map[sum-S]+1 to i
- Store sum in map if not already present
Time and Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(n)
C++ Implementation
#include<iostream>
#include<unordered_map>
using namespace std;
int main() {
int arr[] = {10, 2, -2, -20, 10};
int n = 5, S = -10;
unordered_map<int,int> mp;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
if (sum == S) {
cout << "Subarray found from index 0 to " << i;
return 0;
}
if (mp.find(sum - S) != mp.end()) {
cout << "Subarray found from index "
<< mp[sum - S] + 1 << " to " << i;
return 0;
}
mp[sum] = i;
}
cout << "No subarray found";
return 0;
}
Output
Subarray found from index 0 to 3
Java Implementation
import java.util.*;
public class SubarrayPrefixSum {
public static void main(String[] args) {
int[] arr = {10, 2, -2, -20, 10};
int S = -10;
Map<Integer, Integer> map = new HashMap<>();
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
if (sum == S) {
System.out.println("Subarray found from index 0 to " + i);
return;
}
if (map.containsKey(sum - S)) {
System.out.println("Subarray found from index " +
(map.get(sum - S) + 1) + " to " + i);
return;
}
map.put(sum, i);
}
System.out.println("No subarray found");
}
}
Python Implementation
arr = [10, 2, -2, -20, 10]
S = -10
mp = {}
sum_val = 0
for i, num in enumerate(arr):
sum_val += num
if sum_val == S:
print("Subarray found from index 0 to", i)
break
if (sum_val - S) in mp:
print("Subarray found from index", mp[sum_val - S] + 1, "to", i)
break
mp[sum_val] = i
JavaScript Implementation
let arr = [10, 2, -2, -20, 10];
let S = -10;
let map = new Map();
let sum = 0;
for (let i = 0; i < arr.length; i++) {
sum += arr[i];
if (sum === S) {
console.log("Subarray found from index 0 to", i);
break;
}
if (map.has(sum - S)) {
console.log(
"Subarray found from index",
map.get(sum - S) + 1,
"to",
i
);
break;
}
map.set(sum, i);
}
Summary
| Case | Best Approach |
|---|---|
| Only positive numbers | Sliding Window |
| Negative numbers allowed | Prefix Sum + Hash Map |
Key Takeaways
- Subarray means continuous
- Sliding window is fastest but limited
- Prefix sum handles all cases
- Common interview problem after Two Sum & Kadane
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
