Here is my O(n) solution and the proof


  • 10
    C

    the mth element of the nth row of the Pascal's triangle is C(n, m) = n!/(m! * (n-m)!)

    C(n, m-1) = n!/((m-1)! * (n-m+1)!)

    so C(n, m) = C(n, m-1) * (n-m+1) / m

    In additional, C(n, m) == C(n, n-m)

      class Solution {
        public:
            vector<int> getRow(int rowIndex) {
                vector<int> row;
                if(rowIndex < 0) {
                	return row;
                }
                row.resize(rowIndex + 1);
                row[0] = row[rowIndex] = 1;
                for(int m =1; m < rowIndex /2 + 1; m++) {
                	row[m] = row[rowIndex - m] = ((long long int)row[m - 1] * (rowIndex - m + 1)) / m;
                }
                return row;
            }
        };

  • 4
    S

    I had similar idea but in Java. O(n) time and O(1) space.

    public class Solution {
        public List<Integer> getRow(int rowIndex) {
            List<Integer> resultList = new ArrayList<Integer>();
            if (rowIndex==0){
                resultList.add(1);
                return resultList;
            }
            
            int num = rowIndex/2;
            long temp = 1; // Some test cases have numbers larger than Integer.MAX_VALUE
            resultList.add((int)temp);
            
            // Compute first half using C(n, m) = C(n, m-1) * (n-m+1) / m;
            for(int i = 1; i<=num; i++){
                temp*=rowIndex-i+1;
                temp/=i;
                resultList.add((int)temp);
            }
            
            // Mirror the second half
            for(int i = (rowIndex-1)/2; i>=0; i--){
                resultList.add(resultList.get(i));
            }
            
            return resultList;
        }
    }

  • 0
    A

    Very good formula deriving. It's actually also shown in wikipedia Pascal Triangle entry.

    Here is the C version:

    int *getRow(int rowIndex, int *returnSize) {
        // For row n, the k th element, the entry is the product of its previous entry and (n  + 1 - k)/k.
        *returnSize = rowIndex + 1;
        int *row = malloc(*returnSize * sizeof(int));
        
        int k = 0;
        row[k] = 1;
        
        while (++k < *returnSize) {
            row[k] = (unsigned long long)row[k - 1] * (*returnSize - k) / k;
        }
        
        return row;
    }
    

Log in to reply
 

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