LeetCode 937: Reorder Data in Log Files

A clear explanation of solving Reorder Data in Log Files using custom sorting and stable handling of digit logs.

leetcodestringsortingcustom-sort

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:

Log type Meaning
Letter-log Every word after the identifier contains lowercase letters
Digit-log Every word after the identifier contains digits

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

Item Meaning
Input A list of log strings
Output The reordered list of logs
Letter-log order Sort by content, then identifier
Digit-log order Keep original relative order
Constraint Each log has an identifier and at least one word after it

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)
  1. 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:

Log Type
"dig1 8 1 5 1" Digit-log
"let1 art can" Letter-log
"dig2 3 6" Digit-log
"let2 own kit dig" Letter-log
"let3 art zero" Letter-log

Letter-log keys:

Log Sort key
"let1 art can" ("art can", "let1")
"let2 own kit dig" ("own kit dig", "let2")
"let3 art zero" ("art zero", "let3")

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.

Metric Value Why
Time O(n log n * L) Sorting letter-logs compares string keys
Space O(n * L) Separate lists and sort keys store log strings

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()
Test Why
Standard example Checks all rules together
Mixed logs Checks multi-word contents
Same content Identifier tie-breaker
Only digit-logs Original order must remain