Parallel Pascal's Triangle Generation

Generate Pascal’s triangle with numRows rows in parallel, where each row is computed by a separate thread.

✅ Step 0: Problem Understanding

Pascal’s Triangle:

Row 0:           [1]
Row 1:         [1, 1]
Row 2:       [1, 2, 1]
Row 3:     [1, 3, 3, 1]
Row 4:   [1, 4, 6, 4, 1]
...

Each row is computed from the previous row:

row[i] = prevRow[i - 1] + prevRow[i];

🔹 Step 1: Naive Parallel Solution (Wrong)

Let’s begin with the idea that we spawn numRows threads, one per row.

❌ Initial Code (Incorrect)

public class PascalTriangleNaive {
    public static void main(String[] args) throws InterruptedException {
        int numRows = 5;
        List<List<Integer>> triangle = new ArrayList<>(Collections.nCopies(numRows, null));

        List<Thread> threads = new ArrayList<>();
        for (int row = 0; row < numRows; row++) {
            final int r = row;
            Thread t = new Thread(() -> {
                List<Integer> current = new ArrayList<>();
                current.add(1);
                for (int i = 1; i < r; i++) {
                    int val = triangle.get(r - 1).get(i - 1) + triangle.get(r - 1).get(i);
                    current.add(val);
                }
                if (r > 0) current.add(1);
                triangle.set(r, current);
            });
            threads.add(t);
            t.start();
        }

        for (Thread t : threads) t.join();

        for (List<Integer> row : triangle) System.out.println(row);
    }
}

❌ Problems with This Approach

• Race Condition: All threads run independently, but row i depends on row i - 1. Thread for row 3 may start before row 2 is ready.

• NullPointerException: Accessing triangle.get(r - 1) may return null.

• No Guarantee of Order: Results may be printed before some threads complete.

🔹 Step 2: Fix with Thread Synchronization (Join Previous)

Let’s ensure each thread waits until its dependent row is calculated.

✅ Approach: Use CountDownLatch or simply synchronize row dependencies.

🔸 Step 3: Better Approach — Row Dependency Synchronization

✅ Improved Version Using Latches

import java.util.*;
import java.util.concurrent.*;

public class PascalTriangleWithLatch {
    public static void main(String[] args) throws InterruptedException {
        int numRows = 5;

        List<List<Integer>> triangle = new ArrayList<>(Collections.nCopies(numRows, null));
        CountDownLatch[] latches = new CountDownLatch[numRows];

        for (int i = 0; i < numRows; i++) {
            latches[i] = new CountDownLatch(1);
        }

        ExecutorService executor = Executors.newFixedThreadPool(numRows);

        for (int row = 0; row < numRows; row++) {
            final int r = row;
            executor.submit(() -> {
                try {
                    if (r > 0) {
                        // Wait for previous row to be ready
                        latches[r - 1].await();
                    }

                    List<Integer> current = new ArrayList<>();
                    current.add(1);
                    if (r > 0) {
                        List<Integer> prev = triangle.get(r - 1);
                        for (int i = 1; i < r; i++) {
                            current.add(prev.get(i - 1) + prev.get(i));
                        }
                        current.add(1);
                    }
                    triangle.set(r, current);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                } finally {
                    // Signal that this row is ready
                    latches[r].countDown();
                }
            });
        }

        executor.shutdown();
        executor.awaitTermination(5, TimeUnit.SECONDS);

        for (List<Integer> row : triangle) {
            System.out.println(row);
        }
    }
}

✅ What’s Fixed:

• Thread for row r waits for row r-1 to complete.

• Avoids race condition and NullPointerException.

🔹 Step 4: Final Optimized and Safe Version

Let’s wrap the logic in a class, make it reusable, thread-safe, and extensible.

✅ Final Java Code

import java.util.*;
import java.util.concurrent.*;

public class ParallelPascalTriangle {

    public List<List<Integer>> generate(int numRows) throws InterruptedException {
        List<List<Integer>> triangle = new ArrayList<>(Collections.nCopies(numRows, null));
        CountDownLatch[] latches = new CountDownLatch[numRows];

        for (int i = 0; i < numRows; i++) {
            latches[i] = new CountDownLatch(1);
        }

        ExecutorService executor = Executors.newFixedThreadPool(Math.min(numRows, Runtime.getRuntime().availableProcessors()));

        for (int row = 0; row < numRows; row++) {
            final int r = row;
            executor.submit(() -> {
                try {
                    if (r > 0) {
                        latches[r - 1].await();
                    }

                    List<Integer> current = new ArrayList<>();
                    current.add(1);
                    if (r > 0) {
                        List<Integer> prev = triangle.get(r - 1);
                        for (int i = 1; i < r; i++) {
                            current.add(prev.get(i - 1) + prev.get(i));
                        }
                        current.add(1);
                    }

                    triangle.set(r, current);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                } finally {
                    latches[r].countDown();
                }
            });
        }

        executor.shutdown();
        executor.awaitTermination(10, TimeUnit.SECONDS);
        return triangle;
    }

    public static void main(String[] args) throws InterruptedException {
        ParallelPascalTriangle pt = new ParallelPascalTriangle();
        List<List<Integer>> result = pt.generate(10);
        result.forEach(System.out::println);
    }
}