LeetCode 119. Pascal’s Triangle II (solution with images)

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 problemLeetCode 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/