Posted on by Kalkicode
Code Hash

# 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

1. Define a function `difference` that takes the sum and `k` as parameters and returns the absolute difference between them.
2. Define a function `ksumSubarray` that takes the array `arr` and the target sum `k` as parameters and finds all subarrays with the given sum using a HashMap.
3. Create an empty HashMap called `map` to store cumulative sums and their corresponding indices.
4. Create an empty list called `result` to store pairs of starting and ending indices of subarrays with the required sum.
5. Get the size of the array `arr` and store it in the variable `size`.
6. Initialize `sum` and `diff` to 0 to keep track of the cumulative sum and the difference between the current sum and `k`.
7. Iterate through each index `i` from 0 to `size - 1`, and for each index, do the following:
• Increment `sum` by `arr[i]` to update the cumulative sum.
• If `sum` is equal to `k`, it means the subarray from index 0 to `i` has the required sum, so 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 the `map`, it means there are subarrays with the required sum, so for each value `record` in the list associated with the key `diff`, add the pair `(record + 1, i)` to the `result` list, representing the subarray starting from index `record + 1` to `i`.
• If `sum` exists as a key in the `map`, add `i` to the list associated with the key `sum`.
• Else, add the key `sum` with the value `[i]` to the `map`.
8. Display "Subarray of sum" and `k`.
9. If the size of the `result` list is 0, display "None" because there are no subarrays with the required sum.
10. Else, for each pair `data` in the `result` 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))
{
}
else
{
map.put(sum, new ArrayList < Integer > ());
}
}
// 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)
{
//Array element
int[] arr = {
5 , 3 , 2 , -3 , 3 , 8 , -8 , 6 , 4 , -8
};
// k = 10
// Find subarray with given sum
}
}``````

#### 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()
{
//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
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))
{
}
else
{
map.Add(sum, new List < int > ());
}
}
// 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)
{
//Array element
int[] arr = {
5 , 3 , 2 , -3 , 3 , 8 , -8 , 6 , 4 , -8
};
// k = 10
// Find subarray with given sum
}
}``````

#### 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]:
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.

## Comment

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.

Categories
Relative Post