Foundations · Nested loops

Pattern printing, derived not guessed

Q: What is the time complexity of printing an n-row pyramid?

O(n²) . Row i prints n - i spaces and 2i - 1 stars, so the run totals n² stars plus n(n-1)/2 spaces — that is (3n² - n)/2 characters, or 35 for n = 5 . You cannot beat it, because the output itself contains that many characters.

Q: Your loop starts at i = 0 instead of 1. What changes?

Every formula shifts by one. With i running from 0 to n-1 , a pyramid row becomes n - 1 - i spaces and 2i + 1 stars. Pick one convention and write every formula in it — mixing 0-based and 1-based inside the same pattern is the bug that actually shows up.

Every star pattern is the same two questions asked once per row: how many spaces, then how many characters. Derive both from the row number and you can print any shape without counting by eye.

Print a pyramid one character at a time →

Row i1, 2, 3 … n — one turn of the outer loop per line

→

Spaces = n − iprinted first; they push the row to the right

→

Stars = 2i − 1the visible part of the row

→

Newlineend the line, hand control back to the outer loop

01 The idea

Two loops, one question per row

A pattern is a picture made of characters. Your program cannot draw it. It can only print one character at a time, left to right and top to bottom, and it can never go back. So you break the picture into rows, and for each row you answer one question: which characters, in what order, and how many of each. The outer loop walks the rows. The inner loop prints the characters of the row it is standing on.

Everything hard about pattern printing is deciding how many times that inner loop should run. That count is always a formula in the row number. So do not guess the spaces: draw the pattern on paper, number the rows, count the characters on each row, and read the formula off the counts.

For every row, write down two numbers before you write any code: how many spaces, then how many stars. Both are formulas in the row number i. The loops are just those two numbers, typed out.

Nested loopA loop inside another loop. The inner loop runs from start to finish on every single turn of the outer loop.

Outer loopOne turn per line of output. A 5-row pattern means the outer loop runs exactly 5 times, whatever the shape is.

Row index iThe outer loop's counter. Every count in the pattern — spaces, stars, digits — is written as a formula in i.

02 Worked example

A 5-row pyramid, traced row by row

Take n = 5 and derive the pyramid one row at a time. A dot marks a space the program actually prints; a green cell is a star. Row i needs n − i spaces and 2i − 1 stars — check both formulas on every row before you trust them.

i = 1····*5−1 = 4 spaces, 2(1)−1 = 1 star

i = 2···***5−2 = 3 spaces, 2(2)−1 = 3 stars

i = 3··*****5−3 = 2 spaces, 2(3)−1 = 5 stars

i = 4·*******5−4 = 1 space, 2(4)−1 = 7 stars

i = 5*********5−5 = 0 spaces, 2(5)−1 = 9 stars — widest row is 2n−1

Read the two columns of numbers on their own. Spaces go 4, 3, 2, 1, 0 and stars go 1, 3, 5, 7, 9. Those two sequences are the entire program, and the totals fall straight out of them: 4+3+2+1+0 = 10 spaces and 1+3+5+7+9 = 25 stars, so 35 characters for a 5-row pyramid. Every pattern you will be asked for is a different pair of sequences, derived exactly this way.

03 Mechanics

From five typed strings to two formulas

The version on the left is what most people write first: count the spaces by eye, type each line. It is correct, and it is a dead end — it prints a 5-row pyramid and nothing else. The version on the right prints the same picture, but every count comes from i, so the same six lines print 3 rows or 20.

Naive — one string per row

print "    *"print "   ***"print "  *****"print " *******"print "*********"

Derived — counts from the row index

for i = 1 to n:    spaces = n - i    stars  = 2*i - 1    repeat spaces times: print " "    repeat stars  times: print "*"    print newline

The counts are named before anything prints. spaces and stars exist as values you can compare against the trace in section 02. A wrong pyramid then costs you one arithmetic error to find instead of five string literals to re-count by eye.

n became an input. The typed version is welded to five rows. The follow-up question is always "now do it for n = 7", and the derived version already does — the picture never appears in the code, only the rule that generates it.

Spaces are emitted before stars. Output moves left to right and cannot go back, so the padding has to exist before the thing it pads. Swap lines 4 and 5 and you print a left-aligned staircase with trailing blanks, not a pyramid.

05 Cheat sheet

Five shapes worth memorising

Pattern (n rows, i from 1)	Row i prints	Total stars
Solid square	`n stars`	`n²`
Right triangle	`i stars`	`n(n+1)/2`
Inverted right triangle	`n − i + 1 stars`	`n(n+1)/2`
Pyramid	`n − i spaces, 2i − 1 stars`	`n²`
Hollow square	`star only on the border`	`4n − 4 (n ≥ 2)`

Time is O(n²)Not because the loops are slow, but because the output is that big. A pyramid is (3n² − n)/2 characters — 35 of them for n = 5. You cannot emit that many characters in fewer than that many steps.

Space is O(1)Print each character as you compute it and you store nothing but the counters. Build each row into a string first and it becomes O(n); build the whole picture into a 2-D array and it becomes O(n²).

Pick 0-based or 1-based onceWith i from 1 to n a pyramid row is n − i spaces and 2i − 1 stars. With i from 0 to n − 1 it is n − 1 − i and 2i + 1. Mixing the two inside one pattern is the bug you will actually hit.

