Topics › Basics › Patterns

Pattern 22

Medium TUF ID 415 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given a positive integer n, print the number pattern: a square grid with 2n - 1 rows and 2n - 1 columns made of concentric square rings. The outermost ring is filled with n, the next ring inside it with n - 1, and so on down to the single centre cell, which holds 1. Numbers in a row are separated by single spaces.

Constraints: 1 ≤ n ≤ 50 or so; the grid has (2n - 1)^2 cells.

Example 1

n = 3
3 3 3 3 3
3 2 2 2 3
3 2 1 2 3
3 2 2 2 3
3 3 3 3 3

A 5 × 5 grid: ring of 3s, ring of 2s, centre 1.

Example 2

n = 4
4 4 4 4 4 4 4
4 3 3 3 3 3 4
4 3 2 2 2 3 4
4 3 2 1 2 3 4
4 3 2 2 2 3 4
4 3 3 3 3 3 4
4 4 4 4 4 4 4

A 7 × 7 grid with four rings.

Reading the pattern

This is the first pattern in the series where the value of a cell depends on both coordinates in a non-trivial way, so it is worth finding the right description before coding. Let m = 2n - 1 be the side length and use 0-based coordinates (i, j).

A cell on the outer border has value n. A cell one step in from every border has value n - 1. In general, if a cell’s distance to the nearest border is d = min(i, j, m - 1 - i, m - 1 - j), its value is n - d. Check: the border has d = 0, value n; the centre (n - 1, n - 1) has d = n - 1, value 1.

The same rings can be described from the inside out. The centre is at c = n - 1. The Chebyshev distance (king-move distance) from the centre is max(|i - c|, |j - c|), which is 0 at the centre and n - 1 on the border, so the value is 1 + max(|i - c|, |j - c|). Rings are exactly the level sets of this distance, which is why they are squares rather than circles.

Three programs follow. The first paints rings onto a grid and is the most literal. The other two compute each cell with one of the two formulas above. All three fill an int[][] and hand it to a shared render helper that joins the numbers with spaces, so the output format lives in one place.

Approach 1: Paint the rings from the outside in

Intuition. Fill the whole m × m grid with n. Then fill the inner (m - 2) × (m - 2) square with n - 1, overwriting the centre of the previous fill. Repeat with a smaller square and a smaller value until the single centre cell gets 1. Each cell is written once per ring that contains it; the last write wins and is the correct value.

Algorithm.

1. If n ≤ 0 return "". Let m = 2n - 1 and create g[m][m].
2. For layer from 0 to n - 1: set every cell with layer ≤ i, j ≤ m - 1 - layer to n - layer.
3. Render the grid.

static String paintLayers(int n) {
    int m = 2 * n - 1;
    if (n <= 0) return "";
    int[][] g = new int[m][m];
    for (int layer = 0; layer < n; layer++) {           // square from (layer, layer) to (m-1-layer, m-1-layer)
        int value = n - layer;
        for (int i = layer; i < m - layer; i++) {
            for (int j = layer; j < m - layer; j++) g[i][j] = value;
        }
    }
    return render(g);
}

Complexity. Time O(n^3): layer k repaints a square of side m - 2k, and the sum of those areas over n layers is about (2n)^3 / 6. Space O(n^2) for the grid and the output.

This approach is slower than necessary, but it is the one that most directly mirrors the picture, and for pattern-sized n the cubic cost is irrelevant. Its value is as a baseline: the two formula approaches must reproduce it exactly, and the tests check that for n up to 12.

Approach 2: Distance to the nearest border

Intuition. Compute each cell independently. A cell’s ring index is how far it is from the closest of the four borders: top = i, left = j, bottom = m - 1 - i, right = m - 1 - j. The value is n minus the minimum of those four.

Algorithm.

1. If n ≤ 0 return "". Let m = 2n - 1.
2. For every (i, j): g[i][j] = n - min(i, j, m - 1 - i, m - 1 - j).
3. Render the grid.

