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'

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:

• Matrix Manipulation in Java
• LeetCode for more coding challenges.
• HackerRank for algorithm tutorials and practice problems.