> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/01-27-2022-937.md).

# 01/27/2022 937

Implement java Comparator interface and override its compare method.  Divide the comparasion into three cases: when they are all letter logs, one of them is digit-logs, and both of them are digit-logs. 

Time O(M\*NlogN), M is maximum length of a single log, N is the numbers of logs in the array. 

Space O(M \* N)

{% embed url="<https://leetcode.com/problems/reorder-data-in-log-files/solution/734982>" %}

Reason:\
Because when we use `Comparator` for `Arrays.sort()`, the implementation is **mergeSort**, you can check official document for [Arrays.sort(T\[\] a, Comparator\<? super T> c)](https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort\(T%5B%5D,%20java.util.Comparator\)). And **merge sort will keep the order if 2 elements are the same!!!**

However, for `Array.sort()` methods like `Array.sort(int[]/double[]/char[])` without using `Comparator`, the implementation is **quickSort**, it will not keep the original order. For example, check the Java doc for sorting `int[]` array [public static void sort(int\[\] a)](https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort\(int%5B%5D\)).\
However, thanks for @GregorGk mentioning, these are all primitive types array, no need to consider their order.

class Solution {&#x20;

public String\[] reorderLogFiles(String\[] logs) {

```
    if(logs == null || logs.length == 0) return null;
    Arrays.sort(logs, new MyComparator());
    
    return logs;              
}

public class MyComparator implements Comparator<String>{
    
    @Override
    public int compare(String log1, String log2){
        String[] split1 = log1.split(" ", 2);
        String[] split2 = log2.split(" ", 2);
        
        Boolean isDigit1 = Character.isDigit(split1[1].charAt(0));
        Boolean isDigit2 = Character.isDigit(split2[1].charAt(0));
        
        //case1 both logs are letter-logs
        if(!isDigit1 && !isDigit2){
            int cmp = split1[1].compareTo(split2[1]);
            if(cmp != 0) return cmp;
            return split1[0].compareTo(split2[0]);
        }
        
        //case2 one of logs is digit-log
        if(!isDigit1 && isDigit2)
            return -1;// no need to swap: the letter-log comes before digit-logs
        else if(isDigit1 && !isDigit2)
            return 1;
        else // both logs are digit-log, keep the order
            return 0;
        
    }
    
}
```

}

class Solution {&#x20;

public String\[] reorderLogFiles(String\[] logs) {

```
    if(logs == null || logs.length == 0) return null;
    
    Comparator<String> myComparator = new Comparator<>(){
        @Override
        public int compare(String log1, String log2){
            String[] split1 = log1.split(" ", 2);
            String[] split2 = log2.split(" ", 2);
        
            Boolean isDigit1 = Character.isDigit(split1[1].charAt(0));
            Boolean isDigit2 = Character.isDigit(split2[1].charAt(0));
        
            //case1 both logs are letter-logs
            if(!isDigit1 && !isDigit2){
                int cmp = split1[1].compareTo(split2[1]);
                if(cmp != 0) return cmp;
                return split1[0].compareTo(split2[0]);
            }
        
            //case2 one of logs is digit-log
            if(!isDigit1 && isDigit2)
                return -1;// no need to swap: the letter-log comes before digit-logs
            else if(isDigit1 && !isDigit2)
                return 1;
            else // both logs are digit-log, keep the order
                return 0;
        }
            
    };
    
    Arrays.sort(logs, myComparator);
    return logs;
       
    
}
```

}

```
class Solution {
    public String[] reorderLogFiles(String[] logs) {
        if(logs == null || logs.length == 0) return null;
        
        Arrays.sort(logs, new MyComparator());
        return logs;        
    }
    
    public class MyComparator implements Comparator<String>{
        @Override
        public int compare(String log1, String log2){
            int idx1 = log1.indexOf(" ") + 1;
            int idx2 = log2.indexOf(" ") + 1;
            if(log1.charAt(idx1) >= 'a' && log1.charAt(idx1) <= 'z' && 
               log2.charAt(idx2) >= 'a' && log2.charAt(idx2) <= 'z'){
                String tail1 = log1.substring(idx1);
                String tail2 = log2.substring(idx2);
                int temp = tail1.compareTo(tail2);
                if(temp != 0) return temp;
                else return log1.compareTo(log2);
            }else if(log1.charAt(idx1) >= 'a' && log1.charAt(idx1) <= 'z') return -1;
            else if(log2.charAt(idx2) >= 'a' && log2.charAt(idx2) <= 'z') return 1;
            else return 0; // if both digit-logs, then keep the order
        }
    }
}
```

Let NN be the number of logs in the list and MM be the maximum length of a single log.

* Time Complexity: \mathcal{O}(M \cdot N \cdot \log N)O(M⋅N⋅logN)
  * First of all, the time complexity of the `Arrays.sort()` is \mathcal{O}(N \cdot \log N)O(N⋅logN), as stated in the [API specification](https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#sort-byte:A-), which is to say that the `compare()` function would be invoked \mathcal{O}(N \cdot \log N)O(N⋅logN) times.
  * For each invocation of the `compare()` function, it could take up to \mathcal{O}(M)O(M) time, since we compare the contents of the logs.
  * Therefore, the overall time complexity of the algorithm is \mathcal{O}(M \cdot N \cdot \log N)O(M⋅N⋅logN).
* Space Complexity: \mathcal{O}(M \cdot \log N)O(M⋅logN)

  * For each invocation of the `compare()` function, we would need up to \mathcal{O}(M)O(M) space to hold the parsed logs.
  * In addition, since the implementation of `Arrays.sort()` is based on quicksort algorithm whose space complexity is \mathcal{O}(\log n)O(logn), assuming that the space for each element is \mathcal{O}(1)O(1)). Since each log could be of \mathcal{O}(M)O(M) space, we would need \mathcal{O}(M \cdot \log N)O(M⋅logN) space to hold the intermediate values for sorting.
  * In total, the overall space complexity of the algorithm is \mathcal{O}(M + M \cdot \log N) = \mathcal{O}(M \cdot \log N)O(M+M⋅logN)=O(M⋅logN).

```
  public String[] reorderLogFiles(String[] logs) {
    Arrays.sort(
        logs,
        (l1, l2) -> {
          char e1 = l1.charAt(l1.length() - 1);
          char e2 = l2.charAt(l2.length() - 1);
          boolean isD1 = e1 <= '9' && '0' <= e1;
          boolean isD2 = e2 <= '9' && '0' <= e2;
          if (!isD1 && !isD2) {
            int i1 = l1.indexOf(" "), i2 = l2.indexOf(" ");
            String ID1 = l1.substring(0, i1), ID2 = l2.substring(0, i2);
            if (l1.substring(i1).equals(l2.substring(i2))) return ID1.compareTo(ID2);
            return l1.substring(i1).compareTo(l2.substring(i2));
          } else if (isD1 && isD2) {
            return 0;
          } else if (isD1) return 1; // note here: digit > string
          else return -1;
        });
    return logs;
  }
```