LeetCode 118: Pascal's Triangle Solution
Master LeetCode problem 118 (Pascal's Triangle), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
118. Pascal's Triangle
Problem Explanation
Explanation
To generate Pascal's triangle, we will use a 2D list to store the triangle. We will iterate through each row, and for each row, we will calculate the values based on the previous row. The value at a particular position in a row is the sum of the values at the same position and the previous position in the row above it.
Algorithm:
- Initialize a 2D list to store the triangle.
- Iterate from 1 to numRows.
- For each row, initialize a new list and fill it with 1s (for the first and last elements of the row).
- For elements in between, calculate the value by summing the two values from the previous row.
- Append the row to the triangle list.
- Return the triangle list.
Time Complexity: O(numRows^2) - we need to generate each value in the triangle. Space Complexity: O(numRows^2) - space used to store the triangle.
Solution Code
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
List<Integer> row = new ArrayList<>();
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i) {
row.add(1);
} else {
row.add(triangle.get(i - 1).get(j - 1) + triangle.get(i - 1).get(j));
}
}
triangle.add(row);
}
return triangle;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 118 (Pascal's Triangle)?
This page provides optimized solutions for LeetCode problem 118 (Pascal's Triangle) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 118 (Pascal's Triangle)?
The time complexity for LeetCode 118 (Pascal's Triangle) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 118 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 118 in Java, C++, or Python.