Pyramids and hollow shapes

Why this matters

The full pyramid and the hollow shapes are the patterns that appear most often in tests and interviews. They use every skill from the last two lessons: spaces as part of a row, formulas in i, and a rule for each position. They also add one new skill, which is making a decision for each position with an if.

Hollow shapes are a good test of how you think. A beginner often writes a separate loop for each edge of the shape. An experienced programmer writes one pair of loops that visits every position, and uses a single test to decide what goes there. The second way is shorter, easier to check and easier to change.

New words for this lesson

• Pyramid. A shape where each row is wider than the row above it and the rows are centred on the same middle line.
• Centred. Lined up so the middle of each row sits at the same column. Centring needs leading spaces, which are part of the row.
• Border. The outer edge of a shape. In a square, the border is the first row, the last row, the first column and the last column.
• Hollow. Printed as an outline, with empty space inside. The opposite of solid or filled.
• Width. The number of characters in a row, counting spaces. A row of 5 stars has width 5, and so does a row with 2 spaces and 3 stars.
• Condition. A test that gives true or false. An if statement runs its block only when its condition is true.
• Logical or ||. Reads as "or". a || b is true when at least one side is true. It is the operator you need for "on the border, meaning in the first row or the last row or ...".

The full pyramid

Here is a pyramid with four rows. The top row has one star in the middle, and each row below adds two more stars, one on each side.

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

Make the table first. Row i counts from 1 at the top.

The spaces are n - i, because the bottom row has none and each row above adds one. The stars are 2 * i - 1, which gives the odd numbers 1, 3, 5, 7. The row always has (n - i) + (2 * i - 1) = n + i - 1 characters. That is not the same for every row, but the spaces on the left move the stars to the middle, so the pyramid is centred.

The row is built in two inner loops, as in the right-aligned triangle. The first loop prints the spaces. The second prints the stars.

Type 4 into the Input box.

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

Trace the second row for n = 4. The outer counter i is 2. The first inner loop runs while s <= 2, so it prints two spaces. The second inner loop runs while j <= 3, so it prints three stars. The row is ***. The third row prints one space and five stars, and the bottom row prints none and seven.

The picture below marks each position in the 4 by 7 grid. The shaded cells are the stars, and the blank cells are spaces. You can count the cells in each row and match them with the table.

Grid of seven columns and four rows showing the cells of a four-row pyramid, with the star cells shaded in the middle

Why the formula for stars uses 2 * i - 1

Some learners try 2 * i for the star count. That gives 2, 4, 6, 8 stars, which is an even number. An even number of stars cannot sit exactly in the middle, because a centre star needs an odd count. Each row must add one star on the left and one on the right, which means the count goes up by two each row, starting from 1. The formula 2 * i - 1 gives exactly that: 1, 3, 5, 7.

Number pyramid

Replace the stars with the row number. Each row shows its number as many times as the row count, with a space between the numbers.

   1
  2 2
 3 3 3
4 4 4 4

Row i has i numbers. The first number is at the start of the row content, so the leading spaces are n - i. The numbers are separated by spaces, which means the printed width of the content is 2 * i - 1 characters: i digits and i - 1 gaps. So the content width is the same as the star count in the full pyramid.

The space before each number after the first is the trick. You can print a space before every number and then trim it, or you can print a space only when j < i. The second way is the clean one, because it never prints a trailing space.

Type 4 into the Input box.

   1
  2 2
 3 3 3
4 4 4 4

Notice that the program prints i, not j. The column number would give 1, 1 2, 1 2 3 and so on. The value in each row comes from the row counter.

Hollow square

A hollow square has a border of stars and spaces inside. For n = 5 it looks like this.

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

Every position in the grid is on the border or inside it. A position is on the border when it is in the first row, the last row, the first column or the last column. Print a star at those positions and a space at the others.

This is the first pattern that needs a decision for each position. The test is a condition with ||, which means "or":

if (i == 1 || i == n || j == 1 || j == n) {
    cout << "*";
} else {
    cout << " ";
}

The condition is true when i is 1, or i is n, or j is 1, or j is n. Any one of those makes the position a border. The else branch handles everything else, which is the inside.

Type 5 into the Input box.

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

The inner loop visits all n positions in each row, including the spaces. That is different from the earlier patterns, where the inner loop stopped early. Here every cell is visited, and the if picks what goes in it. This is the general method for any hollow shape: visit every position, and decide with a test.

Checking the border test by hand

Take the row i = 3 in the example with n = 5. The condition for j = 1 is true, because j == 1. For j = 2, j = 3 and j = 4, none of the four tests is true, so the else branch prints spaces. For j = 5, j == n is true, so a star is printed. The row is * *, which matches the picture.

