Start learning free

LESSON 187 OF 410 · NESTED LOOPS

Print X in Java with O(n^2) Time Complexity

Practice O(n2) Read the full explanation

Given a positive integer n print matrix containing an X as in the example below

Example:

Input: n = 5
Output:
x---x
-x-x-
--x--
-x-x-
x---x
Explanation:
Each line contains exactly n = 5 characters and two 'x's.
Each diagonal contains 'x'

Hints:

Notice that on each line there will be exactly two x and the other characters are all -. The only exception is the middle line which will have only one x. How can we use this info?

We can print the matrix line by line. For each line we need to know the two columns where we should print x. How can we know these two columns for every line?

We'll store the columns' indices in two variables firstX and secondX, initially equal to the first and the last column respectively for the first line.
How should these variables change from line to line?

firstX should get incremented and secondX should get decremented.
Now for each line, you know the 'special' columns. How will you print that line?

We'll use a for loop to iterate through every column index of the line.
What should we do inside the loop?

We should use an if - else statement and check if the current index is firstX or secondX and if so, print x. Otherwise, print -.
STEP 1 OF 9
    Ctrl + Enter to check

    JAVA · NESTED LOOPS

    Print X in Java, explained

    Problem Definition

    The task is to print a matrix of size n x n where the diagonals contain the character 'x' and all other positions contain the character '-'.

    Input:

    A single integer n (1 ≤ n ≤ 1000).

    Output:

    A matrix of size n x n with 'x' on the diagonals and '-' elsewhere.

    Example:

    Input: n = 5
Output:
x---x
-x-x-
--x--
-x-x-
x---x

    Understanding the Problem

    The core challenge is to correctly place the 'x' characters on both diagonals of the matrix. This problem is significant in understanding how to manipulate and traverse matrices, which is a common task in computer science.

    Potential pitfalls include incorrectly indexing the matrix or not properly handling the middle row when n is odd.

    Approach

    To solve this problem, we can use a simple nested loop to construct each row of the matrix. For each row, we determine the positions of the 'x' characters and fill the rest with '-'.

    Naive Solution

    A naive solution would involve manually constructing each row, but this is not scalable or efficient. Instead, we can use a systematic approach to determine the positions of 'x' for each row.

    Optimized Solution

    We can use two variables, firstX and secondX, to track the positions of 'x' in each row. Initially, firstX is 0 and secondX is n-1. For each subsequent row, we increment firstX and decrement secondX.

    Algorithm

    1. Initialize firstX to 0 and secondX to n-1.

    2. For each row from 0 to n-1:

    • Initialize an empty string for the row.
    • For each column from 0 to n-1:
      • If the column index is firstX or secondX, append 'x' to the row string.
      • Otherwise, append '-'.
    • Print the row string.
    • Increment firstX and decrement secondX.

    Code Implementation

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

    public static void printXMatrix(int n) {
        // Initialize the positions of 'x' in the first row
        int firstX = 0;
        int secondX = n - 1;

        // Loop through each row
        for (int i = 0; i < n; i++) {
            StringBuilder row = new StringBuilder();

            // Loop through each column in the current row
            for (int j = 0; j < n; j++) {
                if (j == firstX || j == secondX) {
                    row.append('x');
                } else {
                    row.append('-');
                }
            }

            // Print the constructed row
            System.out.println(row.toString());

            // Update the positions of 'x' for the next row
            firstX++;
            secondX--;
        }
    }
}

    Complexity Analysis

    The time complexity of this solution is O(n^2) because we have a nested loop where both the outer and inner loops run n times. The space complexity is O(n) for storing the row string.

    Edge Cases

    Potential edge cases include:

    • n = 1: The output should be a single 'x'.
    • n = 2: The output should be: 
          xx
    xx

    These cases are handled naturally by the algorithm without any special conditions.

    Testing

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

    • Simple cases like n = 1 and n = 2.
    • Odd and even values of n.
    • Large values of n to ensure performance.

    Thinking and Problem-Solving Tips

    When approaching such problems, it's helpful to:

    • Break down the problem into smaller parts.
    • Use systematic approaches to handle repetitive tasks.
    • Think about edge cases and how to handle them.

    Practicing similar problems and studying algorithms can improve problem-solving skills.

    Conclusion

    In this blog post, we discussed how to print a matrix containing an 'X' pattern given a positive integer n. We explored the problem definition, approach, algorithm, and provided a detailed Java implementation. Understanding and solving such problems is crucial for developing strong problem-solving skills in computer science.

    Additional Resources

    For further reading and practice, consider the following resources:

    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free