LeetCode 937: Reorder Data in Log Files

Problem Restatement

We are given a list of log strings.

Each log has this structure:

identifier content

The first word is the identifier.

The rest of the log is the content.

There are two kinds of logs:

We need to reorder the logs using these rules:

1. All letter-logs come before all digit-logs.
2. Letter-logs are sorted by their content.
3. If two letter-logs have the same content, sort them by identifier.
4. Digit-logs keep their original relative order.

The official statement defines the same ordering rules: letter-logs first, letter-logs sorted lexicographically by content then identifier, and digit-logs unchanged in relative order.

Input and Output

Function shape:

class Solution:
    def reorderLogFiles(self, logs: list[str]) -> list[str]:
        ...

Examples

Example 1:

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

The letter-logs are:

"let1 art can"
"let2 own kit dig"
"let3 art zero"

Sort them by content:

"art can"
"art zero"
"own kit dig"

So the sorted letter-logs are:

"let1 art can"
"let3 art zero"
"let2 own kit dig"

The digit-logs keep their original order:

"dig1 8 1 5 1"
"dig2 3 6"

Final answer:

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

First Thought: Separate the Two Types

The ordering rules treat letter-logs and digit-logs differently.

So the simplest approach is:

1. Put letter-logs into one list.
2. Put digit-logs into another list.
3. Sort only the letter-logs.
4. Concatenate sorted letter-logs with digit-logs.

This directly matches the problem rules.

Key Insight

The identifier is not the primary sorting key for letter-logs.

For a letter-log like:

"let1 art can"

we split it into:

identifier = "let1"
content    = "art can"

The sorting key should be:

(content, identifier)

So Python can sort letter-logs with a key function.

Digit-logs should not be sorted at all.

Algorithm

Create two empty lists:

letter_logs = []
digit_logs = []

For each log:

1. Split it into identifier and content:

identifier, content = log.split(" ", 1)

2. Check the first character of content.

If it is a digit, append the whole log to digit_logs.

Otherwise, append the whole log to letter_logs.

Then sort letter_logs by:

(content, identifier)

Finally return:

letter_logs + digit_logs

Walkthrough

Use:

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

Separate logs:

Letter-log keys:

After sorting:

[
    "let1 art can",
    "let3 art zero",
    "let2 own kit dig",
]

Append digit-logs in original order:

[
    "dig1 8 1 5 1",
    "dig2 3 6",
]

Correctness

Every log is either a letter-log or a digit-log. The algorithm places each log into exactly one of these two groups.

All letter-logs are returned before all digit-logs because the final result is letter_logs + digit_logs.

The algorithm sorts letter_logs using the key (content, identifier). Therefore, letter-logs are ordered lexicographically by content first. If two contents are equal, their identifiers are compared next. This exactly matches the required ordering.

The algorithm never sorts digit_logs. It appends them as they appear in the input and later appends the list unchanged to the result. Therefore, digit-logs keep their original relative order.

Since all required ordering rules are satisfied, the returned list is correct.

Complexity

Let:

n = len(logs)

and let L be the maximum log length.

If there are k letter-logs, the sorting cost is more precisely O(k log k * L).

Implementation

class Solution:
    def reorderLogFiles(self, logs: list[str]) -> list[str]:
        letter_logs = []
        digit_logs = []

        for log in logs:
            identifier, content = log.split(" ", 1)

            if content[0].isdigit():
                digit_logs.append(log)
            else:
                letter_logs.append(log)

        def sort_key(log: str) -> tuple[str, str]:
            identifier, content = log.split(" ", 1)
            return (content, identifier)

        letter_logs.sort(key=sort_key)

        return letter_logs + digit_logs

Code Explanation

We keep two lists:

letter_logs = []
digit_logs = []

For each log, split only once:

identifier, content = log.split(" ", 1)

The second argument 1 matters. It keeps the full content together, even when the content has many words.

We classify the log by checking the first content character:

if content[0].isdigit():

If it is a digit-log, store it without sorting:

digit_logs.append(log)

Otherwise, store it as a letter-log:

letter_logs.append(log)

The sort key splits the log again and returns:

(content, identifier)

This gives the required letter-log order.

Finally:

return letter_logs + digit_logs

puts letter-logs before digit-logs.

Testing

def run_tests():
    s = Solution()

    assert s.reorderLogFiles([
        "dig1 8 1 5 1",
        "let1 art can",
        "dig2 3 6",
        "let2 own kit dig",
        "let3 art zero",
    ]) == [
        "let1 art can",
        "let3 art zero",
        "let2 own kit dig",
        "dig1 8 1 5 1",
        "dig2 3 6",
    ]

    assert s.reorderLogFiles([
        "a1 9 2 3 1",
        "g1 act car",
        "zo4 4 7",
        "ab1 off key dog",
        "a8 act zoo",
    ]) == [
        "g1 act car",
        "a8 act zoo",
        "ab1 off key dog",
        "a1 9 2 3 1",
        "zo4 4 7",
    ]

    assert s.reorderLogFiles([
        "let2 abc",
        "let1 abc",
        "dig1 1 2",
    ]) == [
        "let1 abc",
        "let2 abc",
        "dig1 1 2",
    ]

    assert s.reorderLogFiles([
        "dig1 3 4",
        "dig2 1 2",
    ]) == [
        "dig1 3 4",
        "dig2 1 2",
    ]

    print("all tests passed")

run_tests()