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 . Check it out and try to solve your challenges too! here 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 , return the row of Pascal's triangle. Given an input k kth space? Bonus: Can you do this using only O(k) 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 . As the problem’s text states, building one is really simple: Pascal’s triangle is a particular triangular array, often used in statistics, combinatorics, and algebra 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 is built as the sum of the elements directly above 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. j j 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, more properties explained! here are And of course, this is a clear example of a : we could treat it as a and solve the problem by calculating each node. We won’t take this approach - although we will probably see it in another article. tree binary tree We’ll see some 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. array-based solutions As we often do, we’ll see algorithms written in , a really cool programming language with high performance and a quite understandable syntax. Go Let’s see the solutions then! The iterative solution This solution is based on the use of a , which stores the results used while calculating the next line. temporary array https://gist.github.com/NicolaM94/df7b4551a4e737a875a11b9d406fb35f?embedable=true#file-ptiterative-go The function accepts an argument , an integer equal to the desired row of the triangle. pascalTriangleIterative row Next, if is equal to 1 or 2, the function simply returns [1] or [1,1]. row After that, we define the 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. out 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 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 we are on and the next one. out out Obviously, we must range to the second-last element of out to avoid an exception. After that, we simply add the 1 at the end, and start the outer loop again, setting equal to the temporary array. IndexOutOfBound out When will be equal to the desired row number, we end the loop and return out. n The recursive solution https://gist.github.com/NicolaM94/25fd6adb19ddacb6233ae9ffab73e57b?embedable=true#file-ptrecursive-go This solution takes a recursive approach, taking three arguments as follows: , a counter to keep track of the loop we are on cnt , the row number we are interested in row , the elements of the previous row elements It goes as follows: we check if the is lesser than the wanted . If it’s not, we simply return the as it contains the solution (line 10). cnt row elements If it’s not, then we create our temporary array and apply the same loop as the previous solution, taking as array for the loop. We append the final and return another call to the function to keep the loop going until we reach the desired line. temp elements 1 Space complexity Even if these solutions are ok, they take more than O(n) space, where 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. n No copies solution Let’s try to implement a . To do this we must modify the final array one step at a time, inserting the new elements and removing the previous ones. solution without copying the array Here’s my attempt: https://gist.github.com/NicolaM94/7b7c30cf402f7f88429160fb729f8f8b?embedable=true#file-pascaltriangles-go 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, , and directly modifies it. pascalLine 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 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. IndexOutOfBound There also is an if condition at the top: we check if the given 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 with (an array containing a 1): if so, we return the second line of the triangle, containing two 1s ( ). pascalLine pascalLine []int{1} []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: https://gist.github.com/NicolaM94/4c0f2efedc57c120d3484caf7deb9c74?embedable=true#file-compareslices-go We can now use the in our main function to obtain the line that we want, simply calling the function on a given initial array, like this: pascalTriangle https://gist.github.com/NicolaM94/a5497f2215d02a91d8fbe222844409b9?embedable=true#file-main-go 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 elements and to loop over we are stuck with O(n) time; n We must loop over arrays to get to the nᵗʰ row, which takes O(n) time. n Basically, we are looping over arrays times, which gives us a time of O(n²). n 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 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 ( ): 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). n. return append([]int{1},pascalLine... 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 Also published here.

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

Read My Stories

Too Long; Didn't Read

Making security fun one episode at a time

Daily Coding Problem: Pascal’s Triangles and Space Complexity

Too Long; Didn't Read

People Mentioned

Nicola Moro

STORY’S CREDIBILITY

Guide

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

Daily Coding Problem: Pascal’s Triangles and Space Complexity

Too Long; Didn't Read

People Mentioned

Nicola Moro

STORY’S CREDIBILITY

Guide

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES