Skip to main content

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

Find all subarray with given sum

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))
            {
                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.

Last updated on by Kalkicode




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.

New Comment