Link : → https://leetcode.com/problems/pascals-triangle-ii/
Problem: →
Given an integer rowIndex, return the rowIndexth (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:
Example 1:
Example 2:
Example 3:
Constraints:
0 <= rowIndex <= 33
Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?
Solution: →
We can easily solve this problem by getting reference from previous example like below,
LeetCode 118. Pascal’s Triangle
Those, who have not seen above example, please refer that one first.
In above problem, we need to find array of an array like below,
But over here, we just need to find a row array of given rowIndex.
First thing you can notice over here, that we need to append 1 in start and end position of row array.
We can achieve that by following way,
In previous problem LeetCode 118, we are creating rowArray as well, so it will be easy to do addition of previous row’s first two, second two’s additions,
Here, we just need to return only colArray, so we have taken only one array instead of two like previous leetcode, to reduce space complexity.
But, still we require previous row, so we can calculate addition of previous row’s elements.
To achieve that, we have taken one preList, which will keep record of previous array. So for every for loop, preList have previous array’s elements.
So, with use of preList, we can do addition and can append to current colList.
Such as,
At the end we just return preList, as for current iteration, preList is the current colList, for next iteration, colList will change.
Now, lets see full source code.
Code (Java): →
Code (Python): →
Time Complexity
Here, we have used two for loops, so total time complexity will be O(n²).
Space Complexity
Here, we have used only one array, other array is just for reference, so total space complexity will also be O(n).
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Thanks for reading this article ❤
If this article helps you, please clap 👏 this article.
Please follow me on medium, I will post useful information like above.
Instagram → https://www.instagram.com/alexmurphyas8/
Twitter → https://twitter.com/AlexMurphyas8
If I got something wrong? Let me in the comments. I would love to improve.
Share with your friends and followers
Start blogging about your favorite technologies, reach more readers and earn rewards!
Join other developers and claim your FAUN account now!
User Popularity
11
Influence
1k
Total Hits
1
Posts
Read, Learn, Know, Teach
Hand curated newsletters for Developers, private Slack with like minded people, podcasts, job offers, news and more!
Only registered users can post comments. Please, login or signup.