24. Pascal Triangle

The problem can be found at the following link: Question Link

My Approach

To generate the nth row of Pascal's Triangle, I optimize the simple brute force approach as follows:

• I initialize two vectors, out and prev, both of size n, with all elements set to 1.

• I iterate through each row, updating the elements of out based on the sum of the two corresponding elements from the prev vector.

• I also use modular arithmetic to prevent integer overflow.

• In each iteration, I update the out array with the values from the prev array.

Explain with Example

For example, let's generate the 5th row of Pascal's Triangle:

- Initialization: out = [1, 1, 1, 1, 1], prev = [1, 1, 1, 1, 1]
- After the first iteration, out = [1, 2, 1, 1, 1], prev = [1, 1, 1, 1, 1]
- After the second iteration, out = [1, 3, 3, 1, 1], prev = [1, 2, 1, 1, 1]
- After the third iteration, out = [1, 4, 6, 4, 1], prev = [1, 3, 3, 1, 1] which is the 5th row of Pascal Triangle.

Time and Auxiliary Space Complexity

• Time Complexity: O(n^2), where n is the number of rows.

• Auxiliary Space Complexity: O(n), as I use two vectors of size n.

Code (C++)

class Solution {
public:
    int mod = 1e9 + 7;

    vector<long long> nthRowOfPascalTriangle(int n) {
        vector<long long> out(n, 1), prev(n, 1);
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < i; ++j) {
                out[j] = (prev[j] + prev[j - 1]) % mod;
            }
            prev = out;
        }
        return out;
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.