Find Kth row of Pascal's Triangle
You are given a non-negative integer 'K'. Your task is to find out the Kth row of Pascal’s Triangle.

In Mathematics, Pascal's triangle is a triangular array where each entry of a line is a value of a binomial coefficient. An example of Pascal’s triangle is given below.

Example :-

INPUT : K = 2 OUTPUT: 1 1 In the above example, K = 2, Hence the 2nd row from the top of pascal’s triangle, as shown in the above example is 1 1. INPUT : K = 4 OUTPUT : 1 4 6 4 1 In the above example, K = 4, Hence the 4th row from the top of pascal’s triangle, as shown in the above example is 1 3 3 1.

Input Format

The first line of input contains an integer 'T' representing the number of the test case. Then the test case follows. The first and the only line of each test case contains a single integer “K”.

Output Format:

For every test case, print a single line containing 'R' space-separated integers showing the Kth row of pascal’s triangle, where 'R' is the number of elements in a particular row. The output of each test case will be printed in a separate line.

Note

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Find Kth row of Pascal's Triangle

You are given a non-negative integer 'K'. Your task is to find out the Kth row of Pascal’s Triangle.

In Mathematics, Pascal's triangle is a triangular array where each entry of a line is a value of a binomial coefficient. An example of Pascal’s triangle is given below.

example

Example :-

INPUT : K = 2
OUTPUT: 1 1

In the above example, K = 2, Hence the 2nd row from the top of pascal’s triangle, as shown in the above example is 1 1.

INPUT   : K = 4
OUTPUT  : 1 4 6 4 1

In the above example, K = 4, Hence the 4th row from the top of pascal’s triangle, as shown in the above example is 1 3 3 1.

Input Format

The first line of input contains an integer 'T' representing the number of the test case. Then the test case follows.

The first and the only line of each test case contains a single integer “K”.

Output Format:

For every test case, print a single line containing 'R' space-separated integers showing the Kth row of pascal’s triangle, where 'R' is the number of elements in a particular row.

The output of each test case will be printed in a separate line.

Note

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
1 <= K <= 50

Where ‘T’ is the number of test cases, ‘K’ is the input row number.

Time limit: 1 sec.

Accepted Answer

Naive Approach

In this approach, we find the row elements of the previous row using recursion, and based on the values of previous row elements, we will evaluate the current row elements.

We are given a function kthRow() which takes an integer ‘K’ as the only parameter and returns an integer vector. This is the definition of our recursive function too.
As the base condition of our recursive function, we will check if ‘K’ is equal to 1 or not. If ‘K’ is 1, we will return the vector containing 1.
Now we will call our recursive function kthRow() with K - 1 as our new parameter to store the previous row elements.
Now by adding the previous row elements, we will find the current row elements and then return the current row.

Space Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the input row index.

We are taking a vector and doing recursive calls so total space taken will be of the order of (N * (N - 1)) / 2. Hence the worst-case space complexity will be O(N ^ 2).

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the input row index.

Due to recursive calls, we are doing work in the order of (N * (N - 1)) / 2. Hence our worst-case time complexity is O(N ^ 2).

Java (SE 1.8)

/*

    Time Complexity: O(N ^ 2).

    Space Complexity: O(N ^ 2).



    Where 'N' is the input row index.

*/



import java.util.ArrayList;



public class Solution {

	public static ArrayList kthRow(int k) {



		ArrayList currentRow = new ArrayList<>();

		

		// First element of each row.

		currentRow.add((long) 1);



		// Base condition.

		if (k == 1) {

			return currentRow;

		}

		// Recursive call.

		ArrayList previousRow = kthRow(k - 1);



		// Evaluate current row with the help of previous row.

		for (int i = 1; i < previousRow.size(); i++) {

			long temp = previousRow.get(i - 1) + previousRow.get(i);

			currentRow.add(temp);

		}



		currentRow.add((long) 1);

		return currentRow;

	}

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N ^ 2).

    Space Complexity: O(N ^ 2).



    Where 'N' is the input row index.

