Pascal Triangle In Java Using Array

Pascal's Triangle is a fascinating mathematical structure that arises in various fields, from combinatorics to probability. Its elegant pattern of numbers, where each number is the sum of the two numbers directly above it, makes it a popular subject for programming challenges.

In this article, you will learn how to generate Pascal's Triangle in Java using array-based approaches, covering both a direct 2D array implementation and an optimized space version.

Problem Statement

The challenge is to generate the first n rows of Pascal's Triangle. Each number in the triangle (except for the ones at the edges) is the sum of the two numbers directly above it. The edges of the triangle always consist of the number 1.

For instance, to find the number in row i and column j (0-indexed), it's given by C(i, j), the binomial coefficient "i choose j". This can be recursively defined as:

• C(i, 0) = 1
• C(i, i) = 1
• C(i, j) = C(i-1, j-1) + C(i-1, j) for 0 < j < i

Example

Here’s what the first 5 rows of Pascal's Triangle look like:

1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1

Background & Knowledge Prerequisites

To understand the solutions presented, a basic understanding of Java programming concepts is helpful. Specifically, familiarity with the following topics will be beneficial:

• Arrays: Declaring, initializing, and accessing elements in one-dimensional and two-dimensional arrays.
• Loops: for loops for iteration.
• Basic Arithmetic: Addition.

Use Cases or Case Studies

Pascal's Triangle is not just a mathematical curiosity; it has practical applications across various domains:

• Combinatorics: Each entry C(n, k) represents the number of ways to choose k items from a set of n distinct items (combinations).
• Binomial Expansion: The numbers in row n are the coefficients of the terms in the binomial expansion of (x + y)^n. For example, row 2 (1 2 1) corresponds to (x + y)^2 = 1x^2 + 2xy + 1y^2.
• Probability Theory: It's used in calculating probabilities in situations involving binary outcomes, such as coin flips.
• Computer Science Algorithms: Concepts related to dynamic programming often involve similar recursive patterns.

Solution Approaches

We will explore two effective ways to generate Pascal's Triangle using arrays in Java.

Approach 1: Generating with a 2D Array

This approach directly constructs the triangle by storing all numbers in a 2D array. Each row is calculated based on the values in the previous row.

• Summary: Uses a int[][] array to hold the entire triangle, calculating each cell (i, j) as the sum of (i-1, j-1) and (i-1, j).

// Pascal's Triangle using 2D Array
import java.util.Scanner;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Step 1: Get the number of rows from the user
        System.out.print("Enter the number of rows for Pascal's Triangle: ");
        int numRows = scanner.nextInt();

        // Step 2: Declare and initialize a 2D array (jagged array for varying row lengths)
        int[][] triangle = new int[numRows][];

        // Step 3: Iterate through each row to populate the triangle
        for (int i = 0; i < numRows; i++) {
            // Each row 'i' has 'i + 1' elements
            triangle[i] = new int[i + 1];

            // The first and last elements of each row are always 1
            triangle[i][0] = 1;
            triangle[i][i] = 1;

            // Step 4: Calculate the intermediate elements for rows > 1
            for (int j = 1; j < i; j++) {
                triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
            }
        }

        // Step 5: Print the Pascal's Triangle
        System.out.println("\\nPascal's Triangle (" + numRows + " rows):");
        for (int i = 0; i < numRows; i++) {
            // Add leading spaces for proper alignment
            for (int k = 0; k < numRows - i - 1; k++) {
                System.out.print(" ");
            }
            for (int j = 0; j <= i; j++) {
                System.out.print(triangle[i][j] + " ");
            }
            System.out.println();
        }

        scanner.close();
    }
}

Run

• Sample Output:

Enter the number of rows for Pascal's Triangle: 5

    Pascal's Triangle (5 rows):
        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1

• Stepwise Explanation:

