title: K-th Smallest in Lexicographical Order
body: <p>Given integers n and k, find the lexicographically k-th smallest integer in the range from 1 to n.</p>
  
  <p>Note: 1 ≤ k ≤ n ≤ 109.</p>
  
  <p>Example:</p>
  
  <p>Input:
  n: 13   k: 2</p>
  
  <p>Output:
  10</p>
  
  <p>Explanation:
  The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.</p>
  
  <p>I have written a code which works fine but when I give very high input it takes a lot of time to execute and hence time out. Could some one please suggest me how i can make it more efficient.</p>
  
  <p>Thanks!!</p>
  
  <pre><code>public class Solution {
  
  class MyComp implements Comparator&lt;Integer&gt;{
      @Override
      public int compare(Integer n1, Integer n2) {
          return  String.valueOf(n1).compareTo(String.valueOf(n2));
      }
  }
  
  public int findKthNumber(int n, int k) {
      if(n==0 || k ==0 || k &gt; n) return 0;
      int[] tracker = new int[9];
      Arrays.fill(tracker,0);
  
  
      Map&lt;Integer,TreeSet&lt;Integer&gt;&gt; map = new HashMap&lt;Integer,TreeSet&lt;Integer&gt;&gt;();
      for(int i =1;i&lt;=n;i++){
          String prefix = String.valueOf(i);
          int currIndex = Integer.parseInt(prefix.substring(0,1));
          //Update count
          tracker[currIndex-1] = tracker[currIndex-1] + 1;
          if(map.containsKey(currIndex)){
               TreeSet&lt;Integer&gt; set = map.get(currIndex);
               set.add(i);
               map.put(currIndex,set);
          }else{
              TreeSet&lt;Integer&gt; set = new TreeSet&lt;Integer&gt;(new MyComp());
              set.add(i);
              map.put(currIndex,set);
          }
  
      }
  
      // counter to check the if we reach near by K
      int count =1;
      for(int i=0;i&lt;9 ;i++ ){
          int lookUp = i+1;
          int val = tracker[i];
          if( count + map.get(lookUp).size() &gt; k){
              for(int res : map.get(lookUp)){
                  if(count == k) return res;
                  count++;
              }
          }
          count = count + map.get(lookUp).size();
      }
  
      return 0;
  
  }
  
  }
  </code></pre>