1
\$\begingroup\$

I am trying to print the Z pattern, but the time complexity is coming to \$O(n^2)\$. Is there any way to reduce the time complexity?

package matrix;

public class ZPattern 
{
    public static void main(String[] args) {
        String a[][] = { {"1","2","3","4","5"},
                {"a","b","c","d","e"},
                {"6","7","8","9", "f"},
                {"g","h","i","j","k"},
                {"m","n","o","p","q"}
            };
        for(int i=0;i<a.length;i++)
        {
            for(int j=0;j<a.length;j++)
            {
                if(i==0||i==a.length-1)
                {
                    System.out.print(a[i][j]);
                }
                else if(i+j==a.length-1)
                {
                    System.out.print(a[i][j-1]);
                }
                else
                {
                    System.out.print(" ");
                }
            }
            System.out.println("");
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ for(int j=0;j<a.length;j++) looks wrong. Shouldn't that be for(int j=0;j<a[i].length;j++)? \$\endgroup\$ – πάντα ῥεῖ Apr 15 '17 at 7:40
  • \$\begingroup\$ @πάνταῥεῖ Because printing a Z only makes sense for square grids? So in this specific case it doesn't matter much. \$\endgroup\$ – Imus Apr 15 '17 at 11:14
1
\$\begingroup\$

Bug?

The output from your version:

12345
   c 
  7  
 g   
mnopq

But the output should be

12345
   d
  8
 h
mnopq

It's unclear why you chose this.

                    System.out.print(a[i][j-1]);

This could be

                    System.out.print(a[i][j]);

Then it prints the output correctly.

Avoid unnecessary comparisons in loops

You iterate over each element in the entire square and print different things based on an if/else structure. But you don't actually have to do that. Consider

    public static void drawZ(String[][] matrix) {
        System.out.println(String.join("", matrix[0]));

        int n = matrix.length - 1;
        for (int i = 1; i < n; i++)
        {
            int m = matrix.length - i - 1;
            for (int j = m; j > 0; j--)
            {
                System.out.print(" ");
            }

            System.out.println(matrix[i][m]);
        }

        System.out.println(String.join("", matrix[n]));
    }

This is in a separate method, which makes it easy to reuse.

This prints the first and last line separately. So we don't need that part of the if.

This prints the spaces separately from the line of the Z. So we don't need those parts of the if either.

Rather than calculating i + j - a.length - 1 on every iteration, this code just counts down from m, which it calculates once per row.

This calls a Java 8 built-in method to join the characters in a row rather than rolling our own for loop.

This prints the equivalent part of the matrix. If that's not what you want, you can replace [m] with [m - 1]. That would give the original behavior.

\$\endgroup\$
0
\$\begingroup\$

You're trying to print an N x N matrix so the inherit complexity is O(n²). No way to go around this.

What you can reduce is the "spaces" you print. More specifically the Os in this pattern:

ZZZZZ
___ZO
__ZOO
_ZOOO
ZZZZZ

Even if you don't print those, the Z pattern stays the same. This then results in code like this:

public static void main(String[] args) {
    int[][] grid = new int[][]{{1,1,1,1,1},{0,0,0,1,0},{0,0,1,0,0},{0,1,0,0,0},{1,1,1,1,1}};
    for(int i = 0; i < grid[0].length; i++){
        System.out.print(grid[0][i]);
    }
    System.out.println();
    for(int i = 1; i < grid.length - 1; i++){
        for(int j = 0; j < grid.length-i; j++){
            if(j==grid.length-i-1){
                System.out.print(grid[i][j]);
            } else {
                System.out.print(" ");
            }
        }
        System.out.println();
    }
    for(int i = 0; i < grid[grid.length-1].length; i++){
        System.out.print(grid[grid.length-1][i]);
    }
    System.out.println();
}

But I really don't think it's worth it. Don't forget that you're just printing a big Z pattern here. Do those couple of milliseconds actually make a difference? I couldn't tell the difference between your near instant printing code and mine after the change ...

So go for readability first, minor optimisations second.
If this was a method that would be executed millions of times it would be a different story.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.