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:

                Input: rowIndex = 3
Output: [1,3,3,1]
            

Example 2:

                Input: rowIndex = 0
Output: [1]
            

Example 3:

                Input: rowIndex = 1
Output: [1,1]
            

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): →

                class Solution {
    public List<Integer> getRow(int rowIndex) {
        
        List<Integer> preList = null;
        for(int i = 0; i <= rowIndex; i++){
            
            List<Integer> colList = new ArrayList<>();
            for(int j = 0; j <= i; j++){
                if(j == 0 || i == j){
                    colList.add(1);
                }else{
                    colList.add(j, preList.get(j-1)+preList.get(j));                                 
                }
            }
            preList = colList;
        }
        return preList;
    }
}
            

Code (Python): →

                class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        preList = []
        
        for i in range(rowIndex+1):
            colList = []
            for j in range(i+1):
                        
                #First and last element is 1
                if j == 0 or j == i:
                    colList.append(1)
                else:
                    colList.append(preList[j-1]+preList[j])
            preList = colList
        return preList
            

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.


Only registered users can post comments. Please, login or signup.

Start blogging about your favorite technologies and get more readers

Join other developers and claim your FAUN account now!

Stats
12

Influence

208

Total Hits

1

Posts