Gowthaman Ravi
Gowthy's Blog

Gowthy's Blog

Dynamic Programming | Pascal's Triangle II

Gowthaman Ravi's photo
Gowthaman Ravi
·Jan 26, 2022·

Subscribe to my newsletter and never miss my upcoming articles

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

LEETCODE GIF.gif

Example 1: Input: rowIndex = 3 Output: [1,3,3,1]

Example 2: Input: rowIndex = 0 Output: [1]

Example 3: Input: rowIndex = 1 Output: [1,1]

Constraints: 0 <= rowIndex <= 33

Java Solution

public class Solution {
    public List<Integer> getRow(int k) {
        Integer[] arr = new Integer[k + 1];
        Arrays.fill(arr, 0);
        arr[0] = 1;

        for (int i = 1; i <= k; i++) 
            for (int j = i; j > 0; j--) 
                arr[j] = arr[j] + arr[j - 1];

        return Arrays.asList(arr);
    }
}

C++ Solution

class Solution {
public:
    int a[34]={1}, b[34]={1};
    vector<int> getRow(int n) {
         int a[n+1];
         int b[n+1];
        vector<int> ans;
         for(int i=0;i<=n;i++){
             a[i]=1;
             b[i]=1;
         }

        for( int i=0;i<n;i++){
            for(int j=1;j<=i;j++){
                b[j]= a[j-1]+a[j];
            }

            for(int j=1;j<=i;j++){
                a[j]= b[j];
            }

        }
        for(int i=0;i<=n;i++){
            ans.push_back(a[i]);
        }
        return ans;
    }
};
 
Share this