06 Where & why

You will not ship a pyramid

Nested-loop printing is not an algorithm you will put into production. Its value is that it forces you to turn a picture into arithmetic, which is the same move every grid, matrix and DP-table problem asks for later.

Reach for the derive-then-print method when…

The output is a fixed gridEvery line has a count you can write down before printing. If you can fill a table of row, spaces and characters by hand, the loops write themselves.

The shape is symmetricPyramids, diamonds and hourglasses are two triangles glued together. Derive one half, then reuse or mirror the same two formulas for the other.

You are in a screening roundTCS NQT, Infosys and Wipro first rounds still open with a pattern. It is a five-minute question if you derive the counts and a twenty-minute question if you guess them.

You are new to a languagePrinting a pyramid exercises loops, counters and output formatting in about ten lines. It is the fastest check that you can drive an unfamiliar language's basics.

Use something else when…

Situation	Better choice	Why
The shape depends on data, not on the row number	Fill a 2-D array, print it at the end	An array lets you write cells in any order. Direct printing can only go left to right, top to bottom, and never revisit a cell.
The output goes to a file, a UI or a log	Build each row as a string, then emit	Direct printing costs one write per character — about n² writes. Building rows costs n writes and one string per row of O(n) space.
Rows are irregular, like a calendar or a report	Padding and alignment helpers	Left-pad and centre functions already handle width. Hand-counted spaces break the moment a value's width changes.
The pattern is a fractal, like Sierpinski's triangle	Recursion over the grid	There is no simple per-row count to derive. The shape is defined in terms of smaller copies of itself, so the code has to be too.

You will not print a pyramid at work. You will constantly write an inner loop whose bound depends on the outer loop's counter — upper-triangular matrix walks, pair generation with j starting at i + 1, every DP table fill. That is what this lesson is really teaching.

07 Interview questions

What they actually ask

Pattern questions open screening tests and language rounds. What is being marked is never the printed shape — it is whether you derived the counts or guessed at them.

What is a nested loop?

A loop written inside the body of another loop. The inner loop runs from start to finish on every single turn of the outer loop, so if the outer runs n times and the inner runs m times, the inner body executes n × m times. In pattern printing the outer loop counts lines and the inner loop counts characters on the line it is currently on.

How do you decide what the inner loop bound should be?

Draw the target pattern on paper, number the rows, and count the characters on each row. Write those counts next to the row numbers and read off the formula that maps one to the other. For a 5-row pyramid the star counts are 1, 3, 5, 7, 9 against rows 1 to 5, which is 2i - 1.

What is the time complexity of printing an n-row pyramid?

O(n²). Row i prints n - i spaces and 2i - 1 stars, so the run totals n² stars plus n(n-1)/2 spaces — that is (3n² - n)/2 characters, or 35 for n = 5. You cannot beat it, because the output itself contains that many characters.

Is the space complexity also quadratic?

No, it is O(1) when you print each character as you compute it, because you keep only the loop counters. It becomes O(n) if you build each row into a string before printing, since the widest row is 2n - 1 characters. Only building the whole picture into a 2-D array first makes it O(n²).

Why must the spaces be printed before the stars?

Because output moves left to right and cannot go back. The spaces are what push the stars to the right, so they have to be emitted first. Print the stars first and you get a left-aligned staircase with trailing blanks, which is a different shape entirely.

Your loop starts at i = 0 instead of 1. What changes?

Every formula shifts by one. With i running from 0 to n-1, a pyramid row becomes n - 1 - i spaces and 2i + 1 stars. Pick one convention and write every formula in it — mixing 0-based and 1-based inside the same pattern is the bug that actually shows up.

How would you print a hollow square instead of a solid one?

Keep the same two loops and add a condition on the character rather than on the count. Print a star when i is the first or last row or j is the first or last column, and a space otherwise. For an n × n square with n ≥ 2 that is 4n - 4 stars, so 16 when n = 5.

What is an inverted pyramid, and how does the formula change?

The same shape flipped top to bottom, so the widest row comes first. Replace i with n - i + 1 in the derivation: row i prints i - 1 spaces and 2(n - i) + 1 stars. Check it at both ends with n = 5 — row 1 gives 0 spaces and 9 stars, row 5 gives 4 spaces and 1 star.

Right triangle versus pyramid — what is the actual difference in code?

One extra inner loop. A right triangle has no leading spaces, so row i is simply i stars. A pyramid needs a spaces loop before the stars loop, and the star count changes from i to 2i - 1 so the row stays symmetric about the centre. Everything else is identical.

Can you print a pyramid with a single loop?

Hard

Print n centred rows of Pascal’s triangle, where row i holds the binomial coefficients C(i-1, 0) up to C(i-1, i-1), so row 5 reads 1 4 6 4 1. Keep n at 5 or less so every entry stays a single digit and the spacing formula still holds.

Follow-up

The values are not a formula in j alone: each entry is the sum of the two above it, so the loop filling a row must read the row before it. This is the step from pattern printing to a DP table.

Show the hint

Keep the previous row in a list; the new row’s entry at position j is prev[j-1] + prev[j], with 1 at both ends.