Subarray with Given Sum
Java coding interview problem for Array Logic: Subarray with Given Sum.
The Subarray with Given Sum problem is one of the most common array problems asked in coding interviews.
This problem helps developers understand:
- Subarray traversal
- Sliding Window technique
- Prefix Sum pattern
- HashMap optimization
- Handling positive and negative numbers
It is a foundation for many advanced problems:
- Longest subarray problems
- Count subarrays with given sum
- Maximum/minimum window problems
- Range query problems
What is Subarray with Given Sum?
Given an array of integers and a target sum, find a contiguous subarray whose elements add up exactly to the target value.
Example 1
Input:
nums = [1,4,20,3,10,5]
target = 33
Subarray:
[20,3,10]
Sum:
20 + 3 + 10 = 33
Output:
Start Index = 2
End Index = 4
Example 2
Input:
nums = [1,2,3,7,5]
target = 12
Subarray:
[2,3,7]
Sum:
12
Output:
[2,3,7]
Example 3
Input:
nums = [1,2,3]
target = 10
No subarray exists.
Output:
No subarray found
Understanding the Problem
Consider:
Array:
[1,4,20,3,10,5]
Target:
33
We need a continuous section:
1
4
20
3
10
5
Try combinations:
1+4+20 = 25
Not enough.
4+20+3 = 27
Not enough.
20+3+10 = 33
Found.
Why is This Question Asked in Interviews?
This problem tests:
1. Array Traversal
Can you efficiently process elements?
2. Optimization Skills
Can you improve:
O(n²)
to:
O(n)
?
3. Pattern Recognition
Can you identify:
- Sliding Window
- Prefix Sum
4. Handling Constraints
Different approaches are required for:
- Positive numbers
- Negative numbers
- Large arrays
Real-World Applications
Financial Transactions
Finding a continuous set of transactions matching a specific amount.
Example:
Transactions:
[100,200,300,400]
Target:
900
Subarray:
[200,300,400]
Log Analysis
Finding continuous events that match a specific count.
Sensor Data
Finding a period where measurements reach a target value.
Billing Systems
Finding invoice groups matching a required total.
Problem Statement
Given an integer array:
nums
and an integer:
target
find a contiguous subarray whose sum equals the target.
Return the subarray indices or the subarray itself.
Constraints
Example:
1 <= nums.length <= 100000
Values:
-10000 <= nums[i] <= 10000
Important Rules
A subarray must be:
Continuous
Example:
Array:
[1,2,3,4]
Valid:
[2,3]
Invalid:
[1,3]
because element 2 is skipped.
Understanding Subarray Sum Logic
Example:
Input:
[1,2,3,7,5]
Target = 12
Possible subarrays:
[1]
[1,2]
[1,2,3]
[2,3,7]
Check:
2+3+7
=
12
Found.
Positive Numbers vs Negative Numbers
The approach depends on array values.
Case 1 — Positive Numbers Only
Example:
[1,4,20,3,10]
We can use:
Sliding Window
because:
Increasing window increases sum.
Case 2 — Negative Numbers
Example:
[10,-2,3,-1]
Sliding window fails.
Use:
Prefix Sum + HashMap
Array Visualization
Input:
[1,4,20,3,10,5]
Target = 33
Window:
[1]
Sum:
1
Expand:
[1,4]
Sum:
5
Expand:
[1,4,20]
Sum:
25
Expand:
[1,4,20,3]
Sum:
28
Expand:
[1,4,20,3,10]
Sum:
38
Too large.
Remove from left:
[4,20,3,10]
Sum:
37
Remove:
[20,3,10]
Sum:
33
Found.
Dry Run
Input:
nums = [1,4,20,3,10,5]
target = 33
Initialize:
start = 0
sum = 0
Add:
1
Current sum:
1
Add:
4
Current:
5
Add:
20
Current:
25
Add:
3
Current:
28
Add:
10
Current:
38
Greater than target.
Shrink window.
Remove:
1
Sum:
37
Remove:
4
Sum:
33
Window:
[20,3,10]
Found.
Approach 1 — Brute Force Approach
The simplest solution:
Check every possible subarray.
Algorithm
- Choose starting index.
- Expand ending index.
- Calculate sum.
- Compare with target.
Java Program
import java.util.Arrays;
public class SubarrayGivenSumBruteForce {
public static int[] findSubarray(
int[] nums,
int target) {
for (int i = 0;
i < nums.length;
i++) {
int sum = 0;
for (int j = i;
j < nums.length;
j++) {
sum += nums[j];
if (sum == target) {
return Arrays.copyOfRange(
nums,
i,
j + 1);
}
}
}
return new int[0];
}
public static void main(String[] args) {
int[] nums =
{1,4,20,3,10,5};
System.out.println(
Arrays.toString(
findSubarray(nums,33)));
}
}
Output
[20,3,10]
Step-by-Step Explanation
Input:
[1,4,20,3,10,5]
Target:
33
Start:
1
Sum:
1
Expand:
1+4
Sum:
5
Expand:
1+4+20
Sum:
25
Expand:
1+4+20+3+10
Sum:
38
Continue checking.
Eventually:
20+3+10
=
33
Return:
[20,3,10]
Complexity Analysis
Two loops:
Time:
O(n²)
Space:
O(1)
Advantages
- Easy to implement.
- Works with positive and negative numbers.
- Good learning approach.
Drawbacks
- Slow for large arrays.
- Recalculates sums.
- Not interview optimal.
Approach 2 — Prefix Sum Approach
Prefix sum avoids recalculating previous sums.
Prefix Sum Concept
Create cumulative sum array.
Example:
Input:
[1,4,20,3]
Prefix:
[1,5,25,28]
Meaning:
prefix[i] =
sum from 0 to i
Formula
Subarray sum:
i to j
is:
prefix[j] - prefix[i-1]
Example
Prefix:
[1,5,25,28]
Need:
33
Check:
current prefix - target
Approach 3 — Sliding Window Approach (Optimal for Positive Numbers)
The Sliding Window technique is the optimal solution when:
- All numbers are positive.
- We need to find a continuous subarray.
- We need O(n) time.
Core Idea
Maintain a window:
left pointer
right pointer
The window represents the current subarray.
We:
- Expand window by moving right pointer.
- If sum becomes greater than target, shrink from left.
- If sum equals target, return window.
Example
Input:
nums = [1,4,20,3,10,5]
target = 33
Initial:
left = 0
sum = 0
Add:
1
Window:
[1]
Sum:
1
Add:
4
Window:
[1,4]
Sum:
5
Add:
20
Window:
[1,4,20]
Sum:
25
Add:
3
Window:
[1,4,20,3]
Sum:
28
Add:
10
Window:
[1,4,20,3,10]
Sum:
38
Too large.
Shrink:
Remove:
1
Sum:
37
Remove:
4
Sum:
33
Window:
[20,3,10]
Found.
Algorithm
- Initialize:
left = 0
sum = 0
- Traverse using right pointer.
- Add current element.
- While:
sum > target
remove elements from left. 5. If:
sum == target
return subarray.
Java Program
import java.util.Arrays;
public class SubarrayGivenSumSlidingWindow {
public static int[] findSubarray(
int[] nums,
int target) {
int left = 0;
int sum = 0;
for (int right = 0;
right < nums.length;
right++) {
sum += nums[right];
while (sum > target &&
left <= right) {
sum -= nums[left];
left++;
}
if (sum == target) {
return Arrays.copyOfRange(
nums,
left,
right + 1);
}
}
return new int[0];
}
public static void main(String[] args) {
int[] nums =
{1,4,20,3,10,5};
System.out.println(
Arrays.toString(
findSubarray(nums,33)));
}
}
Output
[20,3,10]
Step-by-Step Explanation
Input:
[1,4,20,3,10,5]
Target:
33
Start:
left = 0
Right = 0
Add:
1
Sum:
1
Right = 1
Add:
4
Sum:
5
Right = 2
Add:
20
Sum:
25
Right = 3
Add:
3
Sum:
28
Right = 4
Add:
10
Sum:
38
Shrink:
Remove:
1
Sum:
37
Remove:
4
Sum:
33
Found:
[20,3,10]
Complexity Analysis
Each element enters the window once and leaves once.
Time:
O(n)
Space:
O(1)
Advantages
- Very fast.
- Simple implementation.
- Constant memory.
- Best for positive numbers.
Drawbacks
- Does not work correctly with negative numbers.
Why Sliding Window Fails with Negative Numbers?
Consider:
nums = [10, -5, 3]
target = 8
The sliding window assumes:
Increasing window:
sum increases
Removing from left:
sum decreases
But negative values break this assumption.
Example:
10 + (-5)
becomes:
5
Adding elements can decrease the sum.
Approach 4 — Prefix Sum + HashMap (Works With Negative Numbers)
When negative numbers exist, use:
Prefix Sum + HashMap
Core Idea
If:
currentPrefixSum - target = previousPrefixSum
then the elements between them have sum:
target
Formula
Suppose:
Current prefix:
sum
Need:
sum - target
If this value exists:
A valid subarray exists.
Example
Input:
nums = [10,2,-2,-20,10]
target = -10
Prefix sums:
10
12
10
-10
0
At:
-10
Check:
current - target
=
-10 - (-10)
=
0
Found previous prefix.
Subarray:
[10,2,-2,-20]
Java Program
import java.util.HashMap;
import java.util.Map;
public class SubarrayGivenSumPrefixHashMap {
public static int[] findSubarray(
int[] nums,
int target) {
Map<Integer,Integer> map =
new HashMap<>();
map.put(0,-1);
int sum = 0;
for (int i = 0;
i < nums.length;
i++) {
sum += nums[i];
if (map.containsKey(
sum - target)) {
int start =
map.get(sum - target)
+ 1;
return new int[]{
start,
i
};
}
map.put(sum,i);
}
return new int[]{-1,-1};
}
public static void main(String[] args) {
int[] nums =
{10,2,-2,-20,10};
int[] result =
findSubarray(nums,-10);
System.out.println(
result[0] +
" " +
result[1]);
}
}
Output
0 3
Complexity Analysis
Time:
O(n)
Space:
O(n)
Finding Actual Subarray Elements
Instead of returning:
start index
end index
we can extract:
Arrays.copyOfRange()
Example:
Arrays.copyOfRange(
nums,
start,
end + 1
);
Comparison of All Approaches
| Approach | Works With Negative Numbers | Time | Space |
|---|---|---|---|
| Brute Force | Yes | O(n²) | O(1) |
| Prefix Sum | Yes | O(n²) | O(n) |
| Sliding Window | No | O(n) | O(1) |
| Prefix Sum + HashMap | Yes | O(n) | O(n) |
Sliding Window Pattern Explanation
Sliding Window is useful when:
- Data is continuous.
- We need a range.
- Values have predictable behavior.
Examples:
- Maximum sum subarray of size K
- Longest substring
- Minimum window substring
- Positive number subarray sum
Prefix Sum Pattern Explanation
Prefix Sum is useful when:
Need:
Fast range calculation
Pattern:
Store:
previous cumulative result
Examples:
- Range sum query
- Subarray sum equals K
- Product queries
Primitive vs Object Arrays
Primitive Array
Example:
int[]
Advantages:
- Faster.
- Less memory.
- Better performance.
Object Array
Example:
Integer[]
Advantages:
- Works with Collections.
- Supports generic APIs.
Common Interview Mistakes
Mistake 1
Using Sliding Window with negative numbers.
Mistake 2
Confusing:
subarray
with:
subsequence
Mistake 3
Forgetting empty prefix:
map.put(0,-1);
This handles subarrays starting at index zero.
Mistake 4
Using brute force for large constraints.
Edge Cases
| Input | Target | Result |
|---|---|---|
[1,2,3] |
3 | [1,2] |
[5] |
5 | [5] |
[] |
10 | No result |
[-1,-2,3] |
0 | [-1,-2,3] |
[0,0,0] |
0 | [0] |
Interview Follow-up Questions
Q1. Find all subarrays with given sum.
Q2. Count subarrays with sum K.
Q3. Longest subarray with given sum.
Q4. Solve with negative numbers.
Q5. Find minimum length subarray.
Q6. Maximum sum sliding window.
Q7. Explain prefix sum approach.
Related Problems
- Subarray Sum Equals K
- Longest Subarray with Sum K
- Maximum Subarray
- Sliding Window Problems
- Prefix Sum Problems
- Two Pointer Problems
Key Takeaways
The Subarray with Given Sum problem has different solutions based on constraints.
Decision tree:
Only Positive Numbers?
|
Yes
|
Sliding Window
|
No
|
Prefix Sum + HashMap
Frequently Asked Interview Questions
Q1. What is the optimal solution for positive numbers?
Sliding Window.
Complexity:
O(n)
Q2. What if negative numbers exist?
Use:
Prefix Sum + HashMap
Q3. Why does sliding window fail?
Because negative numbers break the increasing/decreasing sum assumption.
Q4. Why store prefix sum indexes?
To calculate:
current prefix - previous prefix
Interview Tip
When asked:
"Find subarray with given sum."
First clarify:
- Are numbers positive only?
- Can numbers be negative?
- Do we need the subarray or only count?
Then choose:
Positive Numbers:
Sliding Window
Negative Numbers:
Prefix Sum + HashMap
This demonstrates strong understanding of array patterns, optimization, and algorithm selection.