Diamonds and advanced patterns

Why this matters

The diamond is the classic pattern question. It combines everything from the earlier lessons: leading spaces, odd star counts, counting up and counting down, and a decision for each position. It also shows an idea that matters far beyond patterns, which is that a hard shape is often two easy shapes put together.

The later part of this lesson covers Pascal's triangle. It is a pattern whose values depend on the values above it, so it is the first pattern in the module that needs a table of values to be remembered. That makes it a bridge to dynamic programming, which you will study later in the course.

New words for this lesson

• Half. One of the two parts of a symmetric shape, such as the top half of a diamond.
• Symmetric. The same on both sides of a middle line. A diamond is symmetric from top to bottom and from left to right.
• Helper function. A small named piece of code that does one job, and that the main program calls. A function is written with a name, a list of parameters (the values it receives) and a body. Here, void row(int n, int i) receives n and i, and returns nothing.
• Parameter. A variable in a function's header that receives a value from the caller. In row(3, 2), the parameter i gets the value 2.
• Return type void. A function that prints but returns nothing. void means "no value comes back".
• Binomial coefficient. A number that counts ways to choose items. You do not need the formula yet. For this lesson, a Pascal triangle value is one of these numbers.
• Table of values. A grid where each cell holds a value, and cells are filled from earlier cells. You will see this idea in the dynamic programming lessons.

The diamond is two pyramids

Look at this diamond with three stars in the middle row.

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

Do not treat it as one pattern. It is two patterns joined together: a full pyramid on top, and an inverted pyramid below. The top half is the full pyramid from the last lesson, with rows i = 1 to n. The bottom half is the same rows counted down, with the widest row left out, because the widest row already appears at the bottom of the top half.

For a diamond with height n, the total number of rows is 2 * n - 1. For n = 3 that is 5 rows.

Make the table for the top half, then reuse it for the bottom.

The bottom half uses the same two formulas, but i runs from n - 1 down to 1. Row n - 1 is 2, so its spaces are 1 and its stars are 3. Row 1 is the last row, with 2 spaces and 1 star.

Type 3 into the Input box.

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

The two loops of the top half and bottom half are the same code, except for the start and the direction of the outer counter. That repetition is a warning sign. In the next section you will remove it with a helper function. First, check the boundary between the halves. The top half ends with the row i = n, which is the widest row. The bottom half starts at i = n - 1, so the widest row is printed only once. If you started the bottom half at n, the widest row would appear twice and the diamond would have a double line in the middle.

Here is the same idea with a bigger diamond, so you can see the widths grow and shrink. The top half has heights 1 to 4, and the bottom half has heights 3 to 1. For n = 4, there are 7 rows.

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

Removing the repetition with a helper function

Both halves print the same kind of row, so the code for one row can live in a function. A function is a named block of code that you call by name. You give it the values it needs, and it does the work.

Here is a function that prints one row of a diamond with height n. It receives the height n and the row number i.

void row(int n, int i) {
    for (int s = 1; s <= n - i; s++) {
        cout << " ";
    }
    for (int j = 1; j <= 2 * i - 1; j++) {
        cout << "*";
    }
    cout << "\n";
}

The word void means the function returns no value. The function prints, and then it ends. The main program then calls it for each row. The top half calls row(n, i) for i from 1 to n. The bottom half calls it for i from n - 1 down to 1.

The function moves the row logic into one place. If you find a mistake in the spaces, you fix it once, and both halves are correct. This is why programmers use functions even in short programs. A function also makes the main program easier to read, because the name row says what the loop does.

Hollow diamond

A hollow diamond has stars on its outline and spaces inside. Look at the picture for n = 3.

  *
 * *
*   *
 * *
  *

Each row has a left star and a right star, with spaces between them. The first row has one star, where the left and right stars are the same position. The widest row, in the middle, has two stars at the far ends.

Inside each row, the test is the same as the hollow pyramid: print a star at the first column and at the last column of the row's width 2 * i - 1, and a space everywhere else. The helper function can hold this test, so both halves stay the same.

Type 3 into the Input box.

  *
 * *
*   *
 * *
  *

