My Java solution using N-choose-K method.


  • 0
    Y

    I read the mathematical properties about Pascal's Triangle in this website

    http://www.mathsisfun.com/pascals-triangle.html

    enter image description here

    and I also derived that (N choose K) = (N choose K-1) * (n-k+1) / k. This avoids computing the factorial numbers which are larger than Integer.MAX_VALUE.

    public class Solution {
        
        private int nChooseK(long n, long k) {
            if(k == 0) return 1;
            return (int) (nChooseK(n, k-1) * (n-k+1) / k);
        }
    	
        public List<Integer> getRow(int rowIndex) {
            List<Integer> ret = new ArrayList<Integer>(rowIndex+1);
            for(int i = 0 ; i <= rowIndex ; i++) {
            	ret.add(nChooseK(rowIndex, i));
            }
            return ret;
        }
        
    }
    

  • 0
    G

    You might want to use some dynamic programming concept to improve the run time, since there are many duplicated calculations.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.