Find all subarray with given sum
The problem is to find all subarrays in a given array whose elements sum up to a given value k
. A
subarray is a contiguous sequence of elements in the array.
Problem Statement
Given an array of integers and a target sum k
, find all subarrays whose elements sum up to
k
and display their starting and ending indices.
Example

Consider the following example:
Input:
arr = [5, 3, 2, -3, 3, 8, -8, 6, 4, -8]
k = 10
Output:
Subarray of sum 10 are
Index location (0, 2)
Index location (0, 4)
Index location (2, 5)
Index location (0, 6)
Index location (3, 8)
Index location (5, 8)
Index location (7, 8)
Explanation:
- The given array is
[5, 3, 2, -3, 3, 8, -8, 6, 4, -8]
. - The subarray
[5, 3, 2]
starting at index 0 and ending at index 2 has a sum of 10. - The subarray
[5, 3, 2, -3, 3]
starting at index 0 and ending at index 4 has a sum of 10. - The subarray
[2, -3, 3, 8]
starting at index 2 and ending at index 5 has a sum of 10. - The subarray
[5, 3, 2, -3, 3, 8, -8]
starting at index 0 and ending at index 6 has a sum of 10. - The subarray
[-3, 3, 8, -8, 6]
starting at index 3 and ending at index 8 has a sum of 10. - The subarray
[8, -8]
starting at index 5 and ending at index 8 has a sum of 10. - The subarray
[6, 4]
starting at index 7 and ending at index 8 has a sum of 10.
Idea to Solve the Problem
To find all subarrays with the given sum k
, we can use a HashMap to keep track of the cumulative sum
of elements seen so far. We iterate through the array and update the sum while storing the indices in the
HashMap. If the difference between the current sum and k
is found in the HashMap, it means there is
a subarray with the required sum. We store the starting and ending indices of such subarrays in a list and
display them at the end.
Pseudocode
Function difference(sum, k)
If sum is greater than or equal to k
Return sum - k
Else if sum is greater than or equal to 0
Return -(k - sum)
Else
Return k + sum
Function ksumSubarray(arr, k)
Create an empty HashMap called map
Create an empty list called result
Get the size of the array and store it in the variable size
Initialize sum and diff to 0
For each index i from 0 to size - 1, do the following:
Increment sum by arr[i]
If sum is equal to k, add the pair (0, i) to the result list
Calculate the difference between sum and k using the difference function and store it in diff
If diff exists as a key in map, do the following:
For each value record in the list associated with the key diff, do the following:
Add the pair (record + 1, i) to the result list
If sum exists as a key in map, add i to the list associated with the key sum
Else, add the key sum with the value [i] to the map
Display "Subarray of sum" and k
If the size of result is 0, display "None"
Else, for each pair data in the result list, do the following:
Display "Index location" and the starting index (data.getKey()) and ending index (data.getValue())
Main function
Initialize arr with the given array [5, 3, 2, -3, 3, 8, -8, 6, 4, -8]
Initialize k with the given value 10
Call the ksumSubarray function with arr and k as parameters
Algorithm
- Define a function
difference
that takes the sum andk
as parameters and returns the absolute difference between them. - Define a function
ksumSubarray
that takes the arrayarr
and the target sumk
as parameters and finds all subarrays with the given sum using a HashMap. - Create an empty HashMap called
map
to store cumulative sums and their corresponding indices. - Create an empty list called
result
to store pairs of starting and ending indices of subarrays with the required sum. - Get the size of the array
arr
and store it in the variablesize
. - Initialize
sum
anddiff
to 0 to keep track of the cumulative sum and the difference between the current sum andk
. - Iterate through each index
i
from 0 tosize - 1
, and for each index, do the following:- Increment
sum
byarr[i]
to update the cumulative sum. - If
sum
is equal tok
, it means the subarray from index 0 toi
has the required sum, so add the pair(0, i)
to theresult
list. - Calculate the difference between
sum
andk
using thedifference
function and store it indiff
. - If
diff
exists as a key in themap
, it means there are subarrays with the required sum, so for each valuerecord
in the list associated with the keydiff
, add the pair(record + 1, i)
to theresult
list, representing the subarray starting from indexrecord + 1
toi
. - If
sum
exists as a key in themap
, addi
to the list associated with the keysum
. - Else, add the key
sum
with the value[i]
to themap
.
- Increment
- Display "Subarray of sum" and
k
. - If the size of the
result
list is 0, display "None" because there are no subarrays with the required sum. - Else, for each pair
data
in theresult
list, display "Index location" and the starting index (data.getKey()
) and ending index (data.getValue()
).
/*
Java program
Find all subarray with given sum
*/
import java.util.*;
import javafx.util.Pair;
public class SubArraySum
{
// Returns absolute difference of given sum and k
private int difference(int sum, int k)
{
if (sum >= k)
{
return sum - k;
}
else if (sum >= 0)
{
return -(k - sum);
}
else
{
return k + sum;
}
}
// This function are finding all the subarray with given sum
public void ksumSubarray(int[] arr, int k)
{
// Define map with list of Integer elements
HashMap < Integer, List < Integer >> map = new HashMap < > ();
// Define list with integer pair value
List < Pair < Integer, Integer >> result = new ArrayList < Pair < Integer, Integer >> ();
// Get the size of array
int size = arr.length;
// Define auxiliary variable which is calculate sum and difference
int sum = 0, diff = 0;
// iterate loop through by given array size
for (int i = 0; i < size; ++i)
{
sum += arr[i];
if (sum == k)
{
// Base case index 0 to i sum is k
result.add(new Pair < Integer, Integer > (0, i));
}
// Find the difference between the current sum and the given k.
diff = difference(sum, k);
if (map.containsKey(diff))
{
//When current sum difference already exist in map collection
for (int record: map.get(diff))
{
//Add new pair into resultant pair
//record+1 is next index of exist sum
result.add(new Pair < Integer, Integer > (record + 1, i));
}
}
if (map.containsKey(sum))
{
map.get(sum).add(i);
}
else
{
map.put(sum, new ArrayList < Integer > ());
map.get(sum).add(i);
}
}
// Display given sum
System.out.println(" Subarray of sum " + k + " are ");
if (result.size() == 0)
{
// In case there are no subarray pair of given k
System.out.println("None");
}
else
{
// Display resultant index
for (Pair data: result)
{
System.out.println(" Index location (" + data.getKey() + " " + data.getValue() + ")");
}
}
}
public static void main(String[] args)
{
SubArraySum task = new SubArraySum();
//Array element
int[] arr = {
5 , 3 , 2 , -3 , 3 , 8 , -8 , 6 , 4 , -8
};
// k = 10
// Find subarray with given sum
task.ksumSubarray(arr, 10);
}
}
input
Subarray of sum 10 are
Index location (0 2)
Index location (0 4)
Index location (2 5)
Index location (0 6)
Index location (3 8)
Index location (5 8)
Index location (7 8)
// Include header file
#include <iostream>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
class SubArraySum
{
public:
// Returns absolute difference of given sum and k
int difference(int sum, int k)
{
if (sum >= k)
{
return sum - k;
}
else if (sum >= 0)
{
return -(k - sum);
}
else
{
return k + sum;
}
}
// This function are finding all the subarray with given sum
void ksumSubarray(int arr[], int k, int size)
{
// Define map with list of Integer elements
unordered_map < int, vector < int > > map;
// Define list with integer pair value
vector < pair < int, int > > result;
// Define auxiliary variable which is calculate sum and difference
int sum = 0;
int diff = 0;
// iterate loop through by given array size
for (int i = 0; i < size; ++i)
{
sum += arr[i];
if (sum == k)
{
// Base case index 0 to i sum is k
result.push_back(make_pair(0, i));
}
// Find the difference between the current sum and the given k.
diff = this->difference(sum, k);
if (map.find(diff) != map.end())
{
//When current sum difference already exist in map collection
for (auto &it : map[diff])
{
//Add new pair into resultant pair
//record+1 is next index of exist sum
result.push_back(make_pair( it + 1, i));
}
}
if (map.find(sum) != map.end())
{
map[sum].push_back(i);
}
else
{
map[sum].push_back(i);
}
}
// Display given sum
cout << " Subarray of sum " << k << " are " << endl;
if (result.size() == 0)
{
// In case there are no subarray pair of given k
cout << "None" << endl;
}
else
{
// Display resultant index
for (auto data = result.begin(); data != result.end(); data++)
{
cout << " Index location (" << data->first
<< " " << data->second << ")" << endl;
}
}
}
};
int main()
{
SubArraySum *task = new SubArraySum();
//Array element
int arr[] =
{
5 , 3 , 2 , -3 , 3 , 8 , -8 , 6 , 4 , -8
};
// Get the size of array elements
int size = sizeof(arr) / sizeof(arr[0]);
// k = 10
// Find subarray with given sum
task->ksumSubarray(arr, 10, size);
return 0;
}
input
Subarray of sum 10 are
Index location (0 2)
Index location (0 4)
Index location (2 5)
Index location (0 6)
Index location (3 8)
Index location (5 8)
Index location (7 8)
// Include namespace system
using System;
using System.Collections.Generic;
public class SubArraySum
{
// Returns absolute difference of given sum and k
private int difference(int sum, int k)
{
if (sum >= k)
{
return sum - k;
}
else if (sum >= 0)
{
return -(k - sum);
}
else
{
return k + sum;
}
}
// This function are finding all the subarray with given sum
public void ksumSubarray(int[] arr, int k)
{
// Define map with list of Integer elements
Dictionary < int, List < int >> map = new Dictionary <int, List < int >> ();
// Define list with integer pair value
List < Tuple < int, int >> result = new List < Tuple < int, int >> ();
// Get the size of array
int size = arr.Length;
// Define auxiliary variable which is calculate sum and difference
int sum = 0;
int diff = 0;
// iterate loop through by given array size
for (int i = 0; i < size; ++i)
{
sum += arr[i];
if (sum == k)
{
// Base case index 0 to i sum is k
result.Add(new Tuple < int, int > (0, i));
}
// Find the difference between the current sum and the given k.
diff = this.difference(sum, k);
if (map.ContainsKey(diff))
{
//When current sum difference already exist in map collection
foreach(int record in map[diff])
{
//Add new pair into resultant pair
//record+1 is next index of exist sum
result.Add(new Tuple < int, int > (record + 1, i));
}
}
if (map.ContainsKey(sum))
{
map[sum].Add(i);
}
else
{
map.Add(sum, new List < int > ());
map[sum].Add(i);
}
}
// Display given sum
Console.WriteLine(" Subarray of sum " + k + " are ");
if (result.Count == 0)
{
// In case there are no subarray pair of given k
Console.WriteLine("None");
}
else
{
// Display resultant index
for (int i = 0; i < result.Count; i++)
{
Console.WriteLine(" Index location ({0} {1})",
result[i].Item1, result[i].Item2);
}
}
}
public static void Main(String[] args)
{
SubArraySum task = new SubArraySum();
//Array element
int[] arr = {
5 , 3 , 2 , -3 , 3 , 8 , -8 , 6 , 4 , -8
};
// k = 10
// Find subarray with given sum
task.ksumSubarray(arr, 10);
}
}
input
Subarray of sum 10 are
Index location (0 2)
Index location (0 4)
Index location (2 5)
Index location (0 6)
Index location (3 8)
Index location (5 8)
Index location (7 8)
<?php
/*
PHP Program
Find all subarray with given sum
*/
class Hashing
{
// Returns absolute difference of given sum and k
public
function difference($sum, $k)
{
if ($sum >= $k)
{
return $sum - $k;
}
else if ($sum >= 0)
{
return -($k - $sum);
}
else
{
return $k + $sum;
}
}
// This function are finding all the subarray with given sum
public
function subarray_sum($arr, $k)
{
$dict_item = array();
$result = array();
// Define auxiliary variable which is calculate sum and difference
$sum = 0;
$diff = 0;
// Get the size of array
$size = count($arr);
// iterate loop through by given array size
for ($i = 0; $i < $size; ++$i)
{
// Calculate current sum
$sum += $arr[$i];
if ($sum == $k)
{
// Base case index 0 to i sum is k
$result[] = array(0, $i);
}
$diff = $this->difference($sum, $k);
if (array_key_exists($diff, $dict_item))
{
for ($j = 0; $j < count($dict_item[$diff]); $j++)
{
$result[] = array($dict_item[$diff][$j] + 1, $i);
}
}
if (array_key_exists($sum, $dict_item))
{
array_push($dict_item[$sum], $i);
}
else
{
$dict_item[$sum] = array($i);
}
}
// Display Given k sum
echo " Subarray of sum ".$k.
" are\n";
if (count($dict_item) == 0)
{
// In case there are no subarray pair of given k
}
else
{
// Display resultant index
foreach($result as $key => $value)
{
echo " Index location ($value[0] $value[1]) \n";
}
}
}
}
function main()
{
$obj = new Hashing();
// Define array of integer elements
$arr = array(5, 3, 2, -3, 3, 8, -8, 6, 4, -8);
// k = 10
// Find subarray with given sum
$obj->subarray_sum($arr, 10);
}
main();
input
Subarray of sum 10 are
Index location (0 2)
Index location (0 4)
Index location (2 5)
Index location (0 6)
Index location (3 8)
Index location (5 8)
Index location (7 8)
# Python program
# Find all subarray with given sum
class Hashing:
# Returns absolute difference of given sum and k
def difference(self,amount, k) :
if(amount >= k ) :
return amount-k
elif(amount >= 0) :
return -(k - amount)
else :
return k + amount
# This function are finding all the subarray with given sum
def subarray_sum(self,collection,k):
dictItem = {}
result = []
# Define auxiliary variable which is calculate sum and difference
amount = 0
diff = 0
# iterate loop through by given array size
for i, val in enumerate(collection):
# Calculate current sum
amount += val
if(amount==k):
result.append([0,i])
# Find the difference between the current sum and the given k.
diff=self.difference(amount,k)
if diff in dictItem:
# When current sum difference already exists in dictionary collection
for record in dictItem[diff]:
# Add new pair
result.append([record+1,i])
if amount in dictItem :
dictItem[amount].append(i)
else:
dictItem[amount]=[i]
# Display given sum
print(" Subarray of sum ",k," are")
if len(result) == 0:
# In case there are no subarray pair of given k
print("None")
else :
# Display resultant index
for record in result:
print(" Index location (",record[0],"",record[1],")")
def main():
obj = Hashing()
# Define list element
item =[5, 3, 2,-3, 3, 8, -8, 6, 4, -8]
# k = 10
# Find subarray with given sum
obj.subarray_sum(item,10)
if __name__=="__main__":
main()
Output
Subarray of sum 10 are
Index location ( 0 2 )
Index location ( 0 4 )
Index location ( 2 5 )
Index location ( 0 6 )
Index location ( 3 8 )
Index location ( 5 8 )
Index location ( 7 8 )
Time Complexity
The time complexity of the code is O(n), where n is the number of elements in the array. This is because we need to iterate through the array once to find all subarrays with the given sum. The operations in the HashMap (insertion, deletion, and retrieval) take constant time on average, making the overall time complexity linear in the number of elements.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment