Reorder Data in Log Files

LeetCode Problem #937

You have an array of logs.  Each log is a space delimited string of words.

For each log, the first word in each log is an alphanumeric identifier.  Then, either:

• Each word after the identifier will consist only of lowercase letters, or;
• Each word after the identifier will consist only of digits.

We will call these two varieties of logs letter-logs and digit-logs.  It is guaranteed that each log has at least one word after its identifier.

Reorder the logs so that all of the letter-logs come before any digit-log.  The letter-logs are ordered lexicographically ignoring identifier, with the identifier used in case of ties.  The digit-logs should be put in their original order.

Return the final order of the logs.

Example 1

Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]

Constraints

1. 0 <= logs.length <= 100
2. 3 <= logs[i].length <= 100
3. logs[i] is guaranteed to have an identifier, and a word after the identifier.

Solution

import Foundation

func isAlpha(_ log: String) -> Bool {
    let log = log.components(separatedBy: " ")
    let firstValue = String(log[1].last!)
    return Int(firstValue) == nil
}

func reorderLogFiles(_ logs: [String]) -> [String] {
    var logIndexA = 0
    var logIndexB = logs.count - 1
    var logFiles = [String](repeating: "", count: logIndexB + 1)
    
    for log in logs.reversed() {
        if isAlpha(log) {
            logFiles[logIndexA] = log
            logIndexA += 1
        } else {
            logFiles[logIndexB] = log
            logIndexB -= 1
        }
    }
    
    logFiles[0...logIndexA - 1].sort {
        let a = $0.drop { $0 != " " }
        let b = $1.drop { $0 != " " }
        
        if a == b {
            return $0 < $1
        }
        
        return a < b
    }
    
    return logFiles
}

Time Complexity

We must traverse all elements at least once. This takes \(O(n) \) time.

Sorting the array takes \(O(nlogn) \) for a comparison sort. A non-comparison sort can be used in this case, which would lead to a \(O(n) \) runtime.

Therefore, our runtime is \(O(n) \).

Space Complexity

The space used is equal to the input. Therefore, our space complexity is \(O(n) \).

Think Differently

1. An important part of the program was to differentiate between an alphabetic log and a numeric log. I used the Int initializer to convert numeric strings to type Int. I didn't think of what would happen if the number was greater than Int.max.
2. At first I ambitiously tried to implement my own sorting algorithm. I believe the best algorithm to use would be a non-comparison sorting algorithm. We could get the runtime down to \(O(n) \) with this type of algorithm. I ended up using the Swift sort closure.
3. At some point, I didn't check my bounds for indexing the logFiles array.