Skip to main content
CodePeet

Hollow Square

Try it yourself
EasyProblem

Description

Given n, return an n by n square of stars that's hollow inside, as a list of rows. The first and last rows are n stars; every row between them is a star, n - 2 spaces and a star.

Examples

Example 1

Input: n = 4

Output: ["", " ", " ", ""]

Explanation: The top and bottom rows are solid; the two rows between have a star at each end and 2 spaces inside.

Example 2

Input: n = 1

Output: ["*"]

Explanation: A 1 by 1 square is a single star.

Example 3

Input: n = 2

Output: ["", ""]

Explanation: With only two rows, both are solid: there's no inside.

Constraints

  • 1 ≤ n ≤ 100

Editorial

Approach - Build Each Row from Its Counts

Intuition

Two kinds of row: the border rows, first and last, are solid, and every row between them is a star at each end with spaces inside. Decide the kind by the row's index, i == 0 or i == n - 1, so a square of side 1, whose only row is both first and last, comes out as a single star.

Step-by-Step Explanation

Let's trace Example 1, n = 4:

  1. Row 1: the first row, 4 stars.
  2. Row 2: a star, 2 spaces and a star.
  3. Row 3: a star, 2 spaces and a star.
  4. Row 4: the last row, 4 stars.
  5. Return the 4 rows.

Hollow Square — The rows, built one per step from the top; the row just built is lit.

Algorithm

  1. For each row index i from 0 to n - 1: if it's the first or the last, add n stars; otherwise add a star, n - 2 spaces and a star.
  2. Return the rows.

Code

class Solution {
public:
    vector<string> hollowSquare(int n) {
        vector<string> rows;
        for (int i = 0; i < n; i++) {
            if (i == 0 || i == n - 1) rows.push_back(string(n, '*'));
            else rows.push_back("*" + string(n - 2, ' ') + "*");
        }
        return rows;
    }
};

from typing import List

class Solution:
    def hollowSquare(self, n: int) -> List[str]:
        rows = []
        for i in range(n):
            if i == 0 or i == n - 1:
                rows.append("*" * n)
            else:
                rows.append("*" + " " * (n - 2) + "*")
        return rows

import java.util.*;

class Solution {
    public List<String> hollowSquare(int n) {
        List<String> rows = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (i == 0 || i == n - 1) rows.add("*".repeat(n));
            else rows.add("*" + " ".repeat(n - 2) + "*");
        }
        return rows;
    }
}

var hollowSquare = function(n) {
    const rows = [];
    for (let i = 0; i < n; i++) {
        if (i === 0 || i === n - 1) rows.push("*".repeat(n));
        else rows.push("*" + " ".repeat(n - 2) + "*");
    }
    return rows;
};

Complexity Analysis

Time Complexity: O(n²)

There are O(n) rows of O(n) characters, and each character is written once.

Space Complexity: O(n²)

The rows of the answer.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Adding the top and bottom rows separately. return ["*" * n] + middle + ["*" * n]

On n = 1 it returns ["*", "*"]; the answer is ["*"]. Adding a top row and a bottom row always gives at least two rows, but a square of side 1 has only one. Decide each row by its index instead: the first or the last is solid.

Putting one space too many inside. " " * (n - 1)

On n = 4 it returns ["****", "* *", "* *", "****"]; the answer is ["****", "* *", "* *", "****"]. A middle row is n characters wide: two stars and n - 2 spaces between them. With n - 1 spaces the sides stick out by one.

Filling the square. return ["*" * n for _ in range(n)]

On n = 4 it returns ["****", "****", "****", "****"]; the answer is ["****", "* *", "* *", "****"]. Only the border gets stars: inside the first and last rows, each row is a star, spaces, and a star.

Where This Pattern Is Taught

This problem practises nested counting: for each row, how many of each character, and building the row as a string. It's taught in Python for DSA, Java for DSA, C++ for DSA and JavaScript for DSA.