Nth row of Pascal’s Triangle

Given an index n(indexing is 0 based here), find nth row of Pascal's triangle.

Examples:
Input : 2
Output : [1, 2, 1]
According to 0 based indexing, 2nd row contains: 1, 2, 1 
Input : 4
Output : [1, 4, 6, 4, 1]
Similarly 4th row contains: 1, 4, 6, 4, 1

Naive Approach:
Each element of nth row in pascal’s triangle can be represented as: nCi, where i is the ith element in the row.

Pascal’s Triangle

So elements in 4th row will look like: 4C0, 4C1, 4C2, 4C3, 4C4. Using this we can find nth row of Pascal’s triangle.
But for calculating nCr formula used is:

C(n, r) = n! / (r! (n-r)!)

Calculating nCr each time increases time complexity. Also, n! may overflow for larger values of n.

Efficient Approach:
We can find (i+1)th element of row using ith element.
Here is formula derived for this approach:

C(n, i) = n! / (i! (n-i)!) — — — — — — Equation 1
C(n, i+1) = n! / ((i+1)! (n-(i+1))! ) — — — — — — Equation 2
Dividing equation 2 by 1 will give:
C(n, i+1) / C(n, i) = i! (n-i)! / (i+1)! (n-i-1)!
Solving this we get:
C(n, i+1) = C(n, i) * (n-i) / (i+1)

So we can get (i+1)th element of each row with the help of ith element.
Let us find 4rd row of Pascal’s triangle using above formula.

4C0 = 1 // For any non-negative value of n, nC0 is always 1
4C1 = 4C0 * (4–0) / (0+1) = 4
4C2 = 4C1 * (4–1) / (1+1) = 6
4C3 = 4C2 * (4–2) / (2+1) = 4
4C4 = 4C3 * (4–3) / (3+1) = 1

Here we need not to calculate nCi even for a single time.

Source code in java:

import java.util.*;
import java.lang.*;
import java.io.*;
class PascalTriangle{
   // This method will return ArrayList containing nth row 
   public static ArrayList<Integer> nthRow(int N)
   {
       ArrayList<Integer> res = new ArrayList<Integer>();
       // Adding 1 as first element of every row is 1
       res.add(1);
       for (int i = 1; i <= N; i++) {
           res.add(i, (res.get(i — 1) * (N — i + 1)) / (i));
       }
       return res;
   }

   public static void main(String[] args) throws java.lang.Exception
   {
       int n = 4;
       System.out.println(nthRow(n));
   }
}

Complexity analysis:
Time Complexity : O(n)
Space Complexity : O(n)