Pascal's Triangle Problem Solution Code : Java, Python, C, C++ | Given an integer numRows, return the first numRows of Pascal's triangle in Java, Python, C & C++


Pascal's Triangle Problem Code : Java, Python, C, C++ | Given an integer numRows, return the first numRows of Pascal's triangle in Java, Python, C & C++


Question Definition: Pascal's triangle is a triangular array of numbers in which each number is the sum of the two numbers directly above it. It starts with an "1" at the top, and each row represents the coefficients of the binomial expansion.


Description :


Consider Pascal's Triangle to be a numerical pyramid. A single "1" appears at the top, and as you proceed down, two digits immediately above it are added to create each new row.

For instance, you put the first and second numbers in the second row as they are both 1. The numbers for the third row are then calculated by adding the two numbers from the second row that are right above them (1+1 = 2), and the 1s remain on the ends.





The pattern is straightforward: the triangle continues to grow row by row as each number is created by adding the two numbers immediately above it.


Pascal's Triangle Problem Code : Java, Python, C, C++ | Given an integer numRows, return the first numRows of Pascal's triangle in Java, Python, C & C++
Pascal's Triangle Problem Code : Java, Python, C, C++ | Given an integer numRows, return the first numRows of Pascal's triangle in Java, Python, C & C++

Since the numbers in each row correspond to the coefficients you see when expanding something like (a + b) raised to a power, this pattern is helpful in many subjects, particularly mathematics.



The binomial coefficient can be used to represent any number in Pascal's Triangle,  and the following formula can be used to determine the value at any position:

Pascal's Triangle Problem Code : Java, Python, C, C++ | Given an integer numRows, return the first numRows of Pascal's triangle in Java, Python, C & C++
Pascal's Triangle Problem Code : Java, Python, C, C++ | Given an integer numRows, return the first numRows of Pascal's triangle in Java, Python, C & C++

where k is the number's position within the row (also starting at 0) and n is the row number (beginning at 0).


Java : (Pascal's Triangle Java Solution Code)


class Solution {

    public List<List<Integer>> generate(int numRows) {

        List<List<Integer>> res= new ArrayList<>();

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

        {

            List<Integer> temp=new ArrayList<>();

            for(int j=0;j<=i;j++) temp.add(0);

            res.add(temp);

            res.get(i).set(0,1);

            res.get(i).set(i,1);


        }

        for(int i=2;i<numRows;i++)

        {

            for(int j=1;j<i;j++)

            {

                res.get(i).set(j,(res.get(i-1).get(j)+res.get(i-1).get(j-1)));

            }

        }

        return res;


Python : (Pascal's Triangle Python Solution Code)


class Solution:

    def generate(self, numRows):

        res = []

        for i in range(numRows):

            temp = [0] * (i + 1)

            res.append(temp)

            res[i][0] = 1

            res[i][i] = 1


        for i in range(2, numRows):

            for j in range(1, i):

                res[i][j] = res[i - 1][j] + res[i - 1][j - 1]


        return res


# Example usage

solution = Solution()

print(solution.generate(5))



C code: (Pascal's Triangle C Solution Code)


#include <stdio.h>
#include <stdlib.h>

int** generate(int numRows, int** columnSizes, int* returnSize) {
    *returnSize = numRows;
    int** res = (int**)malloc(numRows * sizeof(int*));
    *columnSizes = (int*)malloc(numRows * sizeof(int));

    for (int i = 0; i < numRows; i++) {
        (*columnSizes)[i] = i + 1;
        res[i] = (int*)malloc((i + 1) * sizeof(int));
        res[i][0] = 1;
        res[i][i] = 1;

        for (int j = 1; j < i; j++) {
            res[i][j] = res[i - 1][j] + res[i - 1][j - 1];
        }
    }
    return res;
}

int main() {
    int numRows = 5;
    int* columnSizes;
    int returnSize;
    int** result = generate(numRows, &columnSizes, &returnSize);

    for (int i = 0; i < returnSize; i++) {
        for (int j = 0; j < columnSizes[i]; j++) {
            printf("%d ", result[i][j]);
        }
        printf("\n");
        free(result[i]);
    }
    free(result);
    free(columnSizes);
    return 0;
}



C++ Code :  (Pascal's Triangle C++ Solution Code)



#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res(numRows);
        for (int i = 0; i < numRows; i++) {
            res[i].resize(i + 1, 0);
            res[i][0] = 1;
            res[i][i] = 1;

            for (int j = 1; j < i; j++) {
                res[i][j] = res[i - 1][j] + res[i - 1][j - 1];
            }
        }
        return res;
    }
};

int main() {
    Solution solution;
    int numRows = 5;
    vector<vector<int>> result = solution.generate(numRows);

    for (const auto& row : result) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    return 0;
}



Let's analyze the time complexity and space complexity of the given code for generating Pascal's Triangle.


Time Complexity

  1. Outer Loop (for i in range(numRows)):

    • The outer loop runs numRows times.
  2. Inner Loop (for j in range(1, i)):

    • For each row i, the inner loop runs i - 1 times to calculate the inner elements of the row.

    Total number of iterations for the inner loop:


    This is O(numRows^2)

    Pascal's Triangle Problem Code : Java, Python, C, C++ | Given an integer numRows, return the first numRows of Pascal's triangle in Java, Python, C & C++

    Pascal's Triangle Problem Solution Code : Java, Python, C, C++ | Given an integer numRows, return the first numRows of Pascal's triangle in Java, Python, C & C++
    Time Complexity : Pascal's Triangle Problem Solution Code : Java, Python, C, C++ | Pascal's triangle in Java, Python, C & C++


  1. Total Time Complexity:

    • Initializing the list and setting values at the edges of each row also takes O(numRows^2)
    • Therefore, the overall time complexity is: O(numRows^2)

Space Complexity

  1. Output Space:

    • The output is a 2D list containing Pascal's Triangle. The total number of elements stored is: 1+2+3++numRows=  numRows(numRows+1) /2 . This is O(numRows^2)
  2. Auxiliary Space:

    • No additional data structures are used apart from the result list, so auxiliary space is O(1).
  3. Total Space Complexity:

    • The space complexity is dominated by the output space, which is: O(numRows^2)

Summary

  • Time Complexity: O(numRows^2 )
  • Space Complexity: O(numRows ^2)

Thank You for reading this post. You can check out more articles like this on www.physicswallah.in 

If you have any doubts then you can post a comment below.

No comments:

Post a Comment