Pascals Triangle
Java coding interview problem for Pattern Printing: Pascals Triangle.
Pascal's Triangle is one of the most famous mathematical patterns and is frequently asked in Java coding interviews.
Unlike simple star patterns, Pascal's Triangle combines mathematics, nested loops, and dynamic value generation.
Interviewers ask this problem to evaluate your understanding of:
- Nested loops
- Mathematical logic
- Binomial coefficients
- Pattern recognition
- Dynamic programming concepts
- Algorithm optimization
Learning Pascal's Triangle also helps in understanding advanced topics such as:
- Binomial Theorem
- Combinations (nCr)
- Probability
- Dynamic Programming
- Combinatorics
What is Pascal's Triangle?
Pascal's Triangle is a triangular arrangement of numbers where:
- The first and last number of every row is 1.
- Every middle number is the sum of the two numbers directly above it.
Example
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Every new row is generated from the previous row.
History of Pascal's Triangle
Although it is named after the French mathematician Blaise Pascal, the triangle existed centuries before him.
Many ancient civilizations studied this pattern.
Examples include:
- India
- China
- Persia
- Italy
Blaise Pascal later documented its mathematical properties in detail, making it widely known as Pascal's Triangle.
Why is Pascal's Triangle Asked in Interviews?
Unlike ordinary pattern programs, Pascal's Triangle tests both programming and mathematics.
Interviewers use it to evaluate whether candidates can:
- Work with nested loops
- Generate values dynamically
- Understand mathematical formulas
- Optimize algorithms
- Solve combinatorial problems
It is also a stepping stone toward Dynamic Programming interview questions.
Mathematical Properties
Pascal's Triangle has many interesting mathematical properties.
Property 1
The first number of every row is
1
Property 2
The last number of every row is
1
Property 3
Every middle number is calculated as
Left Parent
+
Right Parent
Example
1 3 3 1
\ | /
6
Because
3 + 3 = 6
Property 4
The sum of every row follows powers of two.
| Row | Sum |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
| 5 | 32 |
Formula
2ⁿ
Property 5
Each value is a Binomial Coefficient.
Example
Row 5
1 5 10 10 5 1
These values represent
5C0
5C1
5C2
5C3
5C4
5C5
Visual Representation
For
Rows = 5
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
------------------
Row 5
1 5 10 10 5 1
Notice:
- Every row starts with 1.
- Every row ends with 1.
- Middle values are generated from the previous row.
Pattern Output
Input
Rows = 5
Output
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Understanding the Logic
For every row:
- Print the row number of elements.
- Print 1 at the beginning.
- Calculate every middle value.
- Print 1 at the end.
Example
Row 4
Previous row
1 3 3 1
Current row
1
1+3 = 4
3+3 = 6
3+1 = 4
1
Result
1 4 6 4 1
Brute Force Approach
The simplest solution generates every value using the Combination Formula.
Formula
nCr
=
n!
------------
r!(n-r)!
For every row:
- Calculate every combination.
- Print the value.
- Move to the next row.
Although simple, this approach repeatedly computes factorials, making it inefficient for larger inputs.
Algorithm
Step 1
Read the number of rows.
rows = 5;
Step 2
Start the outer loop.
0
↓
rows
Each iteration represents one row.
Step 3
Start the inner loop.
0
↓
Current Row
Each iteration prints one element of the current row.
Step 4
Calculate
nCr
for every position.
Step 5
Print the calculated value.
Step 6
Move to the next line.
Repeat until all rows are printed.
Dry Run
Input
Rows = 3
Iteration
Row 0
1
Iteration
Row 1
1 1
Iteration
Row 2
1 2 1
Iteration
Row 3
1 3 3 1
Final Output
1
1 1
1 2 1
1 3 3 1
Approach 1 — Using Factorial and Combination Formula
This is the easiest approach to understand because it directly follows the mathematical definition of the Binomial Coefficient.
Complete Java Program
public class PascalsTriangle {
static int factorial(int n) {
int fact = 1;
for (int i = 1; i <= n; i++) {
fact *= i;
}
return fact;
}
static int combination(int n, int r) {
return factorial(n) /
(factorial(r) * factorial(n - r));
}
public static void main(String[] args) {
int rows = 5;
for (int i = 0; i <= rows; i++) {
for (int j = 0; j <= i; j++) {
System.out.print(combination(i, j) + " ");
}
System.out.println();
}
}
}
Output
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Step-by-Step Code Explanation
Step 1
Create a factorial method.
static int factorial(int n)
This method calculates:
n!
Example
5!
=
120
Step 2
Create a combination method.
combination(n, r)
This calculates:
nCr
Example
5C2
=
10
Step 3
Create the outer loop.
for (int i = 0; i <= rows; i++)
Each iteration represents one row.
Step 4
Create the inner loop.
for (int j = 0; j <= i; j++)
Each iteration prints one value of the current row.
Step 5
Calculate the value.
combination(i, j)
Print the result.
Example Execution
Input
Rows = 4
Output
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Why Does This Work?
Every value in Pascal's Triangle is a Binomial Coefficient, represented mathematically as nCr. The outer loop determines the current row (n), while the inner loop determines the position (r) within that row.
For each position, the program calculates:
nCr = n! / (r! × (n - r)!)
The calculated values naturally form Pascal's Triangle because they satisfy the mathematical relationship where each interior element equals the sum of the two elements directly above it.
Advantages of This Approach
- Easy to understand.
- Directly follows the mathematical definition.
- Excellent for learning combinations.
- Suitable for small input sizes.
- Frequently discussed in coding interviews.
Drawbacks
This solution repeatedly calculates factorial values, which results in unnecessary computations.
For larger values of n, it becomes slower and may also suffer from integer overflow.
In Part 2, we'll build a much more efficient solution using the Binomial Coefficient recurrence, avoiding repeated factorial calculations.
We'll also cover:
- Optimized Binomial Coefficient Approach
- Reusable
printPascalsTriangle()Method - Mathematical Applications
- Time and Space Complexity
- Comparison of Approaches
- Common Interview Mistakes
- Interview Follow-up Questions
- Related Pattern Problems
- Key Takeaways
- Interview Tips
Approach 2 — Optimized Using Binomial Coefficient
The factorial approach is simple but inefficient because it repeatedly calculates factorial values.
A better approach is to generate each element directly from the previous one using the Binomial Coefficient recurrence.
Instead of computing
nCr
using factorials every time, we use
Next Value
=
Current Value × (Row − Column)
-------------------------------
Column + 1
This avoids repeated factorial calculations and significantly improves performance.
Mathematical Formula
Suppose the current value is
nCr
Then,
the next value is
nC(r + 1)
=
nCr × (n − r)
----------------
r + 1
Example
Row = 5
Start
1
Next
1 × 5 / 1
=
5
Next
5 × 4 / 2
=
10
Next
10 × 3 / 3
=
10
Next
10 × 2 / 4
=
5
Next
5 × 1 / 5
=
1
Output
1 5 10 10 5 1
Java Program
public class PascalsTriangleOptimized {
public static void main(String[] args) {
int rows = 5;
for (int i = 0; i <= rows; i++) {
int value = 1;
for (int j = 0; j <= i; j++) {
System.out.print(value + " ");
value = value * (i - j) / (j + 1);
}
System.out.println();
}
}
}
Output
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Step-by-Step Explanation
Suppose
Row = 5
Initially
value = 1
1
Update
1 × (5−0) / (0+1)
=
5
5
Update
5 × (5−1) / (1+1)
=
10
Continue until the row is completed.
No factorial calculations are required.
Approach 3 — Using a Reusable Method
A reusable method improves readability and allows the same logic to be called multiple times.
Java Program
public class PascalsTriangleMethod {
static void printPascalsTriangle(int rows) {
for (int i = 0; i <= rows; i++) {
int value = 1;
for (int j = 0; j <= i; j++) {
System.out.print(value + " ");
value = value * (i - j) / (j + 1);
}
System.out.println();
}
}
public static void main(String[] args) {
printPascalsTriangle(5);
}
}
Mathematical Applications
Pascal's Triangle has many real-world applications.
1. Binomial Expansion
Example
(a + b)⁵
Coefficients
1
5
10
10
5
1
Expansion
a⁵
+
5a⁴b
+
10a³b²
+
10a²b³
+
5ab⁴
+
b⁵
2. Combinations
Every value represents
nCr
Example
5C2
=
10
3. Probability
Used in
- Binomial Distribution
- Statistics
- Machine Learning
4. Dynamic Programming
Many Dynamic Programming problems are based on Pascal's Triangle because every value depends on previously computed values.
5. Combinatorics
Widely used in:
- Counting problems
- Graph theory
- Mathematical proofs
Time Complexity
Suppose
n
is the number of rows.
Factorial Approach
| Operation | Complexity |
|---|---|
| Time | O(n³) (due to repeated factorial computations) |
| Space | O(1) |
Optimized Binomial Coefficient
| Operation | Complexity |
|---|---|
| Time | O(n²) |
| Space | O(1) |
Comparison of Approaches
| Approach | Time | Space | Recommended |
|---|---|---|---|
| Factorial Method | O(n³) | O(1) | Learning Purpose |
| Optimized Binomial Formula | O(n²) | O(1) | ✅ Interview Best |
| Reusable Method | O(n²) | O(1) | Production Ready |
Common Mistakes
Mistake 1
Recomputing factorials repeatedly.
Wrong
factorial()
called for every element.
Correct
Generate the next value directly.
Mistake 2
Using incorrect update formula.
Wrong
value = value * i / j;
Correct
value = value * (i - j) / (j + 1);
Mistake 3
Initializing
value
incorrectly.
Wrong
value = 0;
Correct
value = 1;
Mistake 4
Incorrect inner loop condition.
Wrong
j < i
Correct
j <= i
Otherwise the last element (1) is skipped.
Mistake 5
Using int for very large rows.
For larger values, use
long
or
BigInteger
to avoid overflow.
Interview Follow-up Questions
Q1. What is Pascal's Triangle?
Q2. Why does every row start and end with 1?
Q3. What is the relationship with nCr?
Q4. Can you generate the triangle without factorials?
Q5. What is the optimized formula?
Q6. Why is the optimized solution faster?
Q7. What is the time complexity?
Q8. Where is Pascal's Triangle used?
Q9. Can you store it using a 2D array?
Q10. Can you solve it using Dynamic Programming?
Related Pattern Problems
- Full Pyramid Pattern
- Inverted Pyramid Pattern
- Diamond Pattern
- Floyd's Triangle
- Number Pyramid
- Alphabet Pyramid
- Yang Hui Triangle
- Binomial Coefficient
- Combination (nCr)
Key Takeaways
- Every row starts and ends with 1.
- Every middle element equals the sum of the two elements directly above it.
- Each value represents a Binomial Coefficient (nCr).
- The optimized recurrence avoids repeated factorial calculations.
- The optimized approach runs in O(n²) time with O(1) extra space.
Frequently Asked Interview Questions
Q1. Why is Pascal's Triangle important?
It connects programming with mathematics and is widely used in combinatorics, probability, statistics, and dynamic programming.
Q2. Why is the optimized approach preferred?
It avoids repeated factorial calculations and generates each value from the previous one using a simple recurrence, making it much faster.
Q3. Can Pascal's Triangle be generated using Dynamic Programming?
Yes.
Each element depends on the two elements directly above it, making it a classic Dynamic Programming example.
Q4. Why does every row begin and end with 1?
The first and last values represent:
nC0 = 1
and
nCn = 1
Q5. How can we avoid integer overflow?
For large row numbers, replace int with:
long
or
BigInteger
to support much larger values.
Interview Tip
If an interviewer asks:
"Print Pascal's Triangle in Java."
Start with the factorial-based solution to demonstrate your understanding of the mathematical definition of nCr. Then improve the solution by introducing the Binomial Coefficient recurrence, which generates each value from the previous one in constant time per element.
Mention that this optimized approach reduces the overall complexity from O(n³) (repeated factorial computations) to O(n²) and is the preferred solution in coding interviews because it is efficient, elegant, and scales much better.