# LeetCode 937: Reorder Data in Log Files

## Problem Restatement

We are given a list of log strings.

Each log has this structure:

```text
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:

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

## Examples

Example 1:

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

The letter-logs are:

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

Sort them by content:

```text
"art can"
"art zero"
"own kit dig"
```

So the sorted letter-logs are:

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

The digit-logs keep their original order:

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

Final answer:

```python
[
    "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:

```text
"let1 art can"
```

we split it into:

```text
identifier = "let1"
content    = "art can"
```

The sorting key should be:

```python
(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:

```python
letter_logs = []
digit_logs = []
```

For each log:

1. Split it into identifier and content:

```python
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:

```python
(content, identifier)
```

Finally return:

```python
letter_logs + digit_logs
```

## Walkthrough

Use:

```python
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:

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

Append digit-logs in original order:

```python
[
    "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:

```python
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

```python
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:

```python
letter_logs = []
digit_logs = []
```

For each log, split only once:

```python
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:

```python
if content[0].isdigit():
```

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

```python
digit_logs.append(log)
```

Otherwise, store it as a letter-log:

```python
letter_logs.append(log)
```

The sort key splits the log again and returns:

```python
(content, identifier)
```

This gives the required letter-log order.

Finally:

```python
return letter_logs + digit_logs
```

puts letter-logs before digit-logs.

## Testing

```python
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 |