*/



vector kthRow(int k) 

{ 

    vectorcurrentRow; 

    // First element of each row.

    currentRow.push_back(1);                                  

    // Base condition.

    if (k == 1) 

    {                                             

        return currentRow;  

    } 

    // Recursive call.

    vector previousRow = kthRow(k - 1);        

 

    for(int i = 1; i < previousRow.size(); i++)

    {              

        // Evaluate current row with the help of previous row.

        long long int temp = previousRow[i - 1] + previousRow[i]; 

        currentRow.push_back(temp); 



    } 



    currentRow.push_back(1); 

     

    return currentRow; 

}

Python (3.5)

'''

    Time Complexity: O(N ^ 2).

    Space Complexity: O(N ^ 2).



    Where 'N' is the input row index.

'''



def kthRow(k):

    

    currentRow = []

    # First element of row.

    currentRow.append(1)

    # Base case.

    if k == 1 :

        return currentRow

    

    # Recursive call.

    previousRow = kthRow(k - 1)

    

    for i in range (1, len(previousRow)):

        # Evaluate current row with the help of previous row.

        temp = previousRow[i - 1] + previousRow[i]

        currentRow.append(temp)

        

    currentRow.append(1)

    

    return currentRow

Accepted Answer

Dynamic Programming

In this approach, we will build our solution in the bottom-up manner storing the results in a 2D array “DP”.

We are given a function kthRow() which takes an integer ‘K’ as the only parameter and returns an integer vector.
Initialize a vector “RESULT” to store the final result.
Initialize a 2D integer array “DP” with both rows and columns equal to ‘K’.
Now in a nested loop, we will build our array “DP” using the bottom-up approach, forming the current element by adding values just above it.
Finally, add the final row elements of “DP” in the array “RESULT” and return it as our final answer.

Space Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the input row index.

As we are using a 2D array to “DP” to store our results, hence our space complexity is O(N ^ 2).

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the input row index.

As we are running a single loop and doing work of the order N ^ 2, our worst-case time complexity is O(N ^ 2).

Java (SE 1.8)

/*

    Time Complexity: O(N ^ 2).

    Space Complexity: O(N ^ 2).



    where 'N' is the input row index.

*/



import java.util.ArrayList;



public class Solution {

	public static ArrayList kthRow(int k) {



		ArrayList currentRow = new ArrayList<>();

		// First element of each row.

		currentRow.add((long) 1); 

		long[][] dp = new long[k][k];



		// Iterate through every line and adding integers in it.

		for (int line = 0; line < k; line++) {

            

			// Every line has number of integers equal to line number.

			for (int i = 0; i <= line; i++) {

				// First and last values in every row are 1.

				if (line == i || i == 0) {

					dp[line][i] = 1;

				}

				// Other values are sum of values just above and left of above.

				else {

					dp[line][i] = dp[line - 1][i - 1] + dp[line - 1][i];

				}

			}

		}

		// Base condition.

		if (k == 1) { 

			return currentRow;

		}

		for (int i = 1; i < k; i++) {

			currentRow.add(dp[k - 1][i]);

		}



		return currentRow;

	}

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N ^ 2).

    Space Complexity: O(N ^ 2).



    where 'N' is the input row index.

*/



vector kthRow(int k) 

{ 

    vectorresult; 

    // First element of each row.

    result.push_back(1);                            



    long long int DP[k][k]; 



    // Iterate through every line and add integers.

    for(int i = 0; i < k; i++)

    {       

		               

        for(int j = 0; j <= i; j++)

        {

            // First and last values of every row is 1.

            if(i == j || j == 0)

            {                      

                DP[i][j] = 1;                      

            }



            else

            {

                DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j];

            }

        }



    }

    // Base condition.

    if(k == 1) 

    {                                   

        return result;

    }



    for(int i = 1; i < k; i++)

    {

        result.push_back(DP[k - 1][i]);

    }



    // Returning answer.

    return result;                               

}