1. The user inputs the desired numRows.
2. A 2D array triangle is initialized. Since each row of Pascal's Triangle has a different number of elements, we use a jagged array where triangle[i] is initialized with i + 1 elements.
3. An outer loop iterates from i = 0 to numRows - 1 for each row.
4. For each row i, the first element (triangle[i][0]) and the last element (triangle[i][i]) are set to 1, as per Pascal's Triangle rules.
5. An inner loop calculates the intermediate elements. For j from 1 to i-1, triangle[i][j] is determined by summing triangle[i-1][j-1] (the element directly above and to the left) and triangle[i-1][j] (the element directly above). This step only applies for rows i > 1.
6. Finally, another set of nested loops prints the triangle array with appropriate spacing to maintain the triangle shape.

Approach 2: Generating with Optimized Space (Current Row Only)

This approach is efficient if you only need to print or process one row at a time and don't need to store the entire triangle. It calculates the current row by only referring to the immediately preceding row, effectively using only two rows of space (or even one, with careful iteration).

• Summary: Uses a single 1D array to represent the current row, updating it in place by working backward to calculate new values based on previous values within the same array (which represent the previous row's state).

// Pascal's Triangle with Space Optimization (1D Array)
import java.util.Scanner;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Step 1: Get the number of rows from the user
        System.out.print("Enter the number of rows for Pascal's Triangle: ");
        int numRows = scanner.nextInt();

        // Step 2: Declare and initialize a 1D array to store the current row
        // The maximum length of a row will be numRows
        int[] currentRow = new int[numRows];

        System.out.println("\\nPascal's Triangle (" + numRows + " rows):");

        // Step 3: Iterate through each row to calculate and print
        for (int i = 0; i < numRows; i++) {
            // Add leading spaces for proper alignment
            for (int k = 0; k < numRows - i - 1; k++) {
                System.out.print(" ");
            }

            // Step 4: Calculate elements for the current row, iterating backward
            // This is crucial to use the values from the *previous* iteration (previous row)
            // before they are overwritten for the current row's calculation.
            for (int j = i; j >= 0; j--) {
                if (j == 0 || j == i) {
                    currentRow[j] = 1; // First and last element are always 1
                } else {
                    currentRow[j] = currentRow[j - 1] + currentRow[j];
                }
            }

            // Step 5: Print the current row
            for (int j = 0; j <= i; j++) {
                System.out.print(currentRow[j] + " ");
            }
            System.out.println();
        }

        scanner.close();
    }
}

Run

• Sample Output:

Enter the number of rows for Pascal's Triangle: 5

    Pascal's Triangle (5 rows):
        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1

• Stepwise Explanation:

1. The user provides numRows.
2. A single 1D array currentRow of size numRows is declared. This array will store the values of the currently computed row.
3. The outer loop iterates for each row i from 0 to numRows - 1.
4. The crucial part is the inner loop that iterates *backward* from j = i down to 0.

• If j is the first element (j == 0) or the last element (j == i) of the current row, currentRow[j] is set to 1.
• Otherwise, currentRow[j] is updated as the sum of currentRow[j-1] (which is still the value from the *previous* row's j-1 position) and currentRow[j] (which is still the value from the *previous* row's j position). Iterating backward ensures that currentRow[j-1] has not yet been updated for the current row, effectively allowing us to use the values from the previous row.

1. After the currentRow is fully calculated for the current i, its elements are printed, along with leading spaces for alignment.

Conclusion

Generating Pascal's Triangle provides an excellent exercise in understanding array manipulation and nested loops. The 2D array approach is straightforward, mirroring the triangle's structure directly, while the optimized 1D array method demonstrates how careful iteration can significantly reduce space complexity when only successive rows are needed. Both methods effectively achieve the desired output, offering insights into different programming strategies.

Summary

• Pascal's Triangle Definition: Each number is the sum of the two above it; edges are 1s.
• 2D Array Approach:
• Uses int[][] to store the entire triangle.
• triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j].
• Simple to understand and implement for full triangle storage.
• Optimized 1D Array Approach:
• Uses a single int[] to store and update the current row.
• Iterates backward (j = i down to 0) to correctly use previous row values.
• Space-efficient for generating rows one by one without storing the whole triangle.
• Common Principle: Both methods rely on the recursive definition of Pascal's Triangle to calculate elements based on previously computed values.