Print Rhombus in Java with Time Complexity O(n)

Given an odd positive integer n print a rhombus of stars as in the example below

Example:

Input: n = 5
Output:
  *  
 *** 
*****
 *** 
  *  

Explanation:
There are n = 5 lines. Each line contains exactly n = 5 characters.
1st line contains two spaces, one '*' and two spaces.
2nd line contains one space, three '*' and one space.
3rd line contains five stars.
4th line contains one space, three '*' and one space.
5th line contains two spaces, one '*' and two spaces.

Note: Be careful to add the necessary spaces at the end of every line!

Understanding the Problem

The core challenge of this problem is to print a rhombus shape using stars ('*') and spaces (' '). The rhombus must be symmetrical and centered, with the number of lines and characters per line equal to the given odd integer n. This problem is significant in understanding how to manipulate strings and loops to create specific patterns, which is a common task in programming.

Approach

To solve this problem, we need to understand the pattern of spaces and stars for each line:

The middle line (n/2 + 1) has all stars and no spaces.
Lines above the middle line have increasing stars and decreasing spaces as we move towards the middle.
Lines below the middle line mirror the lines above it.

We can start by writing a naive solution that uses nested loops to print each line. However, this approach can be optimized by calculating the number of spaces and stars for each line directly.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Loop through each line from 1 to n.
Calculate the number of spaces and stars for the current line.
Print the spaces followed by the stars.

Code Implementation

public class RhombusPrinter {
    public static void printRhombus(int n) {
        // Loop through each line
        for (int i = 0; i < n; i++) {
            // Calculate the number of stars for the current line
            int stars = n - 2 * Math.abs(n / 2 - i);
            // Calculate the number of spaces for the current line
            int spaces = (n - stars) / 2;
            
            // Print spaces
            for (int j = 0; j < spaces; j++) {
                System.out.print(" ");
            }
            // Print stars
            for (int j = 0; j < stars; j++) {
                System.out.print("*");
            }
            // Print a new line
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int n = 5; // Example input
        printRhombus(n);
    }
}

Complexity Analysis

The time complexity of this solution is O(n) because we loop through each line once and perform a constant amount of work for each line. The space complexity is O(1) as we are using a fixed amount of extra space.

Edge Cases

Potential edge cases include:

Minimum odd value of n (e.g., n = 1): The output should be a single '*'.
Large values of n: Ensure the program handles large inputs efficiently.

To test these edge cases, we can run the function with different values of n and verify the output manually or using automated tests.

Testing

To test the solution comprehensively, we can use a variety of test cases:

Simple cases: n = 1, n = 3, n = 5
Complex cases: n = 7, n = 9, n = 11
Edge cases: n = 1, very large n

We can use a testing framework like JUnit to automate these tests.

Thinking and Problem-Solving Tips

When approaching such problems, it is helpful to:

Break down the problem into smaller parts.
Identify patterns and relationships in the problem.
Write pseudocode before implementing the actual code.
Test the solution with different inputs to ensure correctness.

Conclusion

In this blog post, we discussed how to print a rhombus of stars given an odd positive integer n. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems helps improve problem-solving skills and string manipulation techniques in programming.

Additional Resources

For further reading and practice problems related to this topic, consider the following resources: