Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Diamond Pattern

Try it yourself
EasyProblem

Description

Given n, return a diamond of stars, 2n - 1 rows high, as a list of rows. The rows grow like a pyramid, row i with 2i - 1 stars, up to 2n - 1 stars in the middle row, then shrink back the same way. Every row is centred, and none has spaces after its stars.

Examples

Example 1

Input: n = 3

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

Explanation: Up to 5 stars in row 3, then back down to 3 and 1: five rows.

Example 2

Input: n = 1

Output: ["*"]

Explanation: One row with one star.

Example 3

Input: n = 2

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

Explanation: 1 star, 3 stars, 1 star.

Constraints

  • 1 ≤ n ≤ 100

Editorial

Approach - Build Each Row from Its Counts

Intuition

The top half, down to the middle row, is a pyramid: row i has n - i spaces and 2i - 1 stars. The bottom half is the same rows in reverse, without the middle row a second time. So build the pyramid's n rows, then add them again from the second-to-last back to the first.

Step-by-Step Explanation

Let's trace Example 1, n = 3:

  1. Row 1: 2 spaces, then 1 star.
  2. Row 2: 1 space, then 3 stars.
  3. Row 3: 0 spaces, then 5 stars, the widest row.
  4. Row 4: 1 space, then 3 stars.
  5. Row 5: 2 spaces, then 1 star.
  6. Return the 5 rows.

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

Algorithm

  1. Build the pyramid: for i from 1 to n, a row of n - i spaces and 2i - 1 stars.
  2. Add the pyramid's rows again in reverse, starting from the second-to-last.
  3. Return all 2n - 1 rows.

Code

class Solution {
public:
    vector<string> diamond(int n) {
        vector<string> top;
        for (int i = 1; i <= n; i++) top.push_back(string(n - i, ' ') + string(2 * i - 1, '*'));
        vector<string> rows = top;
        for (int i = n - 2; i >= 0; i--) rows.push_back(top[i]);   // back up, leaving out the middle row
        return rows;
    }
};

from typing import List

class Solution:
    def diamond(self, n: int) -> List[str]:
        top = [" " * (n - i) + "*" * (2 * i - 1) for i in range(1, n + 1)]
        return top + top[-2::-1]            # back up, leaving out the middle row

import java.util.*;

class Solution {
    public List<String> diamond(int n) {
        List<String> top = new ArrayList<>();
        for (int i = 1; i <= n; i++) top.add(" ".repeat(n - i) + "*".repeat(2 * i - 1));
        List<String> rows = new ArrayList<>(top);
        for (int i = n - 2; i >= 0; i--) rows.add(top.get(i));   // back up, leaving out the middle row
        return rows;
    }
}

var diamond = function(n) {
    const top = [];
    for (let i = 1; i <= n; i++) top.push(" ".repeat(n - i) + "*".repeat(2 * i - 1));
    const rows = [...top];
    for (let i = n - 2; i >= 0; i--) rows.push(top[i]);   // back up, leaving out the middle row
    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.

Repeating the middle row. return top + top[::-1]

On n = 3 it returns [" *", " ***", "*****", "*****", " ***", " *"]; the answer is [" *", " ***", "*****", " ***", " *"]. The widest row is the middle, and it appears once. Going back up from the full top half repeats it: start from the row above it.

Padding the right side too. + " " * (n - i)

On n = 3 it returns [" * ", " *** ", "*****", " *** ", " * "]; the answer is [" *", " ***", "*****", " ***", " *"]. Spaces after the stars are invisible, but they're part of the string, and the answer has none. Only the spaces before the stars centre the row.

Repeating the top half. return top + top[:-1]

On n = 3 it returns [" *", " ***", "*****", " *", " ***"]; the answer is [" *", " ***", "*****", " ***", " *"]. The bottom half is the top half in reverse order, shrinking. Appending the top half again makes it grow a second time.

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.