Why this matters
A zigzag is a line that goes down, then up, then down again. A wave is the same movement, drawn across a page. Programs use this pattern to lay out text in a zigzag, to draw simple charts and to make a symbol bounce from side to side.
The earlier lesson on hourglass, arrow and cross shapes computed each row from its row number. A zigzag works differently. Where the marker is on one column depends on where it was on the column before. The program has to remember one thing from step to step, and that thing is the direction. This lesson teaches a single variable that holds the direction, and how to use it safely.
This lesson uses C++ with the standard output stream std::cout. Compile the samples with g++ -std=c++20 -Wall. The output shown under each sample was produced by running the sample on g++ 15.2.
The idea: a marker that turns at the edges
Picture a grid with 4 rows and 12 columns. Every cell is blank. A marker starts in row 0, column 0. At each step the marker moves one column to the right. It also moves one row down or one row up. It keeps going down until it reaches the bottom row. Then it turns around and goes up until it reaches the top row, and turns again.
Write the row of the marker for each column. This table is the plan the code will follow:
column: 0 1 2 3 4 5 6 7 8 9 10 11
row: 0 1 2 3 2 1 0 1 2 3 2 1The plan changes direction twice. The marker moves down until row 3, which is the last row. It does not move to row 4, because that row does not exist. So it turns around and moves up.
A variable is a named box in memory that holds a value. A direction variable is a variable that holds how the marker moves on the next step. Here it holds +1 for down and -1 for up. Adding the direction to the row moves the marker by one row in that direction. Since row + dir is either one row below or one row above, the marker is always in a neighbouring row.
Trace the first four columns
Work through the first few steps by hand. The grid has 4 rows, so the last row is row 3.
- Column 0. The marker is at row 0 and the direction is +1 (down). The next row would be 1, which is inside the grid. The direction stays +1. The marker moves to row 1.
- Column 1. The marker is at row 1. The next row would be 2, inside the grid. The marker moves to row 2.
- Column 2. The marker is at row 2. The next row would be 3, which is the last row, so it is still inside. The marker moves to row 3.
- Column 3. The marker is at row 3. The next row would be 4. Row 4 is outside the grid, so the direction flips from +1 to -1. The marker moves to row 2, which is 3 plus -1.
- Column 4. The marker is at row 2 and the direction is -1. The next row would be 1, inside the grid. The marker moves to row 1.
The code below follows these same steps.
The first program
This program draws the wave with one star for each column. The grid is a list of 4 strings. Each string is one row, 12 characters long and filled with spaces. Setting grid[row][col] to '*' changes one character in one row.
#include <iostream>
#include <string>
#include <vector>
// Draws one star per column. The star moves down one row per column,
// and turns around when the next row would be off the grid.
int main() {
const int rows = 4;
const int cols = 12;
std::vector<std::string> grid(rows, std::string(cols, ' '));
int row = 0;
int dir = 1; // +1 means down, -1 means up
for (int col = 0; col < cols; ++col) {
grid[row][col] = '*';
int next = row + dir;
if (next < 0 || next >= rows) {
dir = -dir; // turn around at the top or bottom edge
}
row += dir;
}
for (const std::string& line : grid) {
std::cout << line << '\n';
}
}The output is:
* *
* * * *
* * * *
* * Each line in the output is one row of the grid. The first star is at the top left. The stars in column 3 and column 9 are in the bottom row, and the stars in column 0 and column 6 are in the top row. Trailing spaces are part of the grid, so the lines are the full 12 characters wide.
Why the check comes before the move
The program looks at the next row before it moves. This order matters. The check is next < 0 || next >= rows. The first part asks whether the next row is above the top, and the second part asks whether it is below the bottom. The || symbol means "or". If either is true, the direction flips. Then the marker moves in the new direction.
If the program moved first and checked second, the marker would already be off the grid when the check ran. The check is the only thing that keeps the marker inside the rows. It must run before every move.
A short note on the words. next is a new variable that holds the row the marker would reach. It is not the same as row. Keeping the two names separate makes the check easy to read.
A second example: the zigzag text conversion
The first program placed stars. The next program places letters, and then reads them back in a different order. This is a well-known problem: write the characters of a word in a zigzag over a number of rows, then read the rows from top to bottom.
Take the word ABCDE and 2 rows. Write the letters in a zigzag:
A C E
B DRow 0 holds A, C and E. Row 1 holds B and D. Read the top row first, then the bottom row. The result is ACEBD.
The program needs a place to store each row. Instead of a grid of spaces, each row is a std::string that starts empty. Each letter is added to the end of the string for the current row with +=.
#include <iostream>
#include <string>
#include <vector>
// Writes the characters of `text` in a zigzag over `num_rows` rows,
// then reads the rows from top to bottom to get the new string.
std::string zigzag_convert(const std::string& text, int num_rows) {
if (num_rows < 2) {
return text;
}
std::vector<std::string> rows(num_rows);
int row = 0;
int dir = 1;
for (char c : text) {
rows[row] += c;
int next = row + dir;
if (next < 0 || next >= num_rows) {
dir = -dir;
}
row += dir;
}
std::string result;
for (const std::string& r : rows) {
result += r;
}
return result;
}
int main() {
std::cout << zigzag_convert("PAYPALISHIRING", 3) << '\n';
std::cout << zigzag_convert("PAYPALISHIRING", 4) << '\n';
std::cout << zigzag_convert("ABC", 1) << '\n';
std::cout << zigzag_convert("", 3) << "|\n";
}The output is:
PAHNAPLSIIGYIR
PINALSIGYAHRPI
ABC
|Read the first line by hand to check it. With 3 rows, the letters go to rows 0, 1, 2, 1, 0, 1, 2, and so on. Row 0 collects P, A, H, N. Row 1 collects A, P, L, S, I, I, G. Row 2 collects Y, I, R. Joining the rows gives PAHNAPLSIIGYIR.
The function takes two inputs, a std::string and an int, and returns a std::string. The const std::string& in the parameter list is a reference. A reference is a second name for a value that already exists, so the function reads the caller's text without making a copy.
Look at the first if in the function. With one row, every letter stays in row 0, and the direction logic would try to move the marker to row 1 or row -1. The guard returns the text unchanged before the loop starts. Mistake 1 below shows what goes wrong without this guard.
A third example: writing a word on a wave
The last program puts each letter of a word on a wave, one letter per two columns. It returns the rows as a list, so the caller decides how to print them. This is a small step up from the first two programs because it uses a function with a parameter for the number of rows and a parameter for the text.
#include <iostream>
#include <string>
#include <string_view>
#include <vector>
// Places each character of `text` on the wave, one column per character.
// Returns one string per row. Spaces fill every cell the wave does not use.
std::vector<std::string> make_wave(std::string_view text, int rows) {
std::vector<std::string> grid(rows, std::string(text.size() * 2, ' '));
int row = 0;
int dir = 1;
int col = 0;
for (char c : text) {
grid[row][col] = c;
int next = row + dir;
if (next < 0 || next >= rows) {
dir = -dir;
}
row += dir;
col += 2; // one free column between letters
}
return grid;
}
int main() {
for (const std::string& line : make_wave("WAVE", 3)) {
std::cout << line << '\n';
}
std::cout << "--\n";
for (const std::string& line : make_wave("SEARCH", 4)) {
std::cout << line << '\n';
}
}The output is:
W
A E
V
--
S
E H
A C
R The parameter type is std::string_view, which is a read-only view of text. It does not copy the characters. A string literal such as "WAVE" or a std::string both convert to a std::string_view without extra work. It is declared in the <string_view> header.
There are two counters here. row tracks the vertical position of the wave, and col tracks the horizontal position. col goes up by 2 at each letter, which leaves one blank column between letters. The width of each row is text.size() * 2, so the last letter always fits.
Check the word WAVE with 3 rows by hand. The letters go to rows 0, 1, 2, 1. W is in row 0, column 0. A is in row 1, column 2. V is in row 2, column 4. E is in row 1, column 6. The output has E in the second line at position 6, which matches.
Edge cases: one row and empty text
A zigzag needs at least two rows to have a top edge and a bottom edge. With one row, the top row and the bottom row are the same row. The marker would have to turn at both edges at once, and it has no row to move to.
The guard if (num_rows < 2) in zigzag_convert handles this case by returning the input unchanged. The other choice is to reject the input with an error. Either choice is fine, as long as the code does not reach the loop with one row.
Empty text is a different case. The loop runs zero times, so nothing is written. The row strings are all empty, and the result is an empty string. The sample above prints | on its own, which shows that the output is empty.
Common mistakes
Most mistakes in this lesson are off-by-one errors, or errors where a row number is outside the grid. Each mistake below was run to get the error message.
Mistake 1: a single row
With one row, the marker has no room. The next row is either -1 or 1, and neither is inside the grid. This sample uses .at(), which checks the index and throws an error when the index is wrong.
#include <iostream>
#include <string>
#include <vector>
int main() {
const int rows = 1;
std::vector<std::string> grid(rows, std::string(5, ' '));
int row = 0;
int dir = 1;
for (int col = 0; col < 5; ++col) {
grid.at(row).at(col) = '*';
int next = row + dir;
if (next < 0 || next >= rows) {
dir = -dir;
}
row += dir;
}
}The program stops with this message:
terminate called after throwing an instance of 'std::out_of_range'
what(): vector::_M_range_check: __n (which is 18446744073709551615) >= this->size() (which is 1)The number 18446744073709551615 is -1 shown as an unsigned number. The index type of .at() is unsigned, so a negative index is turned into a very large positive one. This is why the error message looks strange. The message says the index is too big, but the real problem is that the index is -1.
Mistake 2: an unsigned row number
A std::size_t is an unsigned integer. It cannot hold a negative value. Adding -1 to an unsigned 0 does not give -1. It wraps around to the largest unsigned value.
#include <cstddef>
#include <string>
#include <vector>
int main() {
const std::size_t rows = 3;
std::vector<std::string> grid(rows, std::string(5, ' '));
std::size_t row = 0;
int dir = -1;
row += dir;
grid.at(row)[0] = '*';
}The output is:
terminate called after throwing an instance of 'std::out_of_range'
what(): vector::_M_range_check: __n (which is 18446744073709551615) >= this->size() (which is 3)The fix is to keep row and dir as int, the same as the samples above. Use the int value for the arithmetic and check it before using it as an index.
Mistake 3: an off-by-one edge check
The bottom row is rows - 1, not rows. If the check compares with rows, the marker never turns at the bottom. It goes one row too far and reaches a row that does not exist.
#include <string>
#include <vector>
int main() {
const int rows = 3;
const int cols = 8;
std::vector<std::string> grid(rows, std::string(cols, ' '));
int row = 0;
int dir = 1;
for (int col = 0; col < cols; ++col) {
grid.at(row).at(col) = '*';
if (row == rows) {
dir = -1;
}
row += dir;
}
}The output is:
terminate called after throwing an instance of 'std::out_of_range'
what(): vector::_M_range_check: __n (which is 3) >= this->size() (which is 3)The index 3 is one past the last row when there are 3 rows, which are rows 0, 1 and 2. The fix is to compare with rows - 1, or to use the check next >= rows that the sample uses.
Why not use [] and skip the check?
The samples in the lesson use grid[row][col] without .at(). That is what the working programs use. [] does not check the index. An index outside the grid is undefined behaviour. This term means the program may crash, print wrong output, or seem to work for a while. A program with an off-by-one error can print something that looks right. Keep .at() while you learn, because it turns a silent error into a message you can read.
Practice
Exercise 1. Trace a wave with 3 rows and 7 columns. Write the row of the marker for each column, from column 0 to column 6. Which row holds the star in column 5?
Show the answer
The rows are 0, 1, 2, 1, 0, 1, 2. The marker moves 0, 1, 2, then turns at row 2 and goes up to 1 and 0, then turns at row 0 and goes down to 1 and 2. Column 5 is row 1.
Exercise 2. Change the first program so it has 2 rows and 6 columns. Predict the two output lines before you run it.
Show the answer
The rows are 0, 1, 0, 1, 0, 1. Row 0 has stars in columns 0, 2 and 4, and row 1 has stars in columns 1, 3 and 5. The output is * * * on the first line and * * * on the second line, with a trailing space after the first line. The program prints exactly that.
Exercise 3. Predict the output of zigzag_convert("ABCDE", 2).
Show the answer
The answer is ACEBD. Row 0 gets A, C and E. Row 1 gets B and D. Joining row 0 and then row 1 gives ACEBD.
Exercise 4. Change make_wave so each letter is 3 columns from the last one instead of 2. Only two lines of the program need to change. Which two lines are they?
Show the answer
The first line to change is the size of each row, which should be text.size() * 3. The second is the step, col += 3. A test with the word HI! and 2 rows prints this, with brackets added to show the ends of each line:
[H ! ]
[ I ]Exercise 5. Explain why the direction variable has type int and not std::size_t, using the words "negative" and "wrap" in your answer.
Show the answer
The direction is -1 on the way up, and that is a negative number. An unsigned type cannot hold a negative number. When -1 is added to an unsigned value of 0, the result wraps around to a very large positive number, which the program then uses as an index. An int holds -1 correctly, and the check next < 0 can then find the edge.
Summary
- A zigzag marker is a row number plus a direction variable that holds +1 or -1.
- Check the next row before the move, and flip the direction if the next row is outside the grid.
- The same loop can write a word on a wave, or write letters into rows and read the rows back.
- A single row has no top or bottom edge to turn at, so guard that case before the loop starts.
- Keep row and direction as
int. Unsigned arithmetic wraps around, and a bad index throws an error when you use.at().