Let's make this one less mysterious. For 118. Pascal's Triangle, the solution in this repository is mainly a straightforward implementation solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: straightforward implementation.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The solution is organized around the main LeetCode entry point and a few local helpers.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(numRows^2)
- Space: O(numRows^2)
Guide
C++ Solution
Your submission
The accepted solution
01/**
02Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.
03
04
05In Pascal's triangle, each number is the sum of the two numbers directly above it.
06
07Example:
08
09Input: 5
10Output:
11[
12 [1],
13 [1,1],
14 [1,2,1],
15 [1,3,3,1],
16 [1,4,6,4,1]
17]
18**/
19
20/**
21Approach 1: Dynamic Programming
22**/
23
24/**
25Complexity Analysis
26Time complexity : O(numRows^2)
27Space complexity : O(numRows^2)
28**/
29
30//Runtime: 8 ms, faster than 25.38% of C++ online submissions for Pascal's Triangle.
31//Memory Usage: 8.7 MB, less than 86.38% of C++ online submissions for Pascal's Triangle.
32
33class Solution {
34public:
35 vector<vector<int>> generate(int numRows) {
36 vector<vector<int>> ans;
37 for(int i = 1; i <= numRows; i++){
38 vector<int> v = vector<int>(i, 1);
39 if(i > 2){
40 for(int j = 1; j <= v.size()-2; j++){
41 v[j] = ans[ans.size()-1][j-1] + ans[ans.size()-1][j];
42 }
43 }
44 ans.push_back(v);
45 }
46 return ans;
47 }
48};Cost