Read the main function first. It is very short: two loops that call row. Then read row. It handles one line of output, and that is the whole job. Splitting the work this way is called decomposition, which means breaking a problem into smaller parts with clear jobs.

Note that row is written above main. The compiler reads the file from top to bottom, so it must know about row before main calls it. If you put row below main, you get an error that says the name row was not declared, and the fix is to move the function up or add a declaration before main.

Hourglass

The hourglass is the diamond turned inside out. The top is an inverted pyramid, and the bottom is a full pyramid. Its widest row is at the very top and the very bottom, and its narrowest row is in the middle.

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

The top half counts i down from n to 1, which makes the rows shrink. The bottom half counts i up from 2 to n, which makes them grow. The narrowest row is printed once, because the bottom half starts at 2, not at 1. The leading spaces are n - i in both halves, which keeps the shape centred.

Type 3 into the Input box.

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

The bottom half starts at 2 so that the middle row, which is the single star, is printed only once. The top half already printed i = 1 at the narrow point. Ask yourself, for any shape made of two halves, which row sits on the join, and which half prints it. The answer decides the start of the second loop.

Butterfly

The butterfly is made of two blocks of stars with a gap between them, and the gap grows toward the middle. Here it is for n = 4.

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

Each row has three parts: left stars, a gap of spaces, and right stars. In the top half, row i has i stars on each side, and the gap has 2 * (n - i) spaces. Row 1 has a gap of 6 spaces, row 2 has 4, row 3 has 2, and row 4 has none, which is why the middle row is solid.

The gap uses 2 * (n - i), not n - i. The gap is on both sides of the middle line, so it is twice as wide as one side of the shape. This is a common mistake. A learner who writes n - i gets a gap half the width of the picture.

The bottom half reuses the top half's loops, with i counting down from n - 1 to 1. Row 1 at the bottom is the same as row 1 at the top.

Type 4 into the Input box.

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

Compare the butterfly with the diamond. The diamond's row has one block of stars, but the butterfly's row has two blocks with a gap between them. The number of stars on each side is i, the same as the triangle's row count. The gap is what changes. This is the general technique for a new pattern: find the parts of a row, write one loop for each part, and let the loops follow the same formula with i.

For n = 1 the butterfly is special. The top half prints one star, a gap of zero spaces, and one star, so the row reads **. The bottom half has no rows, because it starts at n - 1 = 0. The output is therefore **, not *. Check the edge cases before you assume a pattern works for n = 1.

Pascal's triangle

Pascal's triangle is a famous number pattern. Each row starts and ends with 1, and every other value is the sum of the two values above it.

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

Check the middle values of row 3. The value 2 is the sum of the 1 above it on the left and the 1 above it on the right. The value 3 in row 4 is the sum of the 1 and the 2 above it, which are in row 3. The rule is simple, and each value needs the values above it.

This rule is what makes Pascal's triangle a table problem. A simple loop that prints one row at a time cannot see the values of the row above, unless the program remembers them. You have two choices.

1. Keep the previous row in an array, and compute each new row from it. This is the most direct method, and it costs memory for one row at a time.
2. Use a formula for each value. The value in row r (counting from 0) and position k (counting from 0) is the number of ways to choose k items from r. The formula can be built from the previous value in the same row. Each value is value * (r - k) / (k + 1) when you move from k to k + 1.

The second method is shorter, and it is the one used in the program below. It keeps only one number at a time, the current value, and updates it. The spaces before each row are n - r - 1, because the top row needs the most spaces.

Here is the diagram of the rule, showing how each cell in the table depends on the two above it.

A small Pascal triangle with arrows from the two cells above each value, showing each cell as the sum of those two

The visualizer below fills a grid in the same order that Pascal's triangle is built, one cell at a time, using values above and to the left. It is a different problem, longest common subsequence, but the habit is the same: each new cell uses cells that are already filled. Step through it and watch which cells the program reads before it writes a new one.

Step through the table above. Watch which earlier cells each new cell reads. You will see that no cell is filled before the cells it depends on. Pascal's triangle works the same way, and the program below follows the same rule.

Type 5 into the Input box.

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

Trace row 2 (counting from 0). The value starts at 1. It prints 1, then value * (2 - 0) / 1 gives 2. It prints 2, then value * (2 - 1) / 2 gives 1. It prints 1, then the loop ends. Row 2 is 1 2 1. The multiplication happens before the division, and the result is always a whole number at each step, so the integer division is exact. Integer division is the normal division for whole numbers, which drops any fraction. Here no fraction is dropped, so the values are exact.

The type is long long, which is a larger whole-number type than int. Pascal values grow fast. A long long can hold numbers up to about 9.2 times 10 to the power of 18. The middle values pass that limit somewhere past row 60, so keep rows small or use a different method for large rows.

What happens inside the computer

Each function call uses memory for its own variables. When main calls row(3, 2), the computer makes a new box for n with value 3 and a new box for i with value 2. These boxes exist only while row runs. When row ends, the boxes are removed, and main continues. The boxes in row do not affect the boxes in main, even when the names match. This is called scope: a variable exists only in the block where it was declared.

In the Pascal program, value is declared inside the outer loop, so it is created fresh for each row and starts at 1 again. If you moved its declaration out of the loop, the value would keep its old state across rows, and the output would be wrong. That is a useful example of where a declaration belongs.

The butterfly and the hourglass use only loops and counters, so their memory is a few integers. The diamond and the hollow diamond use one helper call per row, which adds a small amount of work for the call itself, but the total cost is still the number of characters printed.

Time and space

Each pattern in this lesson prints about n rows of up to 2 * n characters. That is O(n squared) time, because the work is the number of characters printed.

The extra space depends on the method. The diamonds, hourglass and butterfly use O(1) extra space, because they keep only a few counters. The Pascal program also uses O(1) extra space, because it keeps one value at a time. If you stored every row in an array, the space would be O(n squared), which is the cost of a full table.

When an interviewer asks why a Pascal solution uses O(1) space and a table solution uses O(n squared), the answer is the number of values you keep at once. The formula keeps one. The table keeps all of them.

Edge cases

• n = 1 for the diamond. Prints *. The top half has one row and the bottom half has none.
• n = 1 for the hollow diamond. Prints *, because the first star and last star are the same position.
• n = 1 for the butterfly. Prints **, as described above.
• n = 1 for Pascal. Prints 1, which is the only value in the triangle.
• n = 0 for every pattern. Prints nothing, because the first loop does not run. The hourglass also prints nothing, because its loops start at n and 2.
• Very large Pascal rows. The values grow fast, and the multiplication can overflow before the division happens. For rows above about 60, use another method.

Common mistakes

• Printing the widest row twice in a diamond or hourglass. The bottom half must start at n - 1 for the diamond, and at 2 for the hourglass. Count the row on the join only once.
• Starting the bottom half at n instead of n - 1. The output then has a double middle line. Check the join row first.
• Using integer division too early in Pascal. If you write value = value / (k + 1) * (r - k);, the division can drop a fraction before the multiplication, and the values can be wrong. Multiply first, then divide.
• Getting the butterfly gap wrong. The gap is 2 * (n - i), not n - i. Use the picture to check: in row 1 of the n = 4 butterfly, the gap has 6 spaces.
• Forgetting that a helper must be above main. The compiler reads the file top to bottom, so a call to row before its definition is an error. The message says the name was not declared.
• Not testing n = 1. The butterfly prints ** for n = 1, which is a surprise if you expected one star. Many formulas break at n = 1, so always test it.

Debugging walkthrough: the diamond with a double middle

A learner wrote the diamond's bottom half like this, and the output has an extra middle row.

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

The output is:

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

The middle row appears twice. The bottom loop starts at i = n, which is the widest row, so it prints the row again. The fix is to start the bottom loop at n - 1. This is a classic off-by-one error, and the table makes it visible. Write down which row each loop prints, starting with the join row. If the same row number appears in both loops, one of the loops must start one row earlier.

A recipe for any new pattern

When you meet a pattern you have not seen, follow the same steps every time.

