Skip to content

Volume ITechnology

4.0.10 — Pattern Printing: Triangles, Pyramids, Diamonds, Pascal ​

Classic · Easy · LeetCode 118 (Pascal's Triangle) · a staple of service-company online tests

The problem ​

Print shapes like these for a given number of rows n.

*          *          1          1
**        ***         2 3        1 1
***      *****        4 5 6      1 2 1
****    *******       7 8 9 10   1 3 3 1

These look like art. They are really a test of one skill: writing down, for row number i, exactly how many of each thing to print. Once you have that formula, the code is two loops.

The method that solves every pattern ​

  1. Number the rows from 1 to n, top to bottom.
  2. For each row, count the spaces before the first star, and count the stars.
  3. Write each count as a formula in the row number i.
  4. Print that many spaces, then that many stars.

Do steps 2 and 3 on paper with a small table first. Most people who struggle with patterns are trying to guess the code without the table.

1. Right triangle ​

*
**
***
****
row istars
11
22
33

Stars equal the row number.

python
def right_triangle(n: int) -> None:
    for i in range(1, n + 1):
        print("*" * i)

right_triangle(4)

In Python, "*" * i repeats the string i times. In most other languages you need an inner loop that prints one star at a time. The interviewer may ask for that version, to see the nested loop.

python
def right_triangle_loops(n: int) -> None:
    for i in range(1, n + 1):          # one pass per row
        for _ in range(i):             # i stars in row i
            print("*", end="")         # end="" stays on the same line
        print()                        # move to the next line

right_triangle_loops(3)

Inverted triangle. Stars count down instead: row i prints n - i + 1 stars. Check it: row 1 prints n, row n prints 1.

2. Centred pyramid ​

   *
  ***
 *****
*******
row ispacesstars
131
223
315
407

With n = 4 rows: spaces go down by one each row, starting at n - 1. So spaces = n - i. Stars go up by two each row, through the odd numbers 1, 3, 5, 7. So stars = 2i - 1.

python
def pyramid(n: int) -> None:
    for i in range(1, n + 1):
        print(" " * (n - i) + "*" * (2 * i - 1))

pyramid(4)

Why the odd numbers? The pyramid grows by one star on each side per row. That is two more stars per row, starting from one.

3. Diamond ​

  *
 ***
*****
 ***
  *

A diamond is a pyramid with an upside-down pyramid under it. The bottom half skips the widest row, so it is not printed twice.

python
def diamond(n: int) -> None:
    for i in range(1, n + 1):                    # top half, widest row last
        print(" " * (n - i) + "*" * (2 * i - 1))
    for i in range(n - 1, 0, -1):                # bottom half, counting back down
        print(" " * (n - i) + "*" * (2 * i - 1))

diamond(3)

The second loop uses the same formula with i running backwards, from n - 1 down to 1. You did not need a new formula. The old one works with i running backwards.

4. Number patterns and Floyd's triangle ​

Row numbers repeated. Print the row number i times.

python
for i in range(1, 5):
    print(" ".join(str(i) for _ in range(i)))
# → 1
# → 2 2
# → 3 3 3
# → 4 4 4 4

Floyd's triangle counts on without restarting. Robert Floyd, a computer scientist who won the Turing Award in 1978, used it as a teaching example.

python
def floyd(n: int) -> None:
    k = 1                          # (1)
    for i in range(1, n + 1):
        row = []
        for _ in range(i):
            row.append(str(k))
            k += 1                 # (2)
        print(" ".join(row))

floyd(4)
# → 1
# → 2 3
# → 4 5 6
# → 7 8 9 10

(1) The counter lives outside both loops, so it keeps its value from one row to the next.

(2) Every number printed moves the counter on by one.

The common bug is putting k = 1 inside the row loop. Then every row starts again from 1.

5. Pascal's triangle ​

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

Every row starts and ends with 1. Every number inside is the sum of the two numbers just above it. In row 5, the 6 is 3 + 3 from row 4.

It is named after the French mathematician Blaise Pascal, who wrote about it in 1654. It was known much earlier. In India, the writer Halayudha described it clearly in the 10th century, while explaining the older work of the poet Pingala. In China, Yang Hui published it in 1261, and it is still called Yang Hui's triangle there.

Building each row from the one above ​

python
def pascal(n: int) -> list[list[int]]:
    rows = []
    for i in range(n):
        row = [1] * (i + 1)                          # (1)
        for j in range(1, i):
            row[j] = rows[i - 1][j - 1] + rows[i - 1][j]   # (2)
        rows.append(row)
    return rows

for r in pascal(5):
    print(" ".join(map(str, r)))
# → 1
# → 1 1
# → 1 2 1
# → 1 3 3 1
# → 1 4 6 4 1

(1) Make the row full of 1s. The two ends stay 1. The middle gets overwritten.

(2) Each middle entry is the entry above-left plus the entry above. For row index i, those sit at positions j - 1 and j of the previous row.

This is LeetCode 118. It is O(n^2) time, because the rows hold 1 + 2 + \dots + n = \frac{n(n+1)}{2} numbers in total.

What the numbers mean ​

The number at row n, position k (both counted from 0) is \binom{n}{k}, read "n choose k". It counts how many ways there are to choose k things from n. For example, row 4 is 1 4 6 4 1. There are 6 ways to pick 2 people from 4.

Why does "add the two above" give these counts? Say you pick k people from n. Look at one particular person, Asha. Either Asha is picked, and you choose the other k - 1 from the remaining n - 1. Or Asha is not picked, and you choose all k from the remaining n - 1. So \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}. That is exactly the two entries above.

One row on its own ​

To print a single row without building the ones above it, step along the row with a formula. Moving from position k to k + 1 multiplies by (n - k) and divides by (k + 1).

python
def pascal_row(n: int) -> list[int]:
    row = [1]
    for k in range(n):
        row.append(row[-1] * (n - k) // (k + 1))   # (1)
    return row

print(pascal_row(6))   # → [1, 6, 15, 20, 15, 6, 1]

(1) Multiply first, then divide. The product is always exactly divisible by k + 1, so // loses nothing. Dividing first would round down too early and give wrong numbers.

6. Hollow square ​

*****
*   *
*   *
*****

Print a star only on the border. A cell is on the border when it is in the first or last row, or the first or last column.

python
def hollow_square(n: int) -> None:
    for r in range(n):
        line = ""
        for c in range(n):
            on_edge = r == 0 or r == n - 1 or c == 0 or c == n - 1
            line += "*" if on_edge else " "
        print(line)

hollow_square(4)

Every hollow shape works like this. Go through every cell, and decide with one condition whether it gets a star.

Complexity ​

Each pattern prints about n^2 characters in total, so it is O(n^2) time. You cannot do better, because the output itself has that many characters.

What the interviewer will push on ​

These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.

"Print the pyramid without using "*" * n." Use an inner loop that prints one star at a time, with end="" to stay on the same line. The number of spaces and stars per row stays the same: n - i spaces and 2i - 1 stars.

"Now print it upside down." Use the same formula, but run i from n down to 1. You do not need a new formula.

"Print Pascal's triangle." Every row starts and ends with 1. Every number inside is the sum of the two numbers just above it. Build each row from the row before.

"Print only row 30 of Pascal's triangle." Start with 1. Each next number is the last one times (n - k), divided by (k + 1). Multiply first, then divide, so nothing gets rounded away.

One thing to volunteer: "I always write a small table first: row number, spaces, stars. Once the table is right, the code is easy."

Next: 4.0.11 Reverse a String and Reverse the Words. The first string problem, and the reason Python strings cannot be changed in place.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet