Problem overview
The method printX receives a positive integer n and prints an n by n grid in which the two diagonals are made of x characters and every other cell is -. Each line is printed with println.
For n = 5 the output is:
x---x
-x-x-
--x--
-x-x-
x---x
Every line has two x characters, except the middle line of an odd-sized grid, where both diagonals meet in the same cell and there is only one.
Approach: two moving columns
The cells that hold an x follow a simple pattern. On line 0, the x characters are in column 0 and column n - 1. On each next line, the first one moves one column to the right and the second one moves one column to the left, so the two approach each other until they cross in the middle.
That means two integers, firstX and secondX, are enough to describe every line. For one line, check each column index: if it equals firstX or secondX, write x; otherwise write -. Then move the two numbers and repeat for the next line.
The program has two parts, mirroring the idea: printX goes through the lines and moves the two numbers, and a helper, buildString, builds one line from n, firstX and secondX.
Another way to see the same thing: on line i, the two x characters are in columns i and n - 1 - i. The lesson keeps two running variables instead of computing that formula, which gives the same positions and is easy to follow one line at a time. Both approaches look at every cell once, so neither changes the amount of work.
Step by step
- Declare
firstXandsecondXwithvar, starting at0andn - 1. Both change on each line, so they can't beval. - Loop over the lines with
for (i <- 0 until n). The loop variable only counts the lines. - Build and print the line. Call
buildString(n, firstX, secondX), store the result in avalnamedstrand pass it toprintln. - Move the x positions. Add 1 to
firstXand subtract 1 fromsecondX. Scala has no++or--, so use+= 1and-= 1. - Write the helper's signature. It takes three
Intvalues and returns aString. - Start with an empty
varstring that collects the characters of the line. - Loop over the column indices with
0 until n. - Append
"x"when the column equalsfirstXorsecondX. The||operator is true when at least one of its sides is true. - Append
"-"otherwise. - Return the string after the loop, once every column has been decided.
The solution in Scala
class Solution {
def printX(n: Int): Unit = {
var firstX = 0
var secondX = n - 1
for (i <- 0 until n) {
val str = buildString(n, firstX, secondX)
println(str)
firstX += 1
secondX -= 1
}
}
def buildString(n: Int, firstX: Int, secondX: Int): String = {
var str = ""
for (i <- 0 until n) {
if (i == firstX || i == secondX) {
str += "x"
} else {
str += "-"
}
}
return str
}
}
The Scala details worth a closer look:
- Two variables called
str. The one inprintXis avalholding one finished line, and the one inbuildStringis a separatevar. Each lives only inside its own method, so they don't interfere. - Parameters are read-only. The helper's parameters
firstXandsecondXhave the same names as the variables inprintX, but they are separate copies of the values. The helper cannot change the caller's variables, and it couldn't reassign its own parameters either. if/elseas a statement. Both branches only changestr, so theifis used for its effect here. In Scala,ifis also an expression with a value, sostr += (if (cond) "x" else "-")would do the same.==compares values. ForInt, that is what is wanted. For strings and other objects, Scala's==callsequals, so it compares contents rather than references.returnis optional. The last expression of a block is its value, sostralone on the last line would be enough.
Complexity
Time: O(n²). The method prints n lines, and each line is built by looping over n columns.
Space: O(n). Only one line exists at a time, and the counters are plain integers.
Edge cases and common mistakes
n = 1. Both positions are 0, so the single line isx.- Even
n. The two diagonals never share a cell, so every line has twoxcharacters. Forn = 4the output isx--x,-xx-,-xx-,x--x. Forn = 2it isxxtwice. - The middle line of an odd
n. Both positions are equal there, so the same condition catches them and prints onex. No special case is needed. - Starting at 1 instead of 0. Columns here are numbered from 0, as with every Scala index. Starting
firstXat 1 andsecondXatnshifts the diagonals by one column, andsecondXwould start at columnn, which is outside the line. - Using
&&instead of||. A column can't be both positions, except in the middle, so almost noxwould be printed. - Forgetting to move the counters. Without the two updates, every line looks like the first.
- Returning inside the loop. A
return strplaced inside the loop inbuildStringends it after the first column, so every line would have a single character.
Testing
n = 1printsx.n = 2printsxxtwice.n = 4printsx--x,-xx-,-xx-,x--x.n = 5prints the five lines shown above.
