Solving a Leetcode problem daily - Day 1 | Pascal’s Triangle

I have written this blog originally in Medium -

Solving a Leetcode problem daily — Day 1: Pascal’s Triangle | by Subhradeep Saha | Apr, 2024 | Medium

Subhradeep Saha ・ May 3, 2024 ・

Medium

Here is the Leetcode problem - Pascal's Triangle

What is Pascal’s Triangle?

Imagine a pyramid of numbers where each element is the sum of the two numbers directly above it. That’s Pascal’s Triangle! Here’s a look at the first few rows:

As you can see, the first row always starts with a 1, and each subsequent row is built by adding the elements above it.

The LeetCode Challenge

The LeetCode challenge asks us to write a function that takes an integer numRows and returns the first numRows rows of Pascal's Triangle.

Understanding the Solution

Complete Code:

class Solution {
public:
  vector<vector<int>> generate(int numRows) {
    vector<vector<int>> res(numRows);
    for (int i = 0; i < numRows; i++) {
      for (int j = 0; j <= i; j++) {
        int left = (i >= 1 && j >= 1) ? res[i - 1][j - 1] : 0;
        int right = (i >= 1 && j < i) ? res[i - 1][j] : 0;
        int sum = (left == 0 && right == 0) ? 1 : left + right;
        res[i].push_ back(sum);
      }
    }
    return res;
  }
};

Here’s a breakdown of the C++ code into sections:

1. Class and Function Definition:

class Solution {
public:
  vector<vector<int>> generate(int numRows) {

This code defines a class Solution with a public function named generate. This function takes an integer numRows as input and is designed to return a 2D vector of integers representing Pascal's Triangle.

2. Result Initialization:

vector<vector<int>> res(numRows);

Here, we create a 2D vector named res. This vector will have numRows rows, and it will be used to store the generated Pascal's Triangle. We are not initializing the number of columns here since the items will be pushed dynamically inside of the loop.

3. Nested Loops for Iterating Through the Triangle:

for (int i = 0; i < numRows; i++) {
      for (int j = 0; j <= i; j++) {

We use two nested loops to iterate through each element of the resulting triangle. The outer loop (i) iterates through each row (0 to numRows-1). The inner loop (j) iterates through each element (0 to i) within the current row.

Explanation of the Loops:
These loops ensure we visit each element in the 2D vector exactly once. The outer loop (i) progresses row by row, while the inner loop (j) fills the elements within each row. Since Pascal's Triangle has a specific structure where elements rely on previous rows, this nested loop approach is ideal for building it efficiently.

Next Steps:

In the next section, we’ll delve into how the code calculates the value for each element in the triangle using these loops.

4. Calculating Element Values:

The core functionality of the code lies within the inner loop:

int left = (i >= 1 && j >= 1) ? res[i - 1][j - 1] : 0;
int right = (i >= 1 && j < i) ? res[i - 1][j] : 0;
int sum = (left == 0 && right == 0) ? 1 : left + right;
res[i].push_back(sum);

Understanding the Logic:
left and right Variables:

• These variables represent the values needed to calculate the current element’s sum based on Pascal’s Triangle’s property.

• left: This stores the value from the element directly above and one position to the left. The ternary expression (i >= 1 && j >= 1) ? res[i - 1][j - 1] : 0) checks if we're not in the first row (i=0) or the first element (j=0) of any row. If valid, it accesses the element in the previous row using res[i - 1][j - 1]. Otherwise, it sets left to 0 (since there's no element there).

• right: This stores the value from the element directly above. The ternary expression (i >= 1 && j < i) ensures we're not in the first row and j is within the current row's boundary (not the last element). If valid, it accesses the element above using res[i - 1][j]. Otherwise, it sets right to 0.

sum Calculation:

• The sum variable holds the final value for the current element (i, j).
• The ternary expression (left == 0 && right == 0) ? 1 : left + right) calculates the sum. If both left and right are 0 (meaning we're at the first element of a row), we set sum to 1 (since the first element in each row is always 1). Otherwise, sum is calculated by adding left and right.

Adding the Value to the Result:
Finally, res[i].push_back(sum) adds the calculated sum to the current row (res[i]) of the result vector.

Key Takeaway:

This logic leverages dynamic programming. By using previously calculated values (left and right from the previous row), the code efficiently builds the triangle element by element.

Next Steps:

In the final section, we’ll see how this code works with different inputs and the complete solution.

Now that we’ve explored the code’s building blocks, let’s see how it works with different inputs and how the pieces fit together to form the complete solution.

Test Cases and Explanation

Let’s see the code in action with some test cases:

Test Case 1: numRows = 1

Output: [[1]]

Explanation:
The first row of Pascal’s Triangle always has a single 1, and the code correctly handles this case using the logic for the first element (left and right become 0, so sum is set to 1).

Test Case 2: numRows = 3

Output: [[1], [1, 1], [1, 2, 1]]

Explanation:

1. Row 1: We have only one element (1) as explained in Test Case 1.
2. Row 2: left for the first element (j=0) is 0 (since we're in the first column of row 2). right (element directly above) is also 0 (since we're in row 2). Therefore, sum becomes 1 (as both left and right are 0). This process repeats for the second element (j=1) in row 2, where left becomes 1 (referring to the first element in row 1) and right is still 0. So, sum is 1 + 0 = 1.
3. Row 3: The calculation for the first element (j=0) follows the same logic as row 2, resulting in sum as 1. For the second element (j=1), left is 1 (referring to the element above and to the left) and right is 1 (referring to the element directly above). So, sum is 1 + 1 = 2. The calculation for the third element (j=2) uses left as 1 and right as 1, resulting in sum as 1 + 1 = 2.

Conclusion

This code effectively generates Pascal’s Triangle in C++ by leveraging dynamic programming and nested loops. By understanding the logic behind calculating element values and the role of each code section, you can now tackle this LeetCode problem and similar problems that involve building upon previously calculated results.

Feel free to experiment with the code by changing the numRows value and observe how the triangle grows! Happy coding!