937. Reorder Data in Log Files

Approach 1: Split into Letters and Digits

class Solution:
    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        digits = []
        letters = []

        for log in logs:
            if log.split()[1].isdigit():
                digits.append(log)
            else:
                letters.append(log)
                
        letters.sort(key = (lambda x: (x.split()[1:], x.split()[0])))
        return letters + digits

Once we isolate the letter logs from the digit ones, sorting them independently is fairly easy. The return value then simply becomes their list concatenation

Time Complexity: O(max(Llog(L), L+ D)) for L letter strings in array or for concatenation

Space Complexity: O(N)

Approach 2: Custom Sort

class Solution:
    def key(self, log):
        id, rest = log.split(" ", 1)
        return (0, rest, id) if rest[0].isalpha() else (1,)

    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        
        return sorted(logs, key = self.key)

The isolation of the log and digit ones can be avoided by encoding the digit ones in the comparison function as well. By using the decreasing order of priority on the tuple, we can assign them the right order, while still preserving the order of the digit strings by assigning them the same value.

Time Complexity: O(Nlog(N)) for L letter strings in array

Space Complexity: O(N)