@meta
title: Pascal's Triangle
questionNo: 2
totalQuestions: 191
sheetLabel: Striver SDE Sheet
sourceLabel: TakeUForward
@endmeta

@page
tag: A
pageNo: 1 / 1
totalPages: 1
@endpage

@section
region: full
title: Problem Statement
content:
Given an integer numRows, generate the first numRows of Pascal's Triangle.
Each row starts and ends with 1, and every inner value is the sum of the two values directly above it.
If the interviewer asks only for one row, mention the nCr based variant too.
@endsection

@section
region: left
title: Examples
content:
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
Explanation: Every inner cell comes from previousRow[j - 1] + previousRow[j].
---
Input: numRows = 1
Output: [[1]]
Explanation: With one row, only the top of the triangle is returned.
@endsection

@section
region: right
title: Custom Notes
content:
- Boundary elements are always 1.
- Full triangle generation is naturally O(n^2).
- For a single row, nCr recurrence is the sharper answer.
- Memory hook: row by row, two parents build one child.
- Do not overuse factorials because they introduce overflow and repeated work.
@endsection

@section
region: full
title: Brute Force Approach : TC: SC:
badge: 1 / 3
content:
Algorithm: Compute each value separately using combinations nCr.
Pseudo:
- For every row i from 0 to numRows - 1:
- For every column j from 0 to i, compute iCj.
- Push the computed value into the current row.
Time: O(n^3) in a naive factorial or repeated multiplication style
Space: O(1) extra apart from answer
Why mention it: Good for showing mathematical understanding, but not the best construction approach.
@endsection

@section
region: full
title: Better Approach : TC: SC:
badge: 2 / 3
content:
Algorithm: Build the triangle row by row using the previous row.
Pseudo:
- Start with an empty answer.
- For each row i, create an array of size i + 1 filled with 1.
- For every inner index j from 1 to i - 1, set row[j] = ans[i - 1][j - 1] + ans[i - 1][j].
- Push the row into the answer.
Time: O(n^2)
Space: O(n^2)
Interview line: This is the standard and most expected answer when the full triangle is required.
@endsection

@section
region: full
title: Optimal Approach : TC: SC:
badge: 3 / 3
content:
Algorithm: For the full triangle, the row-by-row DP build is already optimal. For one specific row, use nCr recurrence.
Pseudo:
- Full triangle case: use previous row to fill current row.
- Single row case: start with 1 and iteratively derive the next combination value.
- Push each derived value into the row answer.
Time: O(n^2) for full triangle, O(n) for one row
Space: O(n^2) for full triangle, O(1) extra for one row
Key insight: The problem has two common variants, and interviewers like when you mention both.
@endsection

@section
region: grid
title: PCode
badge: 1 / 3
codeLang: pseudo
content:
answer = empty list

FOR row from 0 to numRows - 1
    current = empty list
    FOR col from 0 to row
        value = nCr(row, col)
        append value to current
    append current to answer

RETURN answer
@endsection

@section
region: grid
title: PCode
badge: 2 / 3
codeLang: pseudo
content:
answer = empty list

FOR row from 0 to numRows - 1
    current = array of size row + 1 filled with 1
    FOR col from 1 to row - 1
        current[col] = answer[row - 1][col - 1] + answer[row - 1][col]
    append current to answer

RETURN answer
@endsection

@section
region: grid
title: PCode
badge: 3 / 3
codeLang: pseudo
content:
IF full triangle is required
    use row-by-row construction and return all rows

rowAnswer = [1]
current = 1

FOR col from 0 to rowIndex - 1
    current = current * (rowIndex - col) / (col + 1)
    append current to rowAnswer

RETURN rowAnswer
@endsection