Start learning free

LESSON 194 OF 414 · NESTED LOOPS

Print X in Rust: Two Moving Columns per Line

Practice O(n²) Read the full explanation

Given a positive integer n print matrix containing an X as in the example below

Example:

Input: n = 5
Output:
x---x
-x-x-
--x--
-x-x-
x---x
Explanation:
Each line contains exactly n = 5 characters and two 'x's.
Each diagonal contains 'x'

Hints:

Notice that on each line there will be exactly two x and the other characters are all -. The only exception is the middle line which will have only one x. How can we use this info?

We can print the matrix line by line. For each line we need to know the two columns where we should print x. How can we know these two columns for every line?

We'll store the columns' indices in two variables firstX and secondX, initially equal to the first and the last column respectively for the first line.
How should these variables change from line to line?

firstX should get incremented and secondX should get decremented.
Now for each line, you know the 'special' columns. How will you print that line?

We'll use a for loop to iterate through every column index of the line.
What should we do inside the loop?

We should use an if - else statement and check if the current index is firstX or secondX and if so, print x. Otherwise, print -.

STEP 1 OF 9

Guided

Ctrl + Enter to check

RUST · NESTED LOOPS

Print X in Rust, explained

Problem overview

The function print_x receives a positive integer n as an i32 and prints a square of n lines with n characters each. The two diagonals of the square are drawn with x and every other cell is a -.

For n = 5 the output is:

x---x
-x-x-
--x--
-x-x-
x---x

Each line has two x's, except the middle line, where the two diagonals cross and there is only one.

Approach: follow the two diagonals

Looking at the picture line by line, the x's move predictably. On line 0 they sit at the two ends, at columns 0 and n - 1. On each following line the left x moves one column to the right and the right x moves one column to the left. They are two points walking toward each other, which is exactly what the two diagonals of a square are.

So the program keeps two numbers, the column of the first x and the column of the second, and updates them after each line. To print a line, it walks over the columns 0 to n - 1 and writes x when the column equals either number and - otherwise.

When the two numbers meet in the middle of an odd square, they are equal. The test "column equals first or second" is still true for that one column, so the middle line gets one x without any special case. Past the middle the two numbers cross over, and the same test keeps working with the roles swapped.

Here is the state for n = 5 as the loop runs. The column positions are those used when the line is built:

Line	`first_x`	`second_x`	Printed
0	0	4	`x---x`
1	1	3	`-x-x-`
2	2	2	`--x--`
3	3	1	`-x-x-`
4	4	0	`x---x`

On line 3 the first number is larger than the second. That doesn't matter, because the test only asks whether a column equals one of them, and it never compares the two numbers with each other.

Step by step

Declare the two columns with let mut: first_x starts at 0 and second_x starts at n - 1. They are mutable because they move on every line.
Loop once per line with for _ in 0..n. The range excludes n, so the body runs n times, and the loop variable is not used, so it is named _.
Print one line. Inside the loop, call a helper build_string(n, first_x, second_x) with Self::build_string and print the result with println!. The lesson writes the helper afterwards.
Move the x's. After printing, add 1 to first_x and subtract 1 from second_x.
Write the helper's signature above print_x: three i32 parameters, n, first_x and second_x, and a String result.
Create the result as an empty mutable String named result.
Loop over the columns with for index in 0..n. The index takes the values 0 to n - 1.
Choose the character. If index == first_x || index == second_x, push 'x'; otherwise push '-'. The operator || is true when at least one side is true.
Return result after the loop, once every column has been filled.

The solution in Rust

impl Solution {
    fn build_string(n: i32, first_x: i32, second_x: i32) -> String {
        let mut result = String::new();
        for index in 0..n {
            if index == first_x || index == second_x {
                result.push('x');
            } else {
                result.push('-');
            }
        }
        return result;
    }

    fn print_x(n: i32) {
        let mut first_x = 0;
        let mut second_x = n - 1;
        for _ in 0..n {
            println!("{}", Self::build_string(n, first_x, second_x));
            first_x += 1;
            second_x -= 1;
        }
    }
}

The Rust details in these lines:

No ++ or --. Rust has no increment or decrement operators. Use += 1 and -= 1.
Inferred types. first_x and second_x are not annotated, but they are passed where an i32 is expected and compared with index, so Rust infers i32.
Signed on purpose. After the last line has been printed, second_x has dropped to -1, whatever n is. A usize could not hold that, and in a debug build the subtraction would panic. With i32 the value is just a number that matches no column, and it is never used again.
Chars, not strings. 'x' and '-' in single quotes are char values, which is what String::push takes.
Calling the helper. The helper has no self, so the call is Self::build_string(...), and the returned String goes straight into println!.
Explicit return. return result; ends the function. Dropping the word return and the semicolon would mean the same thing.

Complexity

Time: O(n²). The outer loop makes n lines, and building each line visits n columns. The output itself contains n² characters, so no solution can be faster.

Space: O(n). Only one line of n characters is held at a time.

Edge cases and common mistakes

n = 1. Both columns are 0, so the single line is x.
Even n. The columns never coincide; they swap places in the middle instead. For n = 4 the output is x--x, -xx-, -xx-, x--x, and for n = 2 it is xx twice. The same code handles both parities.
Starting at 1 instead of 0. Columns here are 0-based, since index starts at 0. Starting first_x at 1 and second_x at n shifts the whole picture and drops an x from the first line.
Moving the x's before printing. The first line would already be the second one.
Stopping the inner loop at n - 1. The last column would never be written, and the lines would be one character short.
Using && instead of ||. A column can't equal two different numbers, so the line would be all dashes except in the middle.

Testing

n = 1 prints x.
n = 2 prints xx and xx.
n = 3 prints x-x, -x-, x-x.
n = 4 prints x--x, -xx-, -xx-, x--x.

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free