static String borderDistance(int n) {
    int m = 2 * n - 1;
    if (n <= 0) return "";
    int[][] g = new int[m][m];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            int top = i, left = j, bottom = m - 1 - i, right = m - 1 - j;
            g[i][j] = n - Math.min(Math.min(top, bottom), Math.min(left, right));
        }
    }
    return render(g);
}

Dry run for n = 3 (m = 5), row i = 1:

Row 1 is 3 2 2 2 3, as in Example 1.

Complexity. Time O(n^2): constant work per cell. Space O(n^2) for the grid and output.

Approach 3: Distance from the centre

Intuition. Measure from the middle instead of from the edges. With centre c = n - 1, the Chebyshev distance max(|i - c|, |j - c|) is 0 at the centre and increases by one per ring, so the value is 1 + max(|i - c|, |j - c|). This formulation needs no m - 1 - i style mirroring and makes the ring structure obvious: a ring is all cells at the same Chebyshev distance.

Algorithm.

1. If n ≤ 0 return "". Let m = 2n - 1, c = n - 1.
2. For every (i, j): g[i][j] = 1 + max(|i - c|, |j - c|).
3. Render the grid.

static String centreDistance(int n) {
    int m = 2 * n - 1;
    if (n <= 0) return "";
    int c = n - 1;                                      // centre index
    int[][] g = new int[m][m];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            g[i][j] = 1 + Math.max(Math.abs(i - c), Math.abs(j - c));
        }
    }
    return render(g);
}

Why are the two formulas equal? For a cell at row i, min(i, m - 1 - i) = (n - 1) - |i - c|, since m - 1 = 2c. Taking the minimum over both axes gives min(top, bottom, left, right) = (n - 1) - max(|i - c|, |j - c|), and n - ((n - 1) - max(...)) = 1 + max(...).

Complexity. Time O(n^2), space O(n^2) for the grid and output.

Rendering

All three approaches share one helper that turns the grid into text:

static String render(int[][] g) {
    StringBuilder sb = new StringBuilder();
    for (int[] row : g) {
        for (int j = 0; j < row.length; j++) {
            if (j > 0) sb.append(' ');
            sb.append(row[j]);
        }
        sb.append('\n');
    }
    return sb.toString();
}

Keeping the output format in one place means that switching to no separators, or to fixed-width columns, is a one-line change that affects all approaches at once.

Edge cases and pitfalls

• n = 0. m would be -1, and new int[-1][-1] throws NegativeArraySizeException. All three methods return "" before allocating.
• n = 1. A 1 × 1 grid containing 1. Both formulas give 1 for the only cell, and the paint approach paints one layer.
• Grid size. The side is 2n - 1, not n or 2n. Only an odd side has a single centre cell, which is what makes the innermost ring a lone 1.
• Minimum of four, not two. Taking min(i, j) alone gives the correct values in the top-left quadrant only; the bottom and right distances m - 1 - i and m - 1 - j are what fold the other three quadrants in.
• Off by one in the mirrored distances. The last index is m - 1, so the distance to the bottom border is m - 1 - i. Using m - i shifts the rings and breaks the symmetry; the tests catch it because they check that each row equals its mirror row and that each ring k has exactly 8(k - 1) cells.
• Multi-digit numbers. For n ≥ 10 the outer rings print two-digit numbers and the columns no longer line up visually. The separator-based format is still unambiguous; pad with String.format("%2d", v) if alignment matters.
• Separators. The original pattern prints the digits with no separators (4444444). With spaces the output is readable and parseable for any n; the tests split on spaces to recover the grid.

Related problems

• Pattern 21 is the special case of this idea with only the outermost ring drawn.
• Pattern 17 uses the one-dimensional version of “peak minus distance from the centre” for letters.
• Pattern 20 applies the same distance formula to the star count per row.
• Pattern 13 is the simpler case where a cell’s value depends only on its row position and a running count.