Pascal's Triangle II with O(1) space


  • 6
    C

    I got an answer with O(1) space.

    The idea is that, for n-th row, the value at col j is (n,j) (I mean n choose j here).
    And we have (n,j) = (n, j-1) * (n-j+1) / j.

    Then we can have the solution as below:

    class Solution {
    public:
        vector<int> getRow(int rowIndex) {
            vector<int> res;
            if (rowIndex >= 0) {
                res.push_back(1);
            }
            for (int j = 1; j <= rowIndex; j++) {
                res.push_back((double)res.back() * (double)(rowIndex - j + 1) / (double)j);
            }
            return res;
        }
    };
    

    One further question I'm wondering is, is it possible eliminate type cast here (which was to avoid overflow)?


  • -8
    I

    It's not O(1). You return a vector<int> which takes up space of O(k), don't you?
    Also, you might do the division first then multiplication.


  • 0
    C

    I mean extra space, the return vector is a must.
    What's the benefit of division fist?


  • 0
    I

    Say, consider the following four-byte-long ints.
    int main()
    {
    int a = 1 << 30, b = 1 << 30, c = 1 << 30;
    cout << a * b / c << endl;
    cout << a * (b / c) << endl;
    }


  • 0
    C

    If you do want to use int, do division first may also suffer. e.g.
    int main() { int a = 2, b = 1, c = 2; cout << a * b / c << endl; cout << a * (b / c) << endl; }


  • 0
    I

    yes. you are totally right. kinda numeric error.


  • 0
    O

    The arithmetic operation on floating-point numbers are not inaccurate. Will this cause problems?


  • 0
    F

    I think (long long) is better than (double) since double is not precise.


  • 0
    J

    How do you prove it is correct?


  • 0
    V

    multiplying first might cause overflow problem but it assures that the Dividend is always a multiple of divisor.


  • 0
    G

    This is correct. Try to go to the first principle and generate the row. You can find the same pattern used here.
    One suggestion, run time can be further improved by not doing calculation in the second half of the vector, but simply copying previous elements accordingly.


Log in to reply
 

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