2
\$\begingroup\$

I am trying to solve a programming problem on a coding platform. When I execute it on my PC, it works perfectly, but when I submit the code on the coding platform, it throws a "Time Limit Exceeded" error. Can someone check my solution and help optimize it?

Given a number N, the program must print the pattern as described below.

Input Format:The first line contains the value of the N which represent the number N. Output Format:The pattern as described below in the Example.

> Input: 4

> Output:
4444444
4333334
4322234
4321234
4322234
4333334   
4444444

My Approach

Print Upper rectangle and then print the lower rectangle.

The problem statement and my code can also be found here.

import java.util.Scanner;

public class Test004_3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        /*  PRINT UPPER PART
            4444444
            4333334
            4322234
            4321234
        */
        for(int i = N; i>(1); i--)
        {
            for(int j = N; j >i; j--)
                System.out.print(j);
            for(int j = 0; j<(i*2)-1; j++)
               System.out.print(i);
            for(int j = i+1; j<=N; j++)
                System.out.print(j);
            System.out.println("");
        }
        /* 
            PRINT LOWER PART
            4322234
            4333334
            4444444
        */
        for(int i = 1; i<=(N); i++)
        {
            for(int j = N; j>i; j--)
                System.out.print(j);
            for(int j = 0; j<(i*2)-1; j++)
                System.out.print(i);
            for(int j = i+1; j <=N; j++)
                System.out.print(j);
            System.out.println("");
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ I don't understand the "Time limit exceeded". The code runs really fast. \$\endgroup\$ – Roland Illig Jul 31 '16 at 20:33
  • \$\begingroup\$ Do you know of a time limit? This takes to 2 ms for input of 4 and 100 ms for input of 100 on my Macbook Pro, which as @RolandIllig said is pretty quick. \$\endgroup\$ – Dando18 Jul 31 '16 at 20:43
  • \$\begingroup\$ Can you provide a link to the programming challenge? It's possible that someone might suggest something specific to that online judge. \$\endgroup\$ – mdfst13 Jul 31 '16 at 21:48
4
\$\begingroup\$

As has been said by @200_success, outputting individual characters at a time to the console is going to be relatively slow. You'd be better off building up the string using a StringBuilder and then writing the whole thing at the end.

Assuming a maximum number of 9, you can predict the size of the required buffer which will prevent the buffer from needing to resize. A safe value would be:

StringBuilder sb = new StringBuilder(N*2*N*2)

This number will need to be bigger if you have to support multiple digit numbers, however the StringBuilder will scale this for you if required.

Instead of calling System.out.print, you then append to the StringBuilder:

sb.append(j);

Adding new lines when required:

sb.append("\n");

And at the end, write out the entire buffer in one go:

System.out.print(sb);

Putting it together

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    StringBuilder sb = new StringBuilder(N*2*N*2);
    for(int i = N; i>(1); i--) //Print upper part
    {
        for(int j = N; j >i; j--)
            sb.append(j);
        for(int j = 0; j<(i*2)-1; j++)
           sb.append(i);
        for(int j = i+1; j<=N; j++)
            sb.append(j);
        sb.append("\n");
    }
    for(int i = 1; i<=(N); i++)// print lower part
    {
        for(int j = N; j>i; j--)
            sb.append(j);
        for(int j = 0; j<(i*2)-1; j++)
            sb.append(i);
        for(int j = i+1; j <=N; j++)
            sb.append(j);
        sb.append("\n");
    }
    System.out.print(sb);
}
\$\endgroup\$
  • \$\begingroup\$ Thanks sir it worked, but i dont understand why System.out.println() is creating problem it taken constant timeO(1) on the other hand StringBuilder class also takes O(1) time to buildup the string. \$\endgroup\$ – Rajat Khandelwal Aug 1 '16 at 5:23
  • \$\begingroup\$ @Rajatk95 because whilst they may be the same number of operations, each operation takes longer. String builder is simply appending a character to a buffer. Print needs to call out to an operating system function to write to video memory, which is more complex and slower. Consider two calls to sleep, one for a second and one for two seconds. They are both constant time, however over of the calls takes twice as long. \$\endgroup\$ – forsvarir Aug 1 '16 at 6:31
3
\$\begingroup\$

The individual System.out.print() calls are probably resulting in too much system call overhead. Try printing an entire line at a time, or even the entire pattern as one very long string.

\$\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.