How to find the subarray with a given sum

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.

Python code

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 = 0
   
    for i in range(len(arr)):
        
        current_sum += arr[i]
        if current_sum == sum:
            subarray = arr[:i+1]
            return subarray
        previous_sum = current_sum - sum
          
        if previous_sum in hash_map:
            start_index = hash_map[previous_sum]+1
            subarray = arr[start_index: i+1]
            return subarray
   
        hash_map[current_sum] = i
    return "No subarray found"
sum = 6 #change the value of sum
arr = input().split()
arr = [int(i) for i in arr]
subarray = subarray_finder(arr, sum)
print(subarray)

Enter the input below

Code input area

Code explanation

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.

Free Resources