Given an array that could contain negative and positive integers, find a subarray that sums up a given sum. An efficient solution to this problem employs hash maps, which can be abstracted using a dictionary in Python, as shown below.

The code snippet below provides an algorithm that uses a hash map to find a subarray with the given sum.

Note:To run the following code, provide input for the array in the form of just integers separated with a space (without commas or brackets).For example, enter [-3, 5, 1, -6, 4] as:

$\text{-}3\;5\;1\;\text{-}6\;4$

def subarray_finder(arr, sum):hash_map = dict()current_sum = 0for i in range(len(arr)):current_sum += arr[i]if current_sum == sum:subarray = arr[:i+1]return subarrayprevious_sum = current_sum - sumif previous_sum in hash_map:start_index = hash_map[previous_sum]+1subarray = arr[start_index: i+1]return subarrayhash_map[current_sum] = ireturn "No subarray found"sum = 6 #change the value of sumarr = input().split()arr = [int(i) for i in arr]subarray = subarray_finder(arr, sum)print(subarray)

Enter the input below

The algorithm operates with the following properties:

**Lines 1–24:**These lines contain the function`subarray_finder`

that takes the original array,`arr`

, and the given sum`sum`

, and finds the subarray if it exists.**Line 3:**An empty dictionary is created and stored in`hash_map`

, which abstracts our hash map.The keys of the dictionary contain the sum of the array's elements from index 0 to an index

`k`

.The values of the keys will be

`k`

.

**Line 5:**The variable`current_sum`

stores the sum of the array's elements from index 0 to another index (this will be used when traversing the array).**Lines 7–22:**A single traversal of the array is performed:**Line 9:**`current_sum`

is incremented to store the sum of the array from index 0 to index`i`

.**Lines 11–13:**If a subarray is found that begins at index 0 and ends at index`i`

, then it's returned.**Line 15:**The variable`previous_sum`

stores the sum of the array's elements from index 0 to index`k`

. It also acts as the key to`hash_map`

.**Lines 17–20:**The`previous_sum`

tells us about the starting index of the subarray (which is referred to as the index`k`

above). Therefore, if`previous_sum`

exists in`hash_map`

, index`k`

will be the value corresponding to the`previous_sum`

key. Elements from index`k`

up until index`i`

are returned since they sum up to the given sum.**Line 22:**If a subarray is not found that ends at the index`i`

, a key-value pair is added in`hash_map`

which stores the total of the array until the index`i`

.

**Line 24:**We are informed if a subarray isn't found at the end of the traversal.

**Line 27:**We can change the given sum, and it's stored in`sum`

.**Lines 29 and 30:**These take our input for the array.**Lines 32 and 33:**The subarray is found by calling the`subarray_finder`

function, and is then printed.

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS