Pascal's triangle solution


  • 0
    M

    Each line in pascal's triangle can be computed from previous line: first and last elements are always '1' and other elements (let it index be i) are sum of two elements of previous line with inices i and i - 1.

         1
       1   1
        \+/
     1   2   1
      \+/ \+/
    1  3   3   1
    

    There is simple c++ implementation:

    vector<vector<int>> generate(int numRows) {
            vector<vector<int>> res(numRows);
            for (int i = 0; i < numRows; ++i) {
                res[i].push_back(1);
                for (int j = 1; j <= i; ++j) {
                    int el = (j == i) ? 1 : res[i-1][j-1] + res[i-1][j];
                    res[i].push_back(el);
                }
            }
            return res;
        }
    };
    

    For each line we compute k-2 elements, where k - current line number, from 2 elements of previous line in constant time plus get constants for first and last elements. Time complexity is O(n^2). Total number of elements is the sum of arithmetic progression, so for N rows number of elements is

    1+2+..+N = N(N-1)/2
    

Log in to reply
 

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