Daily Coding Problem: Pascal’s Triangles and Space Complexity

Welcome back everyone with another problem to solve! It’s all about triangles lately, so today we’ll see a job interview problem that deals with Pascal’s triangles. We’ll first try to look at what they are, why they are so interesting and we’ll try to find some solutions to compute them.

First things first, the usual disclaimers:

• These problems are provided by the wonderful newsletter Daily Coding Problem, which you can subscribe to here. Check it out and try to solve your challenges too!

• I’m not an expert programmer: just a guy who likes to share his shots! If you happen to have a better or faster solution for an algorithm, please submit it in the comments! I’d love to learn more about this!

  
  

Without further ado, let’s see the problem.

This problem was asked by Stitch Fix and it goes like this:

Pascal’s triangle is a triangular array of integers constructed with the following formula:

The first row consists of the number 1.

For each subsequent row, each element is the sum of the numbers directly above it, on either side.

For example, here are the first few rows:

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

Given an input k, return the kth row of Pascal's triangle.

Bonus: Can you do this using only O(k) space?

This will probably be a long article, so feel free to skip around if you are already familiar with the concepts or if you are interested in a specific part.

Ready? Let’s go!

Pascal’s triangles

Formally speaking, a Pascal’s triangle is a particular triangular array, often used in statistics, combinatorics, and algebra. As the problem’s text states, building one is really simple:

• The first row contains a 1, like this: [ 1 ];

• The second row contains two 1s, like this: [ 1 1];

• In the following rows, the element j is built as the sum of the elements directly above j in the previous row, on its left and right sides. So for example, the second row, which is [1,1], will generate a 2 as the middle element in the third row. We keep doing this for each element in the triangle.

  
  

How come every line starts and ends with 1 then? To explain this we can imagine that where no element is present in the previous line, we count that as a 0. Then, if the 0 is on the left, we’ll have a starting 1, and where the 0 is on the right we’ll have a trailing 1.

Pascal’s triangles are a lot more than a simple game.

Here are some interesting properties:

• The second column from the left lists all the counting numbers;
• The third column from the left lists all the triangular numbers;
• The triangle is symmetrical;
• The sum of the elements of each row doubles from the previous one and it’s always a power of two;
• The elements of each row can be arranged to result as 11 to the power of that line number.

And many more. If you want some more about it, here are more properties explained!

And of course, this is a clear example of a tree: we could treat it as a binary tree and solve the problem by calculating each node. We won’t take this approach - although we will probably see it in another article.

We’ll see some array-based solutions instead, one iterative, one recursive and we’ll try to tackle the bonus question by building one that takes no other space than the solution array space to solve the problem.

As we often do, we’ll see algorithms written in Go, a really cool programming language with high performance and a quite understandable syntax.

Let’s see the solutions then!

The iterative solution

This solution is based on the use of a temporary array, which stores the results used while calculating the next line.

The function pascalTriangleIterative accepts an argument row , an integer equal to the desired row of the triangle.

Next, if row is equal to 1 or 2, the function simply returns [1] or [1,1].

After that, we define the out array, which will be returned at the end of the process. We can initiate it being equal to the second row, to limit the loops from the 3ʳᵈ row to the desired one.

We start the process, by defining a temporary array containing a 1: this will be the 1 at the start of the row. After that, we range over the out array, from the first to the second-last element, and start populating the temporary array: each element will be calculated as the sum of the element of outwe are on and the next one.

Obviously, we must range to the second-last element of out to avoid an IndexOutOfBound exception. After that, we simply add the 1 at the end, and start the outer loop again, setting out equal to the temporary array.

When n will be equal to the desired row number, we end the loop and return out.

The recursive solution

This solution takes a recursive approach, taking three arguments as follows:

• cnt , a counter to keep track of the loop we are on
• row , the row number we are interested in
• elements , the elements of the previous row

It goes as follows: we check if the cnt is lesser than the wanted row . If it’s not, we simply return the elements as it contains the solution (line 10).

If it’s not, then we create our temporary array temp and apply the same loop as the previous solution, taking elements as array for the loop. We append the final 1 and return another call to the function to keep the loop going until we reach the desired line.

Space complexity

Even if these solutions are ok, they take more than O(n) space, where n is the length of the final desired row. This is because while solving the problem we always implement a temporary array, which must be stored somewhere in memory until it’s destroyed or returned as solutions. This temporary array has always the length of the previous row. This gives our solutions a space complexity close to O(n + n-1) = O(2n-1). Still linear space, but we can do better.

No copies solution

Let’s try to implement a solution without copying the array. To do this we must modify the final array one step at a time, inserting the new elements and removing the previous ones.

Here’s my attempt:

Basically, the approach is really similar to what we have done before, but this time the function takes in the last line of the Pascal triangle just calculated, pascalLine , and directly modifies it.

The for loop in the middle simply loops over all the elements of the list and substitutes the current element with the sum of its value and the value of the next element. This is done up until the second-last element: again, to avoid IndexOutOfBound error. Since we substituted all the elements from range 0 to range n-1, we are now missing the starting 1 at the beginning of the array, which we can insert while returning the result.

There also is an if condition at the top: we check if the given pascalLine is equal to the first line of the triangle, containing only a 1: this is because we can not process that line, there are not enough elements to sum for our algorithm. We solve this by comparing pascalLine with []int{1} (an array containing a 1): if so, we return the second line of the triangle, containing two 1s ( []int{1,1} ).

Since the comparison of two arrays is not a primitive operation in Go, we also need to write a simple function to do so.

Here it is:

We can now use the pascalTriangle in our main function to obtain the line that we want, simply calling the function on a given initial array, like this:

Time and space complexity

Let’s start with time complexity: unluckily, with each solution, we are stuck with O(n²) time because:

• We must loop over the array to calculate the sums: the array has n elements and to loop over we are stuck with O(n) time;

• We must loop over n arrays to get to the nᵗʰ row, which takes O(n) time.

  
  

Basically, we are looping over n arrays n times, which gives us a time of O(n²).

Now for space complexity: this last solution is actually better than the other two. We do not use any temporary array or copy of it to store the results: instead, we directly modify the original array. So, at each run, the array will always have length n. This means that our algorithm will use linear space relative to the length of the triangle line we want to obtain, plus some constant time to check conditions and other stuff. Also, in the last line, we are basically summing two arrays ( return append([]int{1},pascalLine... ): don’t get fooled by this! The first array simply serves a container for the initial 1, so it will always take constant space O(1).

Conclusions

Here are my solutions. I’m also working on a tree-based solution, so we’ll catch up shortly with another article about this!

I hope you liked the article and found it interesting: if so, please leave a like or two, it will definitely make my day!

And, as always, thanks for reading.

Nicola