## DEV Community is a community of 894,881 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Vinit Gupta

Posted on

# Kth Row in Pascal Triangle x InterviewBit

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.

## 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<>();

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