Today, the question is the `Kth Row of Pascal Triangle`

.

So what is a Pascal's triangle?

## Pascal's Triangle

It is of the most interesting Number Patterns in Mathematics (named after Blaise Pascal, a famous French Mathematician and Philosopher).

To build the triangle, start with "1" at the top, then continue placing numbers below it in a triangular pattern.

Each number is the numbers directly above it added together.

(Here I have highlighted that 1+3 = 4)

## Approach 1 : Brute Force

Some wise men said(as still they say), when asked in an interview, *always* go for the brute force approach first.

So, what is the brute force approach here? Well in terms of `time`

, there is always `O(N*N)`

complexity.

- Step 1 : Create a 2D list(Java/Python/Javascript) or a 2D vector(C++).
- Step 2 : Generate the first row i.e.
`[1]`

. - Step 3 : Consecutively, for each row add 1 as the first element and then for the
`ith row`

and`jth column`

value :

```
//(if j-1 exists)
list[i][j] = list[i-1][j-1] + list[i-1][j]
```

Then append another 1 at the end.

- Step 4 : Continue
**Step 3**`k times`

And now you have the kth row of the Pascal Triangle.

###
Complexity : Time - `O(N*N)`

, Space-`O(N*N)`

## Approach 2 : Space Optimized

As I said, in this question we cannot optimize the time.

So, as the same wise men said :

When you cannot optimize in terms of time, go for the next in line : SPACE

So, how can we optimize for space? Of course, instead of a 2D list, what if we can do the same in a 1D list?

What we can do here is, *instead of adding the new row to the 2D list, we can just replace the previous list*.

The code looks like this :

```
public ArrayList<Integer> getRow(int k) {
ArrayList<Integer> row = new ArrayList<>();
row.add(1);
int count = 1;
while(count<=k){
int i=0,j=i+1;
ArrayList<Integer> curr = new ArrayList<>();
curr.add(1);
while(i<row.size() && j<row.size()){
curr.add(row.get(i)+row.get(j));
i++;
j++;
}
curr.add(1);
row = curr;
count++;
}
return row;
}
```

Hope you have understood the solution.

For solutions of other InterviewBit questions, ππcheckout my Github Repo

Stay Tuned for more!!

## Discussion (0)