☕ DSA Java Articles

Topics › Basics › Patterns

Pattern 21

Medium TUF ID 414 A2Z

Java source ↗ Edit this article ↗

Problem

Given a positive integer n, print a hollow rectangle of size n × n: stars along the four borders and spaces everywhere inside. The same idea extends to an rows × cols rectangle, and a general version is included.

Constraints: 1 ≤ n ≤ 100 or so. For n = 1 the single cell is a border cell and is printed as a star; for n = 2 there is no interior yet.

Example 1

n = 4
****
*  *
*  *
****

First and last rows are solid; the two middle rows have stars only at the ends.

Example 2

n = 5
*****
*   *
*   *
*   *
*****

Three hollow rows between two solid ones.

Reading the pattern

Unlike the triangles, every row here has the same length, so the loops are a plain n × n grid: for i in 0..n-1, for j in 0..n-1. The entire pattern lives in the cell rule: a cell (i, j) is a star if it lies on any of the four borders, i.e. if

i == 0 || i == n - 1 || j == 0 || j == n - 1

and a space otherwise. This “decide each cell from its coordinates” style is the one that scales to arbitrary two-dimensional figures: diagonals (i == j), checkerboards ((i + j) % 2 == 0), frames of thickness t (min(i, j, n-1-i, n-1-j) < t), and so on.

A second observation gives a very different program: the rectangle contains only two distinct rows, a solid one (*****) and a hollow one (* *). Build each once and concatenate solid + hollow × (n - 2) + solid. That is the “row template” view, and String.repeat makes it a few lines.

Both methods return the figure as a single String with a newline after every row, so main compares them with expected strings and checks that every n yields exactly 4n - 4 stars (for n ≥ 2) with a blank interior.

Approach 1: Visit every cell and apply the border rule

Intuition. Loop over all n^2 cells. For each one, check whether it touches a border; append '*' if it does and ' ' otherwise. There is no special-casing of the first or last row because the rule covers them automatically through i == 0 and i == n - 1.

Algorithm.

  1. For i from 0 to n - 1:
  2. For j from 0 to n - 1: border = (i == 0 || i == n - 1 || j == 0 || j == n - 1); append '*' if border, else ' '.
  3. End the row with a newline.
static String nestedLoops(int n) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            boolean border = i == 0 || i == n - 1 || j == 0 || j == n - 1;
            sb.append(border ? '*' : ' ');
        }
        sb.append('\n');
    }
    return sb.toString();
}

Complexity. Time O(n^2): one constant-time decision per cell. Space O(n^2) for the output string, constant extra memory.

Note border ? '*' : ' ': both branches are char, so the conditional expression has type char and append(char) is chosen. If one branch were a String, the whole expression would become a String and still work; mixing a char with an int would be the trap, since the expression would then be an int and print a number.

Approach 2: Two row templates and repeat

Intuition. Only two kinds of row exist. solid is n stars; hollow is a star, n - 2 spaces, and a star. The figure is solid, then n - 2 copies of hollow, then solid again. Including the newline inside each template makes hollow.repeat(n - 2) produce complete rows.

Two small sizes need care. For n = 1 there is a single row *, not two solid rows, so it is handled first. For n = 2 the template formula works unchanged: hollow would be ** but is repeated zero times, leaving two solid rows.

Algorithm.

  1. If n ≤ 0 return ""; if n == 1 return "*\n".
  2. solid = "*" × n + "\n", hollow = "*" + " " × (n - 2) + "*\n".
  3. Return solid + hollow × (n - 2) + solid.
static String withRepeat(int n) {
    if (n <= 0) return "";
    if (n == 1) return "*\n";
    String solid = "*".repeat(n) + "\n";
    String hollow = "*" + " ".repeat(n - 2) + "*\n";
    return solid + hollow.repeat(n - 2) + solid;
}

Dry run for n = 4:

piece value
solid ****\n
hollow * *\n
hollow.repeat(2) * *\n* *\n
result ****\n* *\n* *\n****\n

Complexity. Time O(n^2): repeat copies n - 2 rows of n + 1 characters. Space O(n^2) for the output plus O(n) for the two templates.

General rectangle

The cell rule does not care whether the grid is square. Replace n by rows for the row tests and by cols for the column tests:

static String rectangle(int rows, int cols) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            boolean border = i == 0 || i == rows - 1 || j == 0 || j == cols - 1;
            sb.append(border ? '*' : ' ');
        }
        sb.append('\n');
    }
    return sb.toString();
}

rectangle(n, n) must equal the square versions, and the tests check that for every n up to 20, together with a few non-square cases such as rectangle(3, 5), which is *****, * *, *****.

Complexity. Time and output space O(rows × cols).

Edge cases and pitfalls