Nested Loop Patterns
Description
Given an integer n representing the number of rows, print various patterns using nested loops. Patterns are formed by printing characters (such as *, numbers, or letters) in specific arrangements controlled by the relationship between the outer loop variable (row) and the inner loop variable (column).
This problem teaches you how nested loops work together: the outer loop controls which row you are on, and the inner loop controls what gets printed in that row. By changing the inner loop's start, end, or step conditions based on the outer loop variable, you can produce triangles, pyramids, diamonds, and more.
Your goal is to understand and implement three fundamental patterns:
- Right Half Pyramid — a right-angled triangle of stars growing from top to bottom
- Inverted Right Half Pyramid — the same triangle flipped upside down
- Full Pyramid — a centered equilateral triangle shape
Examples
Example 1
Input: n = 5, pattern = "Right Half Pyramid"
Output:
*
* *
* * *
* * * *
* * * * *
Explanation: Row 1 has 1 star, row 2 has 2 stars, ..., row 5 has 5 stars. Each row i (1-indexed) prints exactly i stars. The inner loop runs from 1 to i for each row, creating a growing triangle shape.
Example 2
Input: n = 5, pattern = "Inverted Right Half Pyramid"
Output:
* * * * *
* * * *
* * *
* *
*
Explanation: Row 1 has 5 stars, row 2 has 4 stars, ..., row 5 has 1 star. Each row i (1-indexed) prints n - i + 1 stars. The triangle shrinks from top to bottom — the reverse of Example 1.
Example 3
Input: n = 5, pattern = "Full Pyramid"
Output:
*
* * *
* * * * *
* * * * * * *
* * * * * * * * *
Explanation: Each row is centered by printing leading spaces before the stars. Row i (1-indexed) has n - i leading spaces and 2*i - 1 stars. Row 1: 4 spaces + 1 star. Row 2: 3 spaces + 3 stars. Row 5: 0 spaces + 9 stars. The leading spaces push the stars rightward, creating the pyramid shape.
Constraints
- 1 ≤ n ≤ 100 (number of rows)
- Patterns use the
*character by default (can be adapted for numbers or letters) - Each star is followed by a space for readability
- The full pyramid requires leading spaces for center alignment
Editorial
Brute Force
Intuition
The most basic way to think about printing patterns is to treat each row as an independent problem. For each row, you need to figure out: how many characters to print?
Imagine you are laying bricks to build a staircase. For the first step, you place 1 brick. For the second step, you place 2 bricks. For the third, 3 bricks, and so on. Each step (row) is independent — you just need to know the step number to know how many bricks to place.
The brute force approach focuses on the simplest pattern first: the Right Half Pyramid. The relationship is straightforward — row number equals star count. We use two loops: an outer loop to go through rows, and an inner loop to print the right number of stars in each row.
Step-by-Step Explanation
Let's trace through building a Right Half Pyramid with n = 4:
Step 1: Outer loop starts: i = 1 (first row). Inner loop runs from j = 1 to j = 1. Print 1 star. Move to next line.
Output so far: *
Step 2: Outer loop: i = 2 (second row). Inner loop runs from j = 1 to j = 2. Print 2 stars. Move to next line.
Output so far:
*
* *
Step 3: Outer loop: i = 3 (third row). Inner loop runs from j = 1 to j = 3. Print 3 stars. Move to next line.
Output so far:
*
* *
* * *
Step 4: Outer loop: i = 4 (fourth row). Inner loop runs from j = 1 to j = 4. Print 4 stars. Move to next line.
Step 5: Outer loop ends (i = 5 > n = 4). Final output:
*
* *
* * *
* * * *
Step 6: Total stars printed: 1 + 2 + 3 + 4 = 10 = n(n+1)/2. Total operations scale as O(n²).
Right Half Pyramid — Building Row by Row — Watch how the outer loop selects each row and the inner loop fills in the stars, with each row having one more star than the previous row.
Algorithm
Right Half Pyramid:
- For each row
ifrom 1 ton:
a. For each columnjfrom 1 toi:- Print
*followed by a space
b. Print a newline character to move to the next row
- Print
The key relationship: inner loop upper bound = outer loop variable. This makes each row progressively longer.
Code
#include <iostream>
using namespace std;
void rightHalfPyramid(int n) {
// Outer loop: controls which row we are on
for (int i = 1; i <= n; i++) {
// Inner loop: prints i stars for row i
for (int j = 1; j <= i; j++) {
cout << "* ";
}
// Move to the next line after printing all stars in this row
cout << endl;
}
}
int main() {
int n = 5;
rightHalfPyramid(n);
return 0;
}def right_half_pyramid(n):
# Outer loop: controls which row we are on
for i in range(1, n + 1):
# Inner loop: prints i stars for row i
for j in range(1, i + 1):
print("*", end=" ")
# Move to the next line after printing all stars in this row
print()
n = 5
right_half_pyramid(n)class Solution {
public static void rightHalfPyramid(int n) {
// Outer loop: controls which row we are on
for (int i = 1; i <= n; i++) {
// Inner loop: prints i stars for row i
for (int j = 1; j <= i; j++) {
System.out.print("* ");
}
// Move to the next line after printing all stars in this row
System.out.println();
}
}
public static void main(String[] args) {
int n = 5;
rightHalfPyramid(n);
}
}Complexity Analysis
Time Complexity: O(n²)
The inner loop runs i times for each value of i from 1 to n. Total print operations = 1 + 2 + 3 + ... + n = n(n+1)/2. This is an arithmetic series that simplifies to O(n²). For n = 100, we perform about 5,050 print operations.
Space Complexity: O(1)
We only use two loop variables (i and j) and no additional data structures. The output itself goes directly to the console and does not count toward space complexity.
Why This Approach Is Not Efficient
The Right Half Pyramid approach is perfectly correct and efficient for printing that specific pattern — the O(n²) time is inherent since you must print that many characters.
However, it only handles one pattern. To print an Inverted Pyramid, you would need a different inner loop bound. To print a Full Pyramid, you would need to add leading spaces. Each new pattern requires rewriting the loop logic from scratch.
The limitation is not about time complexity (O(n²) is unavoidable for patterns with ~n² characters), but about understanding and flexibility. A beginner writing each pattern independently may not see the common structure:
- Every pattern uses the same outer loop (row 1 to n)
- Only the inner loop conditions change per pattern
- Leading spaces are just another inner loop
The better approach is to understand the general formula that maps any row number to: (1) how many spaces to print, and (2) how many stars to print. Once you have this formula, you can generate any pattern by plugging in different formulas.
Better Approach - Inverted Pyramid (Reversing the Inner Loop)
Intuition
What if instead of building a staircase going up, we want one going down? The Inverted Right Half Pyramid starts with n stars in the first row and decreases by one star each row.
The trick is simple: instead of the inner loop running from 1 to i, it runs from 1 to n - i + 1. When i = 1 (first row), inner loop goes to n (all stars). When i = n (last row), inner loop goes to 1 (one star).
Think of it like eating a chocolate bar one row at a time from the top. You start with a full bar (n pieces), break off one piece each row, and each subsequent row has one fewer piece than the last.
This teaches a crucial nested loop skill: the inner loop bound is a formula involving the outer loop variable, and by choosing different formulas, you control the shape of the output.
Step-by-Step Explanation
Let's trace the Inverted Right Half Pyramid with n = 4:
Step 1: i = 1. Inner loop: j from 1 to (4-1+1) = 4. Print 4 stars.
Output: * * * *
Step 2: i = 2. Inner loop: j from 1 to (4-2+1) = 3. Print 3 stars.
Output:
* * * *
* * *
Step 3: i = 3. Inner loop: j from 1 to (4-3+1) = 2. Print 2 stars.
Output:
* * * *
* * *
* *
Step 4: i = 4. Inner loop: j from 1 to (4-4+1) = 1. Print 1 star.
Step 5: Final output:
* * * *
* * *
* *
*
Step 6: Total stars: 4 + 3 + 2 + 1 = 10 = n(n+1)/2 — same total as the right half pyramid, just in reverse order.
Inverted Right Half Pyramid — Shrinking Row by Row — Watch how the inner loop bound decreases with each row, producing a triangle that narrows from top to bottom — the mirror image of the right half pyramid.
Algorithm
Inverted Right Half Pyramid:
- For each row
ifrom 1 ton:
a. Calculate the number of stars for this row:stars = n - i + 1
b. For each columnjfrom 1 tostars:- Print
*followed by a space
c. Print a newline character
- Print
The only change from the right half pyramid: the inner loop bound is n - i + 1 instead of i.
Code
#include <iostream>
using namespace std;
void invertedRightHalfPyramid(int n) {
for (int i = 1; i <= n; i++) {
// Key change: inner loop goes to (n - i + 1)
// Row 1: n stars, Row 2: n-1 stars, ..., Row n: 1 star
for (int j = 1; j <= n - i + 1; j++) {
cout << "* ";
}
cout << endl;
}
}
int main() {
int n = 5;
invertedRightHalfPyramid(n);
return 0;
}def inverted_right_half_pyramid(n):
for i in range(1, n + 1):
# Key change: inner loop goes to (n - i + 1)
# Row 1: n stars, Row 2: n-1 stars, ..., Row n: 1 star
for j in range(1, n - i + 2):
print("*", end=" ")
print()
n = 5
inverted_right_half_pyramid(n)class Solution {
public static void invertedRightHalfPyramid(int n) {
for (int i = 1; i <= n; i++) {
// Key change: inner loop goes to (n - i + 1)
// Row 1: n stars, Row 2: n-1 stars, ..., Row n: 1 star
for (int j = 1; j <= n - i + 1; j++) {
System.out.print("* ");
}
System.out.println();
}
}
public static void main(String[] args) {
int n = 5;
invertedRightHalfPyramid(n);
}
}Complexity Analysis
Time Complexity: O(n²)
The inner loop runs n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 times total. This is the same arithmetic series as the right half pyramid, just summed in reverse order. The result is still O(n²).
Space Complexity: O(1)
Only two loop variables are used. No extra data structures are needed.
Why This Approach Is Not Efficient
Both the right half and inverted right half pyramids are left-aligned — all stars start from the left edge. They cannot produce centered patterns like a full pyramid (equilateral triangle shape) because they lack leading spaces.
To center a pyramid, each row needs blank space before the stars to push them rightward. Row 1 needs the most spaces (n-1), and the last row needs zero spaces. This requires a second inner loop before the star-printing loop — one to print spaces and one to print stars.
The insight: a full pyramid is not fundamentally harder than a half pyramid. It just requires understanding that each row has two components: leading spaces and stars. Both are controlled by formulas involving the row number i. This leads us to the optimal approach: the general formula method.
Optimal Approach - General Formula Method (Full Pyramid)
Intuition
The full pyramid is the most elegant nested loop pattern because it combines two different inner loops working together:
- Space loop: Prints
n - ispaces to push the stars toward the center - Star loop: Prints
2*i - 1stars to form the widening triangle
Imagine building a real pyramid with blocks. To make it look like a pyramid (not a staircase), you need to center each layer. The bottom layer is widest, and each layer above is narrower and shifted inward. The "shift" is the leading spaces.
For row i (1-indexed):
- Spaces before stars:
n - i(row 1 gets n-1 spaces, last row gets 0) - Stars to print:
2*i - 1(row 1 gets 1 star, row 2 gets 3, row 3 gets 5, ..., row n gets 2n-1)
The odd number sequence (1, 3, 5, 7, ...) for stars is what creates the symmetric diamond-like widening. Each row adds 2 more stars than the previous (one on each side), creating perfect bilateral symmetry.
This formula-based approach generalizes: once you understand that any pattern is just (spaces formula, stars formula), you can produce any pattern by deriving the right formulas.
Step-by-Step Explanation
Let's build a Full Pyramid with n = 4, tracking spaces and stars per row:
Step 1: i = 1. Spaces = 4 - 1 = 3. Stars = 2(1) - 1 = 1.
Print: ___* (3 spaces, 1 star)
Step 2: i = 2. Spaces = 4 - 2 = 2. Stars = 2(2) - 1 = 3.
Print: __* * * (2 spaces, 3 stars)
Step 3: i = 3. Spaces = 4 - 3 = 1. Stars = 2(3) - 1 = 5.
Print: _* * * * * (1 space, 5 stars)
Step 4: i = 4. Spaces = 4 - 4 = 0. Stars = 2(4) - 1 = 7.
Print: * * * * * * * (0 spaces, 7 stars)
Step 5: Verify the pattern forms a centered pyramid:
*
* * *
* * * * *
* * * * * * *
Step 6: Total operations: For each row i, we do (n-i) space prints + (2i-1) star prints = n + i - 1 operations. Summing over all rows: Σ(n + i - 1) from i=1 to n = n² + n(n+1)/2 - n = O(n²).
Step 7: The two formulas — spaces = n - i and stars = 2*i - 1 — completely define the full pyramid. Any pattern can be decomposed into similar formulas.
Step 8: Verify symmetry: row 1 has 3+1+3 = 7 characters wide (with trailing spaces). Row 4 has 0+7+0 = 7 characters. All rows have the same total width: spaces + stars + spaces = (n-i) + (2i-1) + (n-i) = 2n - 1.
Full Pyramid — Spaces and Stars Working Together — Watch how the space loop and star loop cooperate: as spaces decrease by one each row, stars increase by two, creating perfect centering and the iconic pyramid shape.
Algorithm
Full Pyramid:
- For each row
ifrom 1 ton:
a. Space Loop: Forjfrom 1 ton - i:- Print a space character
b. Star Loop: Forkfrom 1 to2*i - 1: - Print
*followed by a space
c. Print a newline character
- Print a space character
General Pattern Formula Framework:
Any pattern can be produced by defining two functions for each row i:
leading_spaces(i, n)— how many spaces before the characterscharacters(i, n)— how many characters (stars/numbers) to print
| Pattern | Spaces Formula | Stars Formula |
|---|---|---|
| Right Half Pyramid | 0 | i |
| Inverted Right Half Pyramid | 0 | n - i + 1 |
| Full Pyramid | n - i | 2*i - 1 |
| Inverted Full Pyramid | i - 1 | 2*(n-i+1) - 1 |
| Diamond | min(n-i, i-1)* | 2min(i, 2n-i) - 1 |
*Diamond uses a combined formula for the upper and lower halves.
Code
#include <iostream>
using namespace std;
void fullPyramid(int n) {
for (int i = 1; i <= n; i++) {
// Space Loop: print (n - i) leading spaces for centering
for (int j = 1; j <= n - i; j++) {
cout << " "; // two spaces to match star width
}
// Star Loop: print (2*i - 1) stars
for (int k = 1; k <= 2 * i - 1; k++) {
cout << "* ";
}
cout << endl;
}
}
// Bonus: Inverted Full Pyramid
void invertedFullPyramid(int n) {
for (int i = 1; i <= n; i++) {
// Space Loop: (i - 1) leading spaces
for (int j = 1; j < i; j++) {
cout << " ";
}
// Star Loop: (2*(n-i+1) - 1) stars
for (int k = 1; k <= 2 * (n - i + 1) - 1; k++) {
cout << "* ";
}
cout << endl;
}
}
// Bonus: Diamond (combining full + inverted)
void diamond(int n) {
// Upper half (full pyramid)
fullPyramid(n);
// Lower half (inverted pyramid, skip the middle row)
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
cout << " ";
}
for (int k = 1; k <= 2 * (n - i + 1) - 1; k++) {
cout << "* ";
}
cout << endl;
}
}
int main() {
int n = 5;
cout << "--- Full Pyramid ---" << endl;
fullPyramid(n);
cout << "\n--- Inverted Full Pyramid ---" << endl;
invertedFullPyramid(n);
cout << "\n--- Diamond ---" << endl;
diamond(n);
return 0;
}def full_pyramid(n):
for i in range(1, n + 1):
# Space Loop: print (n - i) leading spaces for centering
for j in range(n - i):
print(" ", end=" ")
# Star Loop: print (2*i - 1) stars
for k in range(2 * i - 1):
print("*", end=" ")
print()
# Bonus: Inverted Full Pyramid
def inverted_full_pyramid(n):
for i in range(1, n + 1):
# Space Loop: (i - 1) leading spaces
for j in range(i - 1):
print(" ", end=" ")
# Star Loop: (2*(n-i+1) - 1) stars
for k in range(2 * (n - i + 1) - 1):
print("*", end=" ")
print()
# Bonus: Diamond (combining full + inverted)
def diamond(n):
# Upper half (full pyramid)
full_pyramid(n)
# Lower half (inverted, skip middle row)
for i in range(2, n + 1):
for j in range(i - 1):
print(" ", end=" ")
for k in range(2 * (n - i + 1) - 1):
print("*", end=" ")
print()
n = 5
print("--- Full Pyramid ---")
full_pyramid(n)
print("\n--- Inverted Full Pyramid ---")
inverted_full_pyramid(n)
print("\n--- Diamond ---")
diamond(n)class Solution {
public static void fullPyramid(int n) {
for (int i = 1; i <= n; i++) {
// Space Loop: print (n - i) leading spaces for centering
for (int j = 1; j <= n - i; j++) {
System.out.print(" "); // two spaces to match star width
}
// Star Loop: print (2*i - 1) stars
for (int k = 1; k <= 2 * i - 1; k++) {
System.out.print("* ");
}
System.out.println();
}
}
// Bonus: Inverted Full Pyramid
public static void invertedFullPyramid(int n) {
for (int i = 1; i <= n; i++) {
// Space Loop: (i - 1) leading spaces
for (int j = 1; j < i; j++) {
System.out.print(" ");
}
// Star Loop: (2*(n-i+1) - 1) stars
for (int k = 1; k <= 2 * (n - i + 1) - 1; k++) {
System.out.print("* ");
}
System.out.println();
}
}
// Bonus: Diamond (combining full + inverted)
public static void diamond(int n) {
fullPyramid(n);
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
System.out.print(" ");
}
for (int k = 1; k <= 2 * (n - i + 1) - 1; k++) {
System.out.print("* ");
}
System.out.println();
}
}
public static void main(String[] args) {
int n = 5;
System.out.println("--- Full Pyramid ---");
fullPyramid(n);
System.out.println("\n--- Inverted Full Pyramid ---");
invertedFullPyramid(n);
System.out.println("\n--- Diamond ---");
diamond(n);
}
}Complexity Analysis
Time Complexity: O(n²)
For each row i, we perform (n - i) space prints and (2*i - 1) star prints, totaling n + i - 1 operations per row.
Summing over all rows: Σ(n + i - 1) from i=1 to n = n·n + n(n+1)/2 - n = n² + n²/2 + n/2 - n ≈ 3n²/2
This simplifies to O(n²). The quadratic complexity is inherent — you must print approximately n² characters to form the pyramid.
Alternatively, total stars = 1 + 3 + 5 + ... + (2n-1) = n² (sum of first n odd numbers). Total spaces ≈ n²/2. Total characters ≈ 3n²/2 = O(n²).
Space Complexity: O(1)
Only loop variables are used. No arrays or data structures needed. Each character is printed directly to the console.
Key Takeaway: The time complexity O(n²) is the same for all three patterns (right half, inverted, full pyramid) because they all print approximately the same number of characters. The difference between patterns is purely in the formulas controlling the inner loops, not in the algorithmic complexity. Understanding these formulas is the real skill — it is what allows you to create any pattern from the same basic nested loop template.
Visualization
