C++ 4 lines solution using math, 6 lines solution using for loop, Both 0ms


  • 7
    L

    Based on math, the kth element for nth row is C(n, k) = n! / (k!*(n-k)!), then res[k] = res[n - k]

    so the relationship between res[i] and res[i-1] is n! / (k!(n-k)!) / n! / ((k-1)!(n-k + 1)!) = (n - k + 1) / k;

     vector<int> getRow(int rowIndex) {
       vector<int> res(rowIndex + 1, 1);
       for(int k = 1; k <= (rowIndex + 1)/2; k++)
            res[k] = res[rowIndex - k] = (long)res[k - 1]*(long)(rowIndex - k + 1)/k;
       return res;
    }
    

    // normal loop

    vector<int> getRow(int rowIndex) {
        vector<int> res;
        for (int i = 0; i <= rowIndex; i++) {
            res.push_back(1);
            for (int j = i - 1; j >= 1; --j) res[j] = res[j] + res[j-1];
        }
        return res;
    }

Log in to reply
 

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