Summing an Array with Nested Arrays
Tags: python, algorithms
Published: 2021-01-26 15:04:34

(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:

```python
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?

```python
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:

```python
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:

```python
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`.

```python
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. 

```python
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!

```python
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!

```python
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.

```python
# 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.

{% youtube MC3MHLV761Q %}

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:

```python
# 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!