1. Draw the pattern with a small n, such as 3 or 4, and mark each space with a dot so it is visible.
2. Write a table with one row for each row of the picture. Columns: row number, spaces, items, and what each item holds.
3. Find a formula for each column of the table. Look for a pattern in the numbers, and check it on the first and last rows.
4. Decide whether the picture is one block or two. If it is symmetric, it is probably two halves. If each row has parts, write one loop for each part.
5. Write the loops. Use a helper function if two halves print the same row.
6. Test with n = 1, n = 2 and a larger n, and check the join row, the first row and the last row by hand.

This recipe works for every pattern in this course. The formulas change, but the steps do not.

Interview thinking

An interviewer who asks for a diamond wants to see three things. First, that you can split a shape into halves and avoid writing the same loop twice. Second, that you check the join row so it is printed once. Third, that you know the cost.

For Pascal's triangle, the interviewer may ask for two methods. Say the table method first, since it is easy to explain: keep the previous row in an array and build the next row from it. Then offer the formula method as a way to keep only one value. Explain the difference in space, and mention the overflow limit. This shows that you understand both the simple solution and the trade-off.

The answer to "what is the complexity" is always the number of values or characters that the program has to produce. For patterns, that is about n squared.

Symmetry: why one half is enough

A symmetric shape repeats itself across a line. The diamond repeats across its middle row, top to bottom, and each row is also the same on its left and right sides. That gives you two ways to save work, and both are worth knowing.

The first way is the one you used: print the top half once, then print the bottom half by counting down. The top half is the part you have to think about. The bottom half is the same rows in reverse, so it needs no new formula. The only question is where the join is. For a diamond the join row belongs to the top half, so the bottom half starts one row below it.

The second way is to note that each row is symmetric on its own. The spaces on the left mirror the spaces on the right, and the stars on the left mirror the stars on the right. That is why a hollow diamond can use a border test that looks at the first and last column of each row, and not at every column between them. The middle columns are never on the border, so testing them would be wasted work.

A symmetric shape can be printed in either direction. A learner who sees a diamond as one pattern will try to write one loop with a clever formula. A learner who sees two halves will write two simple loops. Both work, but the second is easier to check, and that is the reason to choose it.

Pascal's triangle and the binomial formula

The formula used in the Pascal program is not magic. It comes from counting. The value in row r (counting from 0) and position k (also from 0) is the number of ways to choose k items from a group of r items, when order does not matter. This number is written C(r, k), and it is called a binomial coefficient.

Here is a small example that makes the idea concrete. Suppose you have 4 items, labelled A, B, C and D, and you want to choose 2 of them. The pairs are AB, AC, AD, BC, BD and CD, which is 6 pairs. The value C(4, 2) is 6, and row 4 of Pascal's triangle (counting from 0) holds 1, 4, 6, 4, 1. The third value is the 6. That is no accident. Pascal's triangle is a table of these choice counts.

The rule that each value is the sum of two values above it comes from the same counting. To choose k items from r items, you either include the first item or you do not. If you include it, you choose k - 1 items from the other r - 1. If you do not, you choose k items from the other r - 1. The two cases add up, and the sum rule is the Pascal rule.

The formula the program uses is equivalent to the sum rule, and it builds each value from the one before it in the same row. It is written this way:

C(r, k + 1) = C(r, k) * (r - k) / (k + 1)

Going from one position to the next multiplies by the number of items still left, r - k, and divides by the number of items chosen so far, k + 1. Each step gives a whole number, so the integer division in the program is exact. The multiplication must come first, because value / (k + 1) on its own may not be a whole number, and dividing first would drop a fraction and give the wrong answer.

The formula is worth knowing for interviews, because it shows that you can move from a table idea to a direct calculation. It also gives you the O(1) space version of the pattern, since you never need the previous row.

The hourglass and the diamond side by side

The hourglass and the diamond are closely related. Both have two halves, and both use the same row formulas, n - i spaces and 2 * i - 1 stars. The difference is only in the direction of the counter. In the diamond the widest row is in the middle, so the top half counts up and the bottom half counts down. In the hourglass the widest row is at the top and bottom, so the top half counts down and the bottom half counts up.

This difference changes the join row. In the diamond the join is the widest row, and the bottom half must not print it again. In the hourglass the join is the narrowest row, and the bottom half must not print it again either. The rule is the same in both cases: find the row that sits on the join, and let exactly one half print it. The code for the join is the only part you need to change when you turn one shape into the other.

A useful check is the total number of rows. Both shapes have 2 * n - 1 rows. If your count is different, the join is printed twice, or it is missing.

Interview follow-ups for advanced patterns

After a diamond, interviewers often ask for a change to the shape or to the cost. These are the questions to prepare for.

Can you print a diamond of height n with one loop? Yes. Let i run from 1 to 2 * n - 1, and let d = abs(i - n) be how far the row is from the middle. The row then has d spaces and 2 * (n - d) - 1 stars. Check it on paper for n = 3: the top row has d = 2, so 2 spaces and 1 star, and the middle row has d = 0, so 0 spaces and 5 stars. Test the join row as well, because one loop hides it.

What is the cost of printing a diamond? The bounding box is 2 * n - 1 rows of 2 * n - 1 characters, which is about 4 * n squared characters, and about 2 * n squared of them are stars. Both counts are proportional to n squared, so the time is O(n squared). The extra space is O(1).

How would you print Pascal's triangle without storing any row? Use the formula method from this lesson. Each value depends only on the value before it in the same row, so one variable is enough.

What if the Pascal values overflow? Say that the values grow fast, and that long long holds values up to about 9.2 times 10 to the power of 18. For larger rows you can print the values modulo a number, which keeps them small, but that changes the question. Ask the interviewer what the output must be before you change the method.

How do you check a diamond quickly? Check the middle row, the first row and the join. Those three rows catch almost every formula error in a diamond.

Practice

1. Print a diamond with n = 5. Then say which row is printed once by the top half and once by the bottom half, and why.
2. Print the hollow butterfly pattern for n = 4. Hint: print a star only at the first and last column of each side. Think about where the gap goes.
3. Print a number diamond for n = 3 where each row's middle number is i. Hint: reuse the diamond loops, but print i instead of *. Think about whether each row needs one number or several.
4. Print Pascal's triangle for n = 6 using the formula method. Then print it with n = 7 and check the last row against the binomial values 1, 6, 15, 20, 15, 6, 1.
5. Print the hourglass for n = 4 and count the rows. Then explain why the total is 2 * n - 1 for the hourglass as well as the diamond.
6. Print a hollow hourglass for n = 3, using the border test from the hollow pyramid. Hint: the top half and the bottom half each have their own border.
7. Print a solid diamond of letters for n = 3, from the letter pattern in the number and letter lesson. The middle row is ABCBA.
8. Write a helper function void line(int n, char c, int i) that prints i copies of character c preceded by n - i spaces. Use it to print a solid triangle of # for n = 4.
9. Print the first 4 rows of Pascal's triangle with the table method. Keep the previous row in an array of size 10, and build the next row from it. Explain why the array is updated from the right end.
10. Explain, in words and with a small example, why the formula method for Pascal's triangle uses O(1) extra space, and the table method uses O(n squared) space for n rows. Then say which method you would use in an interview and why.

  1
 2 2
3 3 3
 2 2
  1

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

void line(int n, char c, int i) {
    for (int s = 1; s <= n - i; s++) cout << " ";
    for (int k = 1; k <= i; k++) cout << c;
    cout << "\n";
}

What you now know

• A diamond is two pyramids: the top half runs from 1 to n, and the bottom half runs from n - 1 down to 1.
• Print the join row once. The bottom half of a diamond starts one row lower than the top.
• A helper function holds the logic for one row, so two halves can share it.
• A hollow diamond and a hollow pyramid use the same border test on each row.
• The hourglass is an inverted pyramid joined to a pyramid, and its narrowest row is printed once.
• A butterfly row has three parts, and the gap is 2 * (n - i).
• Pascal's triangle builds each value from the two above it. Multiply before you divide, and watch for overflow.
• For any new pattern, draw it, make a table, find the formulas, and test n = 1.
• The cost of any of these patterns is O(n squared) time, and the extra space is O(1) when only a few values are kept at once.