Domain 1EasyCORE

Reorder Data in Log Files

The problem requires reordering an array of log entries based on specific rules: - **Inputs**: An array of strings (`logs`), where each string represents a log entry. - **Outputs**: The reordered array of log entries according to the specified rules. - **Implicit Constraints**: - Logs are space-delimited, with the first word being an identifier. - There are two types of logs: letter-logs and digit-logs. - Letter-logs should come before digit-logs. - Letter-logs should be sorted lexicographically by their contents. If contents are identical, sort by identifiers. - Digit-logs should maintain their relative order.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

937. Reorder Data in Log Files

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 54.8%


Problem Breakdown

The problem requires reordering an array of log entries based on specific rules:

  • Inputs: An array of strings (logs), where each string represents a log entry.
  • Outputs: The reordered array of log entries according to the specified rules.
  • Implicit Constraints:
    • Logs are space-delimited, with the first word being an identifier.
    • There are two types of logs: letter-logs and digit-logs.
    • Letter-logs should come before digit-logs.
    • Letter-logs should be sorted lexicographically by their contents. If contents are identical, sort by identifiers.
    • Digit-logs should maintain their relative order.

Intuition

A brute-force approach would involve sorting all logs and then separating them into letter-logs and digit-logs. However, this is inefficient because it doesn’t take advantage of the fact that digit-logs need to maintain their original order. A better approach involves:

  1. Separating the logs into letter-logs and digit-logs.
  2. Sorting the letter-logs based on their contents and identifiers.
  3. Concatenating the sorted letter-logs with the unsorted digit-logs.

This approach ensures that we only sort what needs to be sorted, improving efficiency.

Approach

  1. Separate Logs: Iterate through the logs and separate them into two lists: letter_logs and digit_logs.
  2. Sort Letter Logs:
    • Split each letter-log into its identifier and content.
    • Sort the letter_logs based on a tuple (content, identifier), ensuring lexicographical order by content first, then by identifier.
  3. Concatenate Results: Combine the sorted letter_logs with the original digit_logs.

Complexity Analysis

  • Time Complexity: O(n log n), where n is the number of letter-logs. Sorting the letter-logs dominates the time complexity.
  • Space Complexity: O(n), as we store separate lists for letter-logs and digit-logs.

Solution

def reorderLogFiles(logs):
    # Separate logs into letter_logs and digit_logs
    letter_logs = []
    digit_logs = []
    
    for log in logs:
        if log.split(' ')[1].isalpha():
            letter_logs.append(log)
        else:
            digit_logs.append(log)
    
    # Sort letter_logs by content then identifier
    letter_logs.sort(key=lambda x: (x.split(' ', 1)[1], x.split(' ', 1)[0]))
    
    # Concatenate sorted letter_logs with unsorted 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(reorderLogFiles(logs))

Edge Cases Handled

  • Empty Input: If the input list is empty, the function will return an empty list.
  • All Digit Logs: If all logs are digit-logs, they will be returned in their original order.
  • All Letter Logs: If all logs are letter-logs, they will be sorted by content and identifier.
  • Mixed Logs: The function handles a mix of letter-logs and digit-logs correctly, placing all letter-logs before digit-logs.