Python (3.5)

'''

    Time Complexity: O(N ^ 2).

    Space Complexity: O(N ^ 2).



    Where 'N' is the input row index.

'''



def kthRow(k):

    

    currentRow = []

    # First element of row.

    currentRow.append(1)

    

    dp =[[0 for j in range (k)]for i in range (k)]

    

    # Iterate through every line and adding integers in it.

    for line in range (k):

        

        # Every line has number of integers equal to line number.

        for i in range (line + 1):

            # First and last values will be 1.

            if line == i or i == 0:

                dp[line][i] = 1

            # Other values are sum of values just above and left of above.

            else:

                dp[line][i] = dp[line - 1][i - 1] + dp[line - 1][i]

                

    if k == 1:

        return currentRow

    

    for i in range (1, k):

        currentRow.append(dp[k - 1][i])

        

    return currentRow

Accepted Answer

Dynamic Programming - Space optimized

We are given a function kthRow() which takes an integer ‘K’ as the only parameter and returns an integer vector.
Initialize a vector “RESULT” to store the final result.
Initialize two arrays of size K, as “PREVROW” and “CURRROW” to store previous row and current row of the triangle.
Now in a nested loop, we will build our array “CURRROW” using the bottom-up approach, forming the current element by adding values of “PREVROW”.
Finally, add the final row elements of “CURRROW” in the array “RESULT” and return it as our final answer.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the input row index.

As we are creating extra arrays of size N, hence our space complexity is O(N).

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the input row index.

As we are running a single loop and doing work of the order N ^ 2, our worst-case time complexity is O(N ^ 2).

C++ (g++ 5.4)

/*

    Time Complexity: O(N ^ 2).

    Space Complexity: O(N).



    where 'N' is the input row index.

*/



vector kthRow(int k) 

{ 

    vectorresult; 

    // First element of each row.

    result.push_back(1);                            



    long long int prevRow[k];

    long long int currRow[k]; 



    // Iterate through every line and add integers.

    for(int i = 0; i < k; i++)

    {                      

        for(int j = 0; j <= i; j++) 

        {



            // First and last values of every row is 1.

            if(i == j || j == 0)

            {                      

                currRow[i] = 1;                     

            }

            // Current value is sum of values at ith and i-1th index of prevRow.

            else

            {

                currRow[j] = prevRow[j - 1] + prevRow[j]; 

            }                                             

        }



        // Storing current row in previous row.

        for(int i = 0; i < k; i++){                  

            prevRow[i] = currRow[i];               

        }



    }

    // Base condition.

    if(k == 1)

    {                                   

        return result;

    }



    for(int i = 1; i < k; i++)

    {

        result.push_back(currRow[i]);

    }



    // Returning answer.

    return result;                               

}

Java (SE 1.8)

/*

    Time Complexity: O(N ^ 2).

    Space Complexity: O(N).



    where 'N' is the input row index.

*/



import java.util.ArrayList;



public class Solution {

	public static ArrayList kthRow(int k) {



		ArrayList kthRow = new ArrayList<>();

		// First element of each row.

		kthRow.add((long) 1); 



		long[] prevRow = new long[k];

		long[] currRow = new long[k];



		// Iterate through every line and add integers in it.

		for (int line = 0; line < k; line++) {



			for (int i = 0; i <= line; i++) {

				// First and last values in every row are 1.

				if (line == i || i == 0) {

					currRow[i] = 1;

				}

				// Other values are sum of values at ith and i-1th index of prevRow.

				else {

					currRow[i] = prevRow[i - 1] + prevRow[i];

				}

			}

			prevRow = currRow.clone();

		}

		// Base condition.

		if (k == 1) { 

			return kthRow;

		}

		for (int i = 1; i < k; i++) {

			kthRow.add(currRow[i]);

		}



		return kthRow;

	}

}

Python (3.5)

'''

    Time Complexity: O(N ^ 2).

    Space Complexity: O(N).



    Where 'N' is the input row index.

'''



def kthRow(k):

    

    result = []

    # First element of row.

    result.append(1)

    

    currRow = [0] * k

    prevRow = [0] * k

    

    # Iterate through every line and adding integers in it.

    for line in range (k):

        

        # Every line has number of integers equal to line number.

        for i in range (line + 1):

            # First and last values will be 1.

            if line == i or i == 0:

                currRow[line] = 1

            # Other values are sum of values just above and left of above.

            else:

                currRow[i] = prevRow[i - 1] + prevRow[i]

                

        prevRow = currRow.copy()

            

        

    if k == 1:

        return result

    

    for i in range (1, k):

        result.append(currRow[i])

        

    return result

Accepted Answer

Efficient Approach

In this approach, we will try to observe the pattern and make the sequence for the current row elements. We can clearly see that the Kth row of pascal’s triangle has the sequence : C(K, 0), C(K, 1), ..., C(K, K - 1), C(K, K), where C(N, R) is the binomial coefficient or Combination function. As C(K, 0) = 1, we can evaluate other values of the sequence by the formula, C(N, R) = (C(N, R - 1) * (N - R )) / R .

We are given a function kthRow() which takes an integer ‘K’ as the only parameter and returns an integer vector.
We will store the value of the first coefficient, i.e C(K, 0) or 1 in a variable “PREV”. This variable will be used to store all the previous coefficient values
Then in the loop, until we reach K, we will evaluate the value of each element of the Kth row and store it in the vector “ROWVECTOR”, simultaneously storing the current value in “PREV” for further use.
Finally, we will return “ROWVECTOR” as our answer.

Space Complexity: O(1)Explanation:

O(1).

As we are not using any extra space, our space complexity is O(1).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the input row index.

As we are running a single loop up to ‘N’, so our worst-case time complexity is O(N).

Java (SE 1.8)

/*

    Time Complexity: O(N).

    Space Complexity: O(1).



    where 'N' is the input row index.

*/



import java.util.ArrayList;



public class Solution {

	public static ArrayList kthRow(int k) {



		ArrayList currentRow = new ArrayList<>();

		long prev = 1;



		// First element of row.

		currentRow.add(prev); 



		for (long i = 1; i < k; i++) {



			// Formula representation.

			long curr = (prev * (k - i)) / i; 

			

			// Adding the current row element.

			currentRow.add(curr); 

			prev = curr;

		}

        

		return currentRow;

	}

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N).

    Space Complexity: O(1).



    Where 'N' is the input row index.

*/



vector kthRow(int k) 

{

 

    vectorrow;



    long long int prev = 1;



    // First element of row.

    row.push_back(prev); 

 

    for (long long int i = 1; i < k; i++) 

	{



        // Formumala representation.

        long long int curr = (prev * (k - i)) / i; 

        // Adding the current row element.

        row.push_back(curr);             



        prev = curr;



    }



    // Return answer.

    return row;                         

}

Python (3.5)

'''

    Time Complexity: O(N).

    Space Complexity: O(1).



    Where 'N' is the input row index.

'''



def kthRow(k):

    

    currentRow = []

    # First element of row.

    prev = 1

    currentRow.append(prev)

    

    for i in range (1, k):

        # Formula representation.

        prev = (prev * (k - i)) // i

        # Adding the current row element.

        currentRow.append(prev)

        

    return currentRow

You are given a non-negative integer 'K'. Your task is to find out the Kth row of Pascal’s Triangle.

In Mathematics, Pascal's triangle is a triangular array where each entry of a line is a value of a binomial coefficient. An example of Pascal’s triangle is given below.

Example :-

Input Format

Output Format:

Note

Constraints:

Top Ola Cabs SDE-2 interview questions & answers

Popular interview questions of SDE-2