Algocademy Logo

Course Outline

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


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 1 and n 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 now the 'special' columns. How will you print that line?

We'll use a for loop to iterate through every column index from 1 to n.
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 -.

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: