The aim of this article is to help you compute the subarray whose sum is given and the subarray is contiguous. For your information, a contiguous array is one whose elements occupy positions that follow each other. In addition, the sequence of elements is also maintained.
We will look at two approaches to solve this problem. The first approach is a brute-force one where all the subarrays are considered. In this case, the sum of their elements is computed and checked against the given expected sum. If the two are the same, we have found our solution. If not, then we continue adding the remaining items in the sequence till we reach the end.
The second approach involves the use of dynamic programming. In this example, we will engage the use of top-down approach dynamic programming.
Dynamic programming is a class or type of algorithm of simply what is referred in technical terms as algorithm paradigm. This is just one of the paradigm’s alongside others like the divide & conquer, brute-force, greedy algorithms.
Dynamic programming solves a different set of problems. It is important to be able to identify problems that can be solved using dynamic programming and how to arrive at these solutions.
Identifying problems that can be solved using dynamic programming.
Problems that can be solved using dynamic programming exhibit two main properties
1) Optimal Substructure
2) Overlapping Subproblems
When hearing about these two terms for the first time, you might be a little fearful but there is no cause for alarm or fear. Don’t worry about them sounding very mathematical or extremely functional. They are simple concepts that we will break down using a practical approach.
Our solution to solving a problem in a dynamic programming approach involves 4 steps
1) Finding a recurrence relation
This simply refers to a relation that repeats itself. In this case, the concept of recursion is very handy.
This where you have to master the concept of recursion.
Recursion is the concept of a function calling itself until it hits a base case. To better understand the concept of recursion, you can look at the two most famous examples on factorial and the Fibonacci numbers. Other practical examples of recursion is writing a function to do file search in a given directory and a count down timer.
2) Top Down Approach
The top-down approach involves solving a problem from a top level i.e. from a global solution, breaking it down into smaller sub problems and finding solutions for each one of them until we arrive to the global one.
3) Bottom up approach
This is the opposite of the top down approach. It involves first finding the solutions of all the small sub problems and then you build a global one from all the smaller sub problems.
4) Optimization of Bottom up approach
Finally, we need to find ways of optimizing the bottom up solution so that we have a more efficient solution either in form of run time performance or memory.
In the initial two steps, we find out if the solution can be solved in a dynamic programming approach by considering the two concepts of optimal substructure and the overlapping subproblems.
From experience, these concepts can only be mastered by getting your hands dirty through solving a number of such problems. Such a practical problem that will help you master these concepts is the idea of finding a subarray with a given sum.
Using Brute-Force to find SubArray with given Sum
It is the simplest and most obvious approach where the sum of array elements is computed by considering all the subarrays. At the point where the computed sum is equal to the expected sum we print the subarray. Below is the implementation of the brute-force approach in Python.
# Function to find subarray with the given the expected sum in a list
def findSubArrayBruteForce(A, expected_sum):
for i in range(len(A)):
expected_sum_so_far = 0
# consider all subarrays starting from `i` and ending at `j`
for j in range(i, len(A)):
# expected_sum of elements so far
expected_sum_so_far += A[j]
# if the expected_sum so far is equal to the given expected_sum
if expected_sum_so_far == expected_sum:
# print subarray `A[i, j]`
print(A[i:j + 1])
if __name__ == '__main__':
A = [3, 4, -7, 1, 3, 3, 1, -4]
expected_sum = 7
findSubArrayBruteForce(A, expected_sum)
Complexity Analysis
Time Complexity: O(N^3)
The time complexity of this brute-force approach is O(N^3)
= O(N) for printing the subarray
= O(N^2) because the subarray’s sum calculation occurs in O(1) for every one of the N^2 subarrays whose array size is N.
Space Complexity: O(1)
O(1) because no extra space is need in this computation
Finding the SubArray using Optimized Brute-Force
# Returns true if the there is a subarray
# of arr[] with sum equal to 'expected_sum'
# otherwise returns # false.
def findSubArrayBruteForceOpt(arr, expected_sum):
# Pick a starting point
n =len(arr)
for i in range(n):
curr_sum = arr[i]
# try all subarrays starting with 'i'
j = i + 1
while j <= n:
if curr_sum == expected_sum:
print("subarray sum found between indexes (inclusive): %% d and %% d" %% (i, j - 1))
return 1
if curr_sum > expected_sum or j == n:
break
curr_sum = curr_sum + arr[j]
j += 1
print("No subarray found")
return 0
# main function to test findSubArrayBruteForceOpt program
if __name__ == "__main__":
arr = [15, 2, 4, 8, 9, 5, 10, 23]
n = len(arr)
expected_sum = 23
findSubArrayBruteForceOpt(arr, expected_sum)
Complexity Analysis:
Time Complexity: O(N^2)
We use an inner nested loop to traverse the array. Thus the overall worst case time complexity is O(N^2)
Space Complexity: O(1).
There is no extra space needed so the auxilliary space is O(1).
Finding SubArray using the TopDown Approach
The TopDown approach is also called the hashing method. It involves storing the elements’ sum in a hashmap using the array’s prefix. For instance for index 4, we store the sum of elements to index four in the hashmap as follows:
map[sum_upto_index_4] =4
The process of finding a subarray whose sum is equal to the given value entails checking the hashmap for every index in the loop. Store this value in a variable current_sum.
Now, when the difference between the expected sum and the current sum is found in the hashmap, we can conclude that the subarray exists. And we can then extract the respective indexes of these values.
Algorithm walk through:
- create a hashmap called sub_array_indexes and initialize the starting sum to -1 when the starting index is 0 i.e. sub_array_indexes = {0: -1}
- initialize the sum to zero i.e. initial_sum =0
- traverse through the array of integers and for each index add the new value at that index to the previous sum i.e. initial_sum += arr_[i]
- Check if the initial_sum minus the expected sum exists in the map. If it does, then we have found both the indexes that make up the subarray we are looking for.
i.e. if (initial_sum – expected_sum) in sub_array_indexes: - If step 4 above is false, we save the new initial_sum to the map by assigning the current index of the array, sub_array_indexes[initial_sum] = i
# Python Function to get a subarray that adds up to a given sum using hashing
def findSubArrayTopDown(arr_, expected_sum):
# insert `(0, -1)` pair into the set to handle the case when a
# subarray with the given sum starts from index 0
sub_array_indexes = {0: -1}
# keep track of the sum of elements so far
initial_sum = 0
# traverse the original array
for i in range(len(arr_)):
# update initial_sum
initial_sum += arr_[i]
# if `initial_sum - expected_sum` is seen before, we have found
# the subarray with expected_sum `expected_sum`
if (initial_sum - expected_sum) in sub_array_indexes:
print("subarray found between indexes (inclusive): ", (sub_array_indexes.get(initial_sum - expected_sum) + 1, i))
return
# insert (current sum, current index) pair into the dictionary
sub_array_indexes[initial_sum] = i
print("no subarray found with the given sum has been found!")
if __name__ == '__main__':
# sample list of integers and expected sum value to test the max sub array sum
array_ = [15, 2, 4, 8, 9, 5, 10, 23]
sum_ = 23
findSubArrayTopDown(array_ ,sum_)
Complexity Analysis
Time complexity: O(N).
The space complexity of the hashing approach is O(N) because it takes a linear space. This is the case if an array is used in hashing.
Auxiliary space: O(N).
The space complexity is linear because a HashMap is needed. An afterthought here, is to find out if we can further optimize this further so that we can use a constant space. And the answer in this scenario is YES.
Optimized Function to find a SubArray of a given Sum
# An efficient program to print subarray
# with sum as given sum
# Returns true if there is a subarray
# of arr[] with sum equal to 'sum'
# otherwise returns false & prints
# the result.
def subArraySumOpt(arr_, expected_sum):
# Initialize curr_sum as value of first element
# and starting point as 0
n = len(arr_)
curr_sum = arr_[0]
start = 0
# Add elements one by one to curr_sum and
# if the curr_sum exceeds the sum, then remove
# starting element
i = 1
while i <= n:
# If curr_sum exceeds the expected_sum,
# then remove the starting elements
while curr_sum > expected_sum and start < i - 1:
curr_sum = curr_sum - arr_[start]
start += 1
# If curr_sum becomes equal to sum,
# then return true
if curr_sum == expected_sum:
print("subarray sum found between indexes (inclusive): %% d and %% d" %% (start, i - 1))
return 1
# Add this arr_[i] to curr_sum
if i < n:
curr_sum = curr_sum + arr_[i]
i += 1
# If at this point there is no subarray
print("No subarr_ay found")
return 0
# main function to test subArraySumOpt program
if __name__ =='__main__':
arr = [15, 2, 4, 8, 9, 5, 10, 23]
expected_sum = 23
subArraySumOpt(arr, expected_sum)
Complexity Analysis
Time Complexity : O(N).
A single traversal is needed to cover the entire array. So the time complexity is O(n) because there are no multiple loops.
Space Complexity: O(1).
There is no extra space required, thus we say the space complexity is constant.
Conclusion
The problem of finding a subarray with a given sum refers to an array within the main array that adds up to the given sum. This is what we are calling the subarray. The subarray is contiguous to mean that the elements of this subarray are consecutive to each other.
In our solutions, we have addressed various approaches, the first being the brute-force which is slow. We then moved on to a better optimized brute-force approach before deploying the dynamic programming approach which is a better solution overall.
Finally, we optimized this dynamic approach to have a better computation memory. Also, note our illustration to identify that we can use dynamic programming in a particular problem and the necessary steps to accomplish this.
