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
andjth 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!!
Top comments (0)