Pascal’s Triangle II Problem in Leet Code
A proposed solution for a programming problem from Leet Code.
Introduction
If you ever participated of a coding interview, you probably had these brain teaser problems from websites like leetcode.com.
I have been looking at those and trying to solve some of them. Let me tell you why:
- I want to brush up my skills in problem solving: Learning how to solve problems that look like simple, but are actually brain twisters will keep me sharp and give me many new ways to look at a new problem when I face one.
- Expand my coding comfort zone: when we are working on our routine, there’s little time to go back to basics — such as loops, built-in functions — or learn new skills — like recursion, dynamic programming etc. As Data Scientists, probably we are too focused in Pandas, SkLearn, Numpy… you name it.
- Keep alert for new opportunities from the big tech companies, as they love those kinds of problems during coding interviews.
So, today, the daily problem in Leet Code was the Pascal’s Triangle II. Let’s learn more about the problem and follow with a solution.
The Problem
The description can be seen in this link and is as follows:
Given an integer
rowIndex, return therowIndexth(0-indexed) row of the Pascal's triangle.In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:
And then the problem input is a row number and you must return the numbers from that row in an array. For example, if we get rowIndex == 0 , we return [1]. For rowIndex == 2 , we return [1,2,1].
Understanding the Problem
Some videos that have been helping me a lot to learn how to approach these kinds of problems (and actually how to look at problems in general) is the Neet Code channel on Youtube.
In that channel, I have learned that the first step is to spend some time to actually understand the problem. Deeply understand. So, here, get your good old pen and paper and draw some simple cases. See how your brain solves the problem for each simple step. What actions are you taking to solve each little part of the problem.
That might sound like boring or a waste of time, but it is not. Those little parts are actually what you’ll be coding next.
So, here is how I looked at the problem.
- I know that the first level, the
rowIndex == 0is always 1. It does not need to be calculated, because it is the root of the triangle. It is the starting point. So, if I am asked about the first level, the answer is just[1]. - Then, the second level, at
rwoIndex == 1, there is apparently no sum yet. It’s just[1,1]. Should I hard code that one too? Maybe yes, maybe not. Let’s keep going. - When we go to the
rowIndex == 2, then we start to see some additions. The number 2 is the result of the sum of the two number ones in the prior level. So, how did we get the 1 and 1 on the prior level? - There is one catch to solve this problem. The ones come from the sum of 1 + 0. And so are all the other ones on the edges of the triangle. You must add 1+0 on every beginning and end of each level.
5. Finally, the additions are always made by pairs. Two numbers at a time, from the previous level.
Great. Problem understood. Let us code that now.
Coding
When coding the solution, we must apply the same steps as we did when we were understanding the problem. So let’s do that.
- The first level is hard coded. The starting point.
#First level will always be [1]
if rowIndex == 0:
return [1]Steps 2 to 5.
When the rowIndex is greater than 0, then we set up the level=1 (since we already know the result on level 0) and give the first level to the function.
#Starting point
level=1
# Define first level
lvl = [1]Now we will loop through the levels to calculate each one of them until the one we want as the final result. While the level number is within the number of levels we want, we keep looping.
Then we apply step 4, which is the addition of a zero on the edges of the current level. Next, we open a list to hold the next_level numbers and open an inner for loop that will go through each element in the current level making the sum of each pair of numbers.
Finally, we add one to the level variable, just so our while loop can achieve the ending condition and we reset the current level as the next level we have just calculated, so we’re ready for the next calculation, if needed.
while level <= rowIndex:
lvl.insert(0,0) #[0,1]
lvl.insert(len(lvl),0) #[0,1,0]
next_lvl = []
for n in range( len(lvl)-1 ):
element = lvl[n] + lvl[n+1]
next_lvl.append(element) # [1,1]
level +=1
lvl = next_lvl # [1] reassigned with [1,1]The entire function is here:
class Solution(object):
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
#First level will always be [1]
if rowIndex == 0:
return [1]
level=1
# Define first level
lvl = [1]
while level <= rowIndex:
lvl.insert(0,0) #[0,1]
lvl.insert(len(lvl),0) #[0,1,0]
next_lvl = []
for n in range( len(lvl)-1 ):
element = lvl[n] + lvl[n+1]
next_lvl.append(element) # [1,1]
level +=1
lvl = next_lvl # [1] reassigned with [1,1]
return lvlResult
Here is my final result, in terms of performance of the code.
Well, I am fairly satisfied with it. The solution beats 65% of the other users, however the memory usage is not the best.
For sure it can be optimized. Maybe you can try it…
Before You Go
I hope this post was helpful for you to learn a couple of tricks to approach a programming problem.
This problem is an EASY one in the platform, and I might add that there are some others, even the easy ones, that are much harder to come up with a solution. So don’t feel discouraded if you don’t see it at first. Keep trying and studying.
Some topics I think that can help, that I also have in my to do list are: Backtracking, Recursion, Trees, Dynamic Programming.
If you liked this post, don’t forget to follow my blog for more.
You can find me on LinkedIn as well.
