LeetCode Solutions Blog

Reorder Data in Log Files

Number: 974

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Reorder an array of logs so that letter-logs come before digit-logs. Letter-logs are ordered lexicographically by content and, if tied, by identifier; digit-logs maintain their original order.

Key Insights

Separate the logs into letter-logs and digit-logs.
Determine the type of log by checking if the first character of the log's content is a digit.
Sort letter-logs by their content and use identifiers as a secondary key.
Retain the relative order of digit-logs using a stable approach.

Space and Time Complexity

Time Complexity: O(N log N) for sorting the letter-logs, where N is the number of logs. Space Complexity: O(N) for storing the letter and digit logs separately.

Solution

The solution involves splitting each log into an identifier and the rest of the content. For each log, check if the content starts with a digit to classify it as a digit-log; otherwise, classify it as a letter-log. Then, sort the letter-logs lexicographically by content and identifier. Finally, concatenate the sorted letter-logs with the original-order digit-logs to produce the final ordering.

Code Solutions

def reorder_log_files(logs):
    # Helper function to determine if a log is a digit-log.
    def is_digit_log(log):
        # Split log into identifier and content.
        token = log.split(" ", 1)[1]
        # Check if the first character is a digit.
        return token[0].isdigit()
    
    letter_logs = []
    digit_logs = []
    
    # Separate logs into letter and digit logs.
    for log in logs:
        if is_digit_log(log):
            digit_logs.append(log)
        else:
            letter_logs.append(log)
    
    # Sort letter logs by content; if tie, by identifier.
    letter_logs.sort(key=lambda log: (log.split(" ", 1)[1], log.split(" ", 1)[0]))
    
    # Return concatenated list: sorted letter logs then original digit logs.
    return letter_logs + digit_logs

# Example usage:
logs = ["dig1 8 1 5 1", "let1 art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"]
print(reorder_log_files(logs))