For the first row i = 1, the first test is true for every j, so every position is a star. That gives the full top edge.

Hollow rectangle with two inputs

A square has the same number of rows and columns. A rectangle does not. To print a rectangle, read two numbers: the number of rows and the number of columns. In C++ you can read several values in a row with cin >> twice.

int rows, cols;
cin >> rows >> cols;

The first >> puts the first number into rows, and the second >> puts the next number into cols. The spaces between the numbers in the input do not matter, because cin skips them.

Type 4 8 into the Input box.

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

The test is the same as the square, except the last row and the last column use their own limits. i == rows checks the bottom row, and j == cols checks the right column. Name your limits after what they mean, and the test reads like a sentence.

Hollow right triangle

A hollow right triangle has a left edge, a diagonal edge and a bottom edge. Row i has i columns. The left edge is column 1. The diagonal edge is the last column of the row, j == i. The bottom edge is the last row, i == n.

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

The test is j == 1 || j == i || i == n. The inner loop runs while j <= i, so the row only covers its own width. The bottom row is special because its condition i == n is true for every j, and it prints a full line of stars.

Type 5 into the Input box.

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

Check row 3. The row has three columns. Column 1 is a star because j == 1. Column 2 is a space, because none of the tests is true. Column 3 is a star because j == i, which is 3 == 3. The row is * *.

Hollow pyramid

A hollow pyramid combines the centring of the full pyramid with the border test. Each row has leading spaces first, then a row of width 2 * i - 1 that holds the border. The first and last positions of the row are stars. The bottom row is a full line of stars.

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

The border test is j == 1 || j == 2 * i - 1 || i == n. The first condition is the left edge. The second is the right edge of this row, which is at column 2 * i - 1, not at a fixed column. Because the width changes from row to row, the right edge must use the formula. This is a common mistake: using n in place of 2 * i - 1 for the right edge.

Type 5 into the Input box.

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

The first row of the output has four leading spaces and one star. In this row, column 1 and column 2 * i - 1 are the same column, so the star is printed once. The inner loop does not need a special case for this, because both tests point at the same position.

What happens inside the computer

An if statement is a decision. When the program reaches it, the condition is evaluated and gives true or false. If it is true, the first block runs. If it is false, the else block runs. The program then continues after the if in the same way for the next position.

The comparison j == 1 does not change j. It only reads the value and gives a yes or no. A single == would assign a value, which is a different job. This is a source of errors, so read the condition as a question. j == 1 asks whether j is equal to 1.

The || operator is evaluated from left to right, and it stops early. If the first test is true, C++ does not look at the rest, because the answer is already known. This is called short-circuit evaluation. It means i == 1 || i == n skips the second test when i is 1. The result is the same either way, so the shortcut only saves a little time.

When the program runs the hollow square with n = 5, it makes 25 decisions, one for each cell. Each decision reads i, j and n, which are plain variables in memory. There is no list of stars stored anywhere. The shape exists only as the sequence of characters the program prints.

Time and space

A hollow shape visits every cell in its bounding box. A bounding box is the smallest rectangle that holds the shape. For the hollow square that is n * n cells, so the time is O(n squared). For the hollow pyramid the bounding box is n rows by 2 * n - 1 columns, which is still O(n squared).

The space is O(1). The program stores only n, i, j and a few counters. The shape is never saved as a grid in memory. If you wrote the shape into a two-dimensional array first and printed it later, the space would be O(n squared), and that would be a waste when you can decide each cell on the spot.

Edge cases

• n = 1. Every shape with a border prints one star. The full pyramid prints one star in the middle. The hollow square prints a single star, because the top row and the bottom row are the same row. Test this first, because it shows whether your border test handles the overlap.
• n = 2. The hollow square prints a filled 2 by 2 block of stars, because every cell is on the border. The hollow pyramid for n = 2 prints a row with a single star and a full row of three stars. Work out each row by hand before you test.
• Zero or negative n. No loop runs, so nothing prints. This is the same as the earlier lessons.
• The rectangle with rows and columns swapped. 4 8 and 8 4 give different shapes. Check which number goes first in the problem statement.

Common mistakes

• Using && where || is needed. A position is on the border when any one of the tests is true, so the tests join with ||. The && operator needs every test to be true, which almost never happens. The output then has almost no stars.
• Using n for the right edge of the hollow pyramid. The row width is 2 * i - 1, so the right edge moves. Using n puts the star at the wrong place in every row above the bottom.
• Printing trailing spaces. In the hollow square the last column is a star, so no trailing spaces appear. In the hollow triangle, the rows end at the diagonal, so again there is none. If you print the full width for every row, you add spaces at the end of rows where the picture should stop.
• Confusing the two edges of the triangle. The triangle's diagonal edge is at j == i, not at j == n. A test with n makes every row end at the same column.
• Using = instead of ==. if (j = 1) assigns 1 to j, which is always true, so the branch always runs. The compiler may warn you, but the program still compiles.

Debugging walkthrough: a hollow square that prints a line of stars

A learner wrote this program to print a hollow square with n = 3. The output is wrong, and the learner cannot see why.

#include <iostream>
using namespace std;
 
int main() {
    int n = 3;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == 1 || i == n && j == 1 || j == n) {
                cout << "*";
            } else {
                cout << " ";
            }
        }
        cout << "\n";
    }
    return 0;
}

The output is:

***
  *
* *

The first row is correct. The second row has its right star but no left star. The bottom row is missing its middle star. The bug is the condition. In C++, && binds more tightly than ||, which means the expression is read as i == 1 || (i == n && j == 1) || j == n. The left edge test j == 1 only applies when i == n, so the left edge of the middle rows is missing. The fix is to put each test in its own position with its own ||, which is exactly the condition from the square:

if (i == 1 || i == n || j == 1 || j == n) {

Read the condition from the output. A star in row 2 at column 3 means the j == n test is working. A missing star at column 1 means the j == 1 test is not being reached. This matches the operator precedence problem. When an output looks wrong in a particular place, find the test that controls that place and check it on paper for that one value.

A cell-by-cell table for the hollow pyramid

The hollow pyramid is the shape most learners get wrong, so it is worth writing out every cell. Take n = 4. The bottom row is the widest, with seven cells, and each row above is two cells narrower. For each row, the table below records where the leading spaces end, where the border stars are, and whether the row is a full row of stars.

Read the first row of the table with care. The width is 1, so the first star and the last star are the same cell. The test j == 1 || j == 2 * i - 1 is true for j = 1, and it is printed once, not twice. Nothing in the program needs a special case for it.

Now read the bottom row. Its width is 7, so j runs from 1 to 7. The test j == 1 is true at the first cell, and j == 7 is true at the last. The test i == n is also true for every cell, because i is 4 and n is 4. So every cell in the bottom row is a star, and the row is solid. The third test is what makes the bottom row full. Without it, the bottom row would be a hollow outline with spaces inside, which is not the shape in the picture.

Here is the position of the stars for row 2 in absolute terms. Two leading spaces come first, so the row starts at column 3 of the picture. The first star is at j = 1, which is absolute column 3. The second star is at j = 3, which is absolute column 5. The gap between them is at j = 2, which is absolute column 4. The picture of row 2 is therefore two spaces, a star, a space and a star, which reads * * in the centred form.

This table is a good way to check any hollow shape. Write one row per line of the picture, then fill in the tests for each cell. If the table and the program disagree, the program has the bug.

Centring and even widths

A full pyramid is centred because each row has an odd width, 2 * i - 1, and the spaces are chosen so that the middle star sits on the same column in every row. An odd width has a single middle cell, so the centre is exact.

What if a shape needs an even width? Suppose you want a pyramid with two stars at the top instead of one. There is no middle cell in a two-cell row. The two stars sit either side of the centre line, and the spaces on the left are one fewer than you might expect. For this course you should avoid even widths in pyramids. Keep the width odd, and the centring formula works.

The same issue appears when the characters are not all the same width. A row of numbers such as 1 10 1 has a middle that falls on a space, or on a digit, depending on how many digits the numbers have. In a pyramid of two-digit numbers, the centre moves from row to row. The fix is to compute the width of each row as a number of characters, and use that width in the spaces formula. This is the same idea as the setw tool in the number lesson.

Debugging: a pyramid that leans

A learner wrote the full pyramid like this. The shape is wrong, and it seems to lean to the right as it grows.

#include <iostream>
using namespace std;
 
int main() {
    int n = 4;
    for (int i = 1; i <= n; i++) {
        for (int s = 1; s <= i; s++) {
            cout << " ";
        }
        for (int j = 1; j <= 2 * i - 1; j++) {
            cout << "*";
        }
        cout << "\n";
    }
    return 0;
}

The output is:

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

Look at the first row. It has one space and one star, which means the star is in column 2 of the picture. The bottom row has four spaces, so its stars start at column 5. A centred pyramid would keep the middle star at the same column in every row, and this one does not. The shape leans because the spaces grow with i, but they should shrink. The bug is the limit of the spaces loop: it is i, not n - i.

The fix is one change, from s <= i to s <= n - i. After the fix the first row has three spaces, and the bottom row has none. That matches the table in the lesson. The bottom row is now the only row that starts at column 1, and every other row starts a little further in, which is what a pyramid looks like.

This is a good example of a bug that a single output line can show. You do not need to run the whole program in your head. Pick one row, count its spaces, and compare with the table. If the count is wrong, the formula is wrong.

Interview thinking

When an interviewer asks for a hollow shape, the strongest answer is the same method every time.

1. "I will visit every cell in the bounding box with two loops."
2. "For each cell, I decide whether it is on the border, using i and j against the first and last values."
3. "For a pyramid, the first and last columns are functions of i, so I use 2 * i - 1 for the right edge."
4. "I check n = 1 and n = 2, because those are where the border tests overlap."
5. "Time is O(n squared), extra space is O(1)."

If the interviewer asks you to avoid the double loop, you can print each border part separately with its own loop. That works, but it needs more code and more chances for a mistake. Say that the single-loop method is clearer, and offer the other only if asked.

Why the border test works for every hollow shape

Every hollow shape in this lesson uses the same idea, so it is worth stating the idea once. A cell is on the border of a shape when it is at the edge of its row or at the edge of the whole shape. The edge of a row is the first cell and the last cell of that row's width. The edge of the whole shape is the first row, the last row, or a side that is straight up and down.

For the hollow square, the row width is n in every row, so the row edges are column 1 and column n. The shape edges are row 1 and row n. So the test is j == 1 || j == n || i == 1 || i == n. For the hollow pyramid, the row width changes, so the row edges are column 1 and column 2 * i - 1. The shape edge is the bottom row, i == n. For the hollow right triangle, the row edges are column 1 and column i, and the shape edge is the bottom row. Each shape has the same two kinds of edge, and the test is simply the list of them joined by ||.

This is a useful way to design a new hollow shape. Ask two questions. Which cells are at the edge of their row? Which rows or columns are at the edge of the whole shape? Write those as tests, join them with ||, and check each one on a small picture.

Interview follow-ups for hollow shapes

Interviewers often ask for a change to a hollow shape. Prepare for these questions.

What does a hollow square of size 1 print, and why is that a special case? It prints one star. Every edge test is true for the one cell, so the cell is a star. The special case is that the top row and the bottom row are the same row, so a program that prints the top row and then the bottom row separately would print the star twice. The single loop with a combined test avoids this.

Can you print a hollow shape without an if? Yes, but only with more code. You could print the top edge with one loop, the sides with a loop for each middle row, and the bottom edge with another loop. That works and it is more to read, so the if is the better answer, unless the interviewer asks for a specific structure.

How do you make a hollow square with a diagonal line? Add a third test, i == j, to the border test. A cell is a star when it is on the border or on the diagonal. This is a useful drill, because it shows that the test is a list of reasons for a star, and any reason can be added.

What is the cost? The program visits every cell in the bounding box, which is O(n squared) for an n by n square. The extra space is O(1), because the shape is never stored in memory.

How would you test a hollow shape quickly? Check the first row, the last row, one middle row and the join row, if the shape has one. Those four rows catch almost every bug in a hollow shape.

Practice

1. Print the full pyramid of height 6, with the stars centred and no trailing spaces.
2. Print a hollow rectangle with 4 rows and 8 columns. Read the two numbers from the Input box.
3. Print the inverted full pyramid for n = 4. Hint: run i from n down to 1 and keep the same spaces and star formulas.
4. Print the number pyramid for n = 5. Then explain what changes when n is 10 or more.
5. Print a hollow square with a diagonal line from the top-left to the bottom-right corner. For n = 4, the output has stars on the border and on the cells where i == j.
6. Print a solid right triangle and a hollow right triangle for the same n, one below the other. Use n = 4.
7. Print a hollow diamond of height n = 3. Hint: use the two-half structure from the diamond lesson, and the border test from the hollow pyramid.
8. Print a plus sign inside an n by n grid for odd n = 5. The middle row and the middle column are stars, and the other cells are spaces.
9. Read rows and cols, and print a checkerboard of * and . where the top-left cell is *. Test with 3 4.
10. Print a hollow pyramid for n = 4 and count the stars on its border. Then write a formula for the number of border stars in a hollow pyramid of height n. Hint: count the top row, the rows between the top and the bottom, and the bottom row separately.

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

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

What you now know

• A pyramid has leading spaces n - i and 2 * i - 1 stars in row i.
• The spaces keep the stars centred, which is why the spaces are part of the row.
• A hollow shape visits every cell and uses one if to decide what to print.
• The border test joins its tests with ||, not &&.
• The right edge of a hollow pyramid moves, so it uses 2 * i - 1.
• Read two numbers with cin >> rows >> cols; when a shape is not square.
• These shapes cost O(n squared) time and O(1) extra space.