package com.fishercoder.solutions;

import java.util.ArrayList;
import java.util.List;

/**
 * 386. Lexicographical Numbers
 *
 * Given an integer n, return 1 - n in lexicographical order.
 *
 * For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
 *
 * Please optimize your algorithm to use less time and space. The input size may be as large as
 * 5,000,000.
 */
public class _386 {
  public static class Solution1 {
    //Radix sort doesn't apply here! Don't confuse yourself!

    //rewrote their solution from Python to Java:https://discuss.leetcode.com/topic/54986/python-memory-limit-exceeded-for-problem-386/17
    public List<Integer> lexicalOrder(int n) {
      List<Integer> result = new ArrayList();
      int i = 1;
      while (true) {
        result.add(i);
        if (i * 10 <= n) {
          i *= 10;
        } else {
          while (i % 10 == 9 || i == n) {
            i /= 10;
          }
          if (i == 0) {
            return result;
          }
          i++;
        }
      }
    }
  }
}

@@ -85,296 +85,8 @@
 t;%0A%0A
-/**%0A * 386. Lexicographical Numbers%0A *%0A * Given an integer n, return 1 - n in lexicographical order.%0A *%0A * For example, given 13, return: %5B1,10,11,12,13,2,3,4,5,6,7,8,9%5D.%0A *%0A * Please optimize your algorithm to use less time and space. The input size may be as large as%0A * 5,000,000.%0A */%0A
 publ
@@ -101,16 +101,18 @@
  _386 %7B%0A
+  
   public
@@ -137,16 +137,20 @@
 tion1 %7B%0A
+    
     //Ra
@@ -203,16 +203,20 @@
 rself!%0A%0A
+    
     //re
@@ -345,16 +345,20 @@
 -386/17%0A
+    
     publ
@@ -392,24 +392,30 @@
 er(int n) %7B%0A
+      
       List%3CI
@@ -448,16 +448,22 @@
 List();%0A
+      
       in
@@ -473,24 +473,30 @@
  = 1;%0A      
+ 
+     
 while (true)
@@ -506,16 +506,24 @@
         
+  
+      
 result.a
@@ -529,16 +529,24 @@
 add(i);%0A
+        
         
@@ -560,24 +560,34 @@
  10 %3C= n) %7B%0A
+          
           i 
@@ -601,16 +601,24 @@
         
+    
+    
 %7D else %7B
@@ -618,16 +618,26 @@
  else %7B%0A
+          
         
@@ -666,24 +666,36 @@
 %7C i == n) %7B%0A
+            
             
@@ -705,34 +705,50 @@
 = 10;%0A          
+  
-%7D%0A
+        %7D%0A      
           if (i 
@@ -737,24 +737,28 @@
             
+    
 if (i == 0) 
@@ -771,16 +771,28 @@
         
+          
+  
 return r
@@ -812,49 +812,89 @@
     
-%7D%0A          i++;%0A        %7D%0A
+          %7D%0A                    i++;%0A                %7D%0A     
       
+ 
 %7D%0A    
+   
+ 
 %7D%0A
+  
   %7D%0A

refactor 386