Join us

@alexmurphas8 ・ Sep 01,2022 ・ 2 min read ・ 215 views

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,

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.

Join other developers and claim your FAUN account now!

Influence

Total Hits

Posts

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