Find subarray with given sum using DP
We can use dynamic programming to find the subarray with the given sum. The basic idea is to iterate through the array, keeping track of the current sum and storing the difference between the current sum and the given sum in a hash table. If the difference is seen again later in the array, then we know that the subarray with the given sum exists and we can return it. This approach is efficient in terms of time and space, but it may not be suitable if the array is very large and the hash table becomes too large to fit in memory.
Algorithm:
- Initialize an empty hash table and a variable curr_sum to 0.
- Iterate through the array, keeping track of the current element in a variable i.
- Add i to curr_sum and check if curr_sum – sum is in the hash table. If it is, then return the subarray from the index stored in the hash table to i.
- If curr_sum – sum is not in the hash table, add an entry to the hash table with the key curr_sum and the value i.
- If you reach the end of the array and no subarray with the given sum is found, return an empty array.
Below in the implementation of the above approach:
#include <iostream>
#include <unordered_map>
#include <vector>
std::vector<int> find_subarray_with_given_sum(const 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) {
return std::vector<int>({0, i});
}
if (map.count(curr_sum - sum)) {
return std::vector<int>({map[curr_sum - sum] + 1, i});
}
map[curr_sum] = i;
}
return {};
}
int main()
{
std::vector<int> arr = {15, 2, 4, 8, 5, 10, 23};
int target_sum = 21;
std::vector<int> subarray = find_subarray_with_given_sum(arr, target_sum);
if (subarray.empty()) {
std::cout << "No subarray with sum " << target_sum << " found." << std::endl;
} else {
std::cout << "Sum found between indexes " << subarray[0] << " and " << subarray[1] << std::endl;
}
return 0;
}
import java.util.HashMap;
import java.util.Map;
public class SubarraySum {
public static int[] findSubarrayWithGivenSum(int[] arr, int sum) {
Map<Integer, Integer> map = new HashMap<>();
int currSum = 0;
for (int i = 0; i < arr.length; i++) {
currSum += arr[i];
if (currSum == sum) {
return new int[]{0, i};
}
if (map.containsKey(currSum - sum)) {
return new int[]{map.get(currSum - sum) + 1, i};
}
map.put(currSum, i);
}
return new int[]{};
}
public static void main(String[] args) {
int[] arr = {15, 2, 4, 8, 5, 10, 23};
int targetSum = 21;
int[] subarray = findSubarrayWithGivenSum(arr, targetSum);
if (subarray.length == 0) {
System.out.println("No subarray with sum " + targetSum + " found.");
} else {
System.out.println("Sum found between indexes " + subarray[0] + " and " + subarray[1]);
}
}
}
def find_subarray_with_given_sum(arr, target_sum):
curr_sum = 0
index_map = {}
for i, num in enumerate(arr):
curr_sum += num
if curr_sum == target_sum:
return [0, i]
if curr_sum - target_sum in index_map:
startIndex = index_map[curr_sum - target_sum]
#Accounting for a value of 0 at the start Index in arr
startIndex = startIndex if arr[startIndex] == 0 else startIndex + 1
return [startIndex, i]
index_map[curr_sum] = i
return []
arr = [8,2,4,0,6,9,1,2]
target_sum = 18
subarray = find_subarray_with_given_sum(arr, target_sum)
if not subarray:
print(f"No subarray with sum {target_sum} found.")
else:
print(f"Sum found between indexes {subarray[0]} and {subarray[1]}")
using System;
using System.Collections.Generic;
class SubarraySum {
static int[] FindSubarrayWithGivenSum(int[] arr, int sum) {
Dictionary<int, int> map = new Dictionary<int, int>();
int currSum = 0;
for (int i = 0; i < arr.Length; i++) {
currSum += arr[i];
if (currSum == sum) {
return new int[]{0, i};
}
if (map.ContainsKey(currSum - sum)) {
return new int[]{map[currSum - sum] + 1, i};
}
map[currSum] = i;
}
return new int[]{};
}
static void Main() {
int[] arr = {15, 2, 4, 8, 5, 10, 23};
int targetSum = 21;
int[] subarray = FindSubarrayWithGivenSum(arr, targetSum);
if (subarray.Length == 0) {
Console.WriteLine($"No subarray with sum {targetSum} found.");
} else {
Console.WriteLine($"Sum found between indexes {subarray[0]} and {subarray[1]}");
}
}
}
function findSubarrayWithGivenSum(arr, sum) {
const map = new Map();
let currSum = 0;
for (let i = 0; i < arr.length; i++) {
currSum += arr[i];
if (currSum === sum) {
return [0, i];
}
if (map.has(currSum - sum)) {
return [map.get(currSum - sum) + 1, i];
}
map.set(currSum, i);
}
return [];
}
const arr = [15, 2, 4, 8, 5, 10, 23];
const targetSum = 21;
const subarray = findSubarrayWithGivenSum(arr, targetSum);
if (subarray.length === 0) {
console.log(`No subarray with sum ${targetSum} found.`);
} else {
console.log(`Sum found between indexes ${subarray[0]} and ${subarray[1]}`);
}
Output
Sum found between indexes 0 and 2
Time Complexity: O(N)
Auxiliary Space: O(N)
The above solution doesn’t handle negative numbers. We can use hashing to handle negative numbers. See below set 2.
Find Subarray with given sum | Set 1 (Non-negative Numbers)
Given an array arr[] of non-negative integers and an integer sum, find a subarray that adds to a given sum.
Note: There may be more than one subarray with sum as the given sum, print first such subarray.
Examples:
Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Output: Sum found between indexes 2 and 4
Explanation: Sum of elements between indices 2 and 4 is 20 + 3 + 10 = 33Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Output: Sum found between indexes 1 and 4
Explanation: Sum of elements between indices 1 and 4 is 4 + 0 + 0 + 3 = 7Input: arr[] = {1, 4}, sum = 0
Output: No subarray found
Explanation: There is no subarray with 0 sum