Problem Statement: JNEXT

DevG was challanged to find the just next greater number which can be formed using digits of a given number. Now DevG needs your help to find that just next greater number and win the challenge.


The first line have t number of test cases (1 <= t <= 100). In next 2*t lines for each test case first there is number n (1 <= n <= 1000000) which denotes the number of digits in given number and next line contains n digits of given number separated by space.


Print the just next greater number if possible else print -1 in one line for each test case.

Note : There will be no test case which contains zero in starting digits of any given number.



1 5 4 8 3
1 4 7 4 5 8 4 1 2 6



My Solution is

public static void main(String[] argh) throws Exception{
        Reader br = new Reader();
        int t= br.nextInt();

        for(int aa=0; aa<t; aa++){
            int n= br.nextInt();
            int[] arr= new int[n];
            int breakPoint= -1;
            int mI= -1;

            for(int qq=0; qq<n; qq++){
                arr[qq]= br.nextInt();
                if(qq !=0 && arr[qq] > arr[qq-1]){
                    breakPoint= qq-1;
                if(breakPoint != -1){
                    if(arr[breakPoint] < arr[qq]){
                        mI= qq;
            if(breakPoint == -1 || n == 1){

            // swap
            arr[breakPoint]= arr[breakPoint] + arr[mI];
            arr[mI]= arr[breakPoint] - arr[mI];
            arr[breakPoint]= arr[breakPoint] - arr[mI];

            for(int ii=0; ii<breakPoint; ii++){
            for(int ii=n-1; ii>=breakPoint; ii--){

My solution is having O(N) time complexity but still I am getting TLE. Can anyone point out issue?

  • \$\begingroup\$ "My solution is having O(N) time complexity" Are you absolutely sure about that? Please include a link to the original challenge as well. \$\endgroup\$
    – Mast
    Sep 22, 2018 at 7:13
  • \$\begingroup\$ It looks linear time complexity to me. If I am wrong please correct me and mention the improvement needed. \$\endgroup\$
    – Ladoo
    Sep 22, 2018 at 7:20
  • 2
    \$\begingroup\$ I have added the link to question \$\endgroup\$
    – Ladoo
    Sep 22, 2018 at 7:53
  • \$\begingroup\$ I have rolled back your latest edit. Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$
    – Heslacher
    Sep 25, 2018 at 15:03

2 Answers 2

int[] arr

You can probably create it only once, with maximum possible size, outside for for loop.


You need to use StringBuilder and output only whole string in single println call. Multiple System.out.print calls are what makes it slow.

  • \$\begingroup\$ I tried String Builder now but I am still screwed by tle \$\endgroup\$
    – Ladoo
    Sep 25, 2018 at 11:46
  • \$\begingroup\$ I ran you code with StringBuilder ands it was accepted with time "1.56" \$\endgroup\$
    – user158037
    Sep 25, 2018 at 13:45
  • \$\begingroup\$ can you post that code? and time limit is 1.297s. I can see you got the success \$\endgroup\$
    – Ladoo
    Sep 25, 2018 at 13:54
  • \$\begingroup\$ I am having trouble in optimization so trying to learn with some pre written codes. I have updated my post with String builder code \$\endgroup\$
    – Ladoo
    Sep 25, 2018 at 13:56
  • \$\begingroup\$ finally got it correct. But please can you post your answer too? \$\endgroup\$
    – Ladoo
    Sep 25, 2018 at 15:37

It indeed looks like your code is O(n), I atleast can't find a reason for it not to be. Although I would recommend some better variable names and breaking out done functions.

Your code uses Reader which to my knowledge is unbuffered and thus very slow. It is reasonably common for inappropriate IO code in Java programming challenges to cause TLE even for the correct algorithm. Considering you're reading up to one million ints per test case, this could be your suspect.

Try wrapping the Reader in a BufferedReader .

While I believe that the system out stream is buffered, you can also build the output into a StringBuilder to see if that makes a difference.

For reference: https://www.hackerearth.com/practice/notes/inputoutput-in-javascanner-bufferedreader-self-made-fast-io/


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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