Time Limit Exception

Question

I don't know why this code is giving me time limit exception for N*log(N) time limit. Please anyone can tell.I have used only two linear time for loops and one predefined java method for sorting.

class Solution{

 public String minimum_Number(String s){

   int arr[] = new int[s.length()];
   for(int i=0;i<s.length();i++){
       arr[i] = Integer.parseInt(""+s.charAt(i));
      
   }
   Arrays.sort(arr);
   int i=0;
   while(i<arr.length && arr[i]==0){
       i++;
   }
   if(arr[0]==0 && i<arr.length){
       //swap 0 with first non zero element
       arr[0]=arr[i];
       arr[i]=0;
   }
   String ans="";
   for(int j=0;j<arr.length;j++){
       
       ans+=arr[j];
   }
   return ans;
   
}

}

What do you think how fast `Arrays.sort(arr);` is? – Progman May 26 '21 at 18:29 — Progman, May 26 '21 at 18:29
what is the ecpected output and input, can you show here – Siddhant May 26 '21 at 18:39 — Siddhant, May 26 '21 at 18:39

score 1 · Answer 1 · answered May 26 '21 at 18:35

Please try thi, This is working fine for me.

import java.util.*;
public class Solution{

 public String minimum_Number(String s){

   int arr[] = new int[s.length()];
   for(int i=0;i<s.length();i++){
       arr[i] = Integer.parseInt(""+s.charAt(i));
      
   }
   Arrays.sort(arr);
   int i=0;
   while(i<arr.length && arr[i]==0){
       i++;
   }
   if(arr[0]==0 && i<arr.length){
       //swap 0 with first non zero element
       arr[0]=arr[i];
       arr[i]=0;
   }
   String ans="";
   for(int j=0;j<arr.length;j++){
       
       ans+=arr[j];
   }
   return ans;
   
}
public static void main(String args[])
{
Solution sn = new Solution();
String ans = sn.minimum_Number("532974");
System.out.println(ans);
}
}

score 0 · Answer 2 · answered May 26 '21 at 19:05

String operations in Java can be expensive. In general the time complexity of s1 + s2 is O(m + n) where m and n are the string lengths of s1 and s2 respectively. So it is better to use StringBuilder in Java. See this

So to improve runtime to certain limit you can do (though kindly share the exact constraints of the problem to get more specific solution):

public String minimum_Number(String s){

   int arr[] = new int[s.length()];
   for(int i=0;i<s.length();i++){
       arr[i] = Character.getNumericValue(s.charAt(i));
      
   }
   Arrays.sort(arr);
   int i=0;
   while(i<arr.length && arr[i]==0){
       i++;
   }
   if(arr[0]==0 && i<arr.length){
       //swap 0 with first non zero element
       arr[0]=arr[i];
       arr[i]=0;
   }
   StringBuilder ans= new StringBuilder();
   for(int j=0;j<arr.length;j++){
       
       ans.append(arr[j]);
   }
   return ans.toString();

}

Time Limit Exception

2 Answers2