Original problem · C++ solution
Build Pascal rows from left and right parent entries while fixing both boundary entries to one.
Build Pascal rows from left and right parent entries while fixing both boundary entries to one. Keep the previous row intact until the next row is fully computed.
- Time: O(n^2).
- Extra space: O(n).
The types of operands control intermediate arithmetic. Read large values into long long before forming sums, products, or differences so the arithmetic itself uses 64 bits.
Integer division truncates toward zero; floor and ceiling formulas need special care for negative values.
State the invariant without looking at the code. Give one input that breaks the most tempting incorrect approach, then add it to the tests.