(Throughout this article I will be using the terms list and array interchangeably. The Python list type is called an array in many other programming languages)
Summing an array can be done in many ways. In Python we can use a for...in loop. We even have a built in sum function we can use to sum an array. These solutions work perfectly for a 1D array, but how can we sum a 2D array? Let's break this problem into smaller pieces and solve it.
Today we are going to solve two problems—summing an array and any of its nested arrays
First, let's sum an array:
sum([1,2,3,4,5])
# 15
Well that was easy! This helper function provides an easy way to sum all values, but what is the sum function actually doing? Something like this maybe?
def sumOfArray(array):
sumTotal = 0
for number in array:
sumTotal += number
return sumTotal
Each number in the array will be added to the current sumTotal and then we set that value as the new sumTotal.
After we finish iterating, we return the sumTotal. We've accomplished the first step of our goal! Now on to the next step, summing any arrays within our array.
But wait a second, haven't we already figured out how to sum an array? Let's write out the problem in pseudo-code
Currently, we have figured out this much:
def sumArrayofArrays(array):
# create variable to hold sum of array (`sumTotal`)
# iterate through array and add each number to the sum
# return the sum
We know this function will sum an array, so how can we call it on each nested array?
Number or Array?
Right now in our loop, we're calling our variable number, but we know it may not always be a number. For example, if this is our array:
array = [1,2,3,[4,5]]
array[0] # 1 - Number
array[1] # 2 - Number
array[2] # 3 - Number
array[3] # 4 - Array
The 3rd position in our example is a list type! Let's update our loops variable name in order to be more accurate. Let's use element.
def sumOfArray(array):
sumTotal = 0
for element in array:
sumTotal += element
return sumTotal
We now know an element can either be a list or int type. If an element is an int we want to add it to the sumTotal which we're currently doing, but is there a way to check if an element is a list?
Type()?
In Python, we can determine the type of anything by using the type function.
type(3) # <class 'int'>
type([]) # <class 'list'>
type(type) # <class 'type'>
The type function will allow us to check if an element is a list. Let's add that check to our function!
def sumOfArray(array):
sumTotal = 0
for element in array:
if type(element) is list:
# do something
else:
sumTotal += element
return sumTotal
The Final Piece
Whenever we reach a list in our array, we know we want to sum all values within that our nested arrays, but how can we do this?
Well, we've already defined a function that can iterate through a list and return it's sum, so we can call our sumOfArray function recursively and solve our problem outright!
def sumOfArray(array):
sumTotal = 0
for element in array:
if type(element) is list:
sumTotal += sumOfArray(list)
else:
sumTotal += element
return sumTotal
Now that we've defined our function and walked through the process used to create it, let's take a look, step by step and look at what is happening on each line. I know that I find it so much easier to conceptualize and visualize code execution by stepping through the code line by line. Using a debugger or getting a pen and paper tend to be the most helpful for me.
Let's take a simple example incorporating an array with a number and a nested array.
# array = [1, [2]]
We'll use VSCode's built-in Run and Debug tab and take it step by step and explore the space and time complexity of our function.
On the left side of the screen we can see two important parts of our code execution. In the top left we can see how our variables change over time and in the bottom left we can see our call stack.
Ultimately, because we are going to access all values in the array, this means our Time Complexity is O(n) with n being the length of the array
Out Space Complexity is dependent on the max amount of calls we have on the call stack at a given time.
Every time we call a new function, it is put on the call stack. When the function finishes executing, we remove or "pop" it from the call stack. Each function call takes up space on the call stack.
This means for each array that has a nested array, we will call our sumOfArray function and add it to the call stack. This means the depth of the most nested array, which is directly related to the amount of sumOfArray function calls on the call stack, is our Space complexity.
For example:
# Each nested array pushes another `sumArray` function to onto the stack
firstArray = [1,[2]]
# Max Depth - 2
sumOfArray(firstArray)
# 3
# Time Complexity - O(n)
# Space Complexity - O(d) (Here 'd' is 2)
secondArray = [1,[2,[3]]]
# Max Depth - 3
sumOfArray(secondArray)
# 6
# Time Complexity - O(n)
# Space Complexity - O(d) (Here 'd' is 3)
Feel free to play around with code! Run it in your own local VSCode setup or even write out each step.
Recursion
To solve our problem we used a programming technique called recursion.
Recursion allows us to break our problem down into its smallest pieces, solve those smallest pieces, which will help us find our final result.
Every time an element is of type list , a new call to sumOfArray will be added to the stack
If a list has no nested arrays it will return it's sum.
If it has a nested array, when that array is reached during iteration, it will add another call to the stack.
This will repeat until we reach the most deeply nested array. Then as each call returns it's array's sum, each sumOfArray function on the stack will be popped off, eventually returning us the sum of all values in the original array and it's nested arrays.
I highly recommend using pen and paper and a simple input array to see exactly how recursion has helped us solve the our problem here. It can be a highly useful tool to help us solve problems like this, where it seems hard to find an iterative solution!
Top comments (0)