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.

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!!