# Reorder Data in Log Files
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/reorder-data-in-log-files)
Canonical: https://scaleengineer.com/dsa/problems/reorder-data-in-log-files
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, String
**Companies:** [Snap](https://scaleengineer.com/companies/snap)
---
## Problem
You are given an array of `logs`. Each log is a space-delimited string of words, where the first word is the **identifier**.

There are two types of logs:

* **Letter-logs**: All words (except the identifier) consist of lowercase English letters.
* **Digit-logs**: All words (except the identifier) consist of digits.

Reorder these logs so that:

1. The **letter-logs** come before all **digit-logs**.
2. The **letter-logs** are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers.
3. The **digit-logs** maintain their relative ordering.

Return _the final order of the logs_.

**Example 1:**

**Input:** logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
**Output:** ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]
**Explanation:**
The letter-log contents are all different, so their ordering is "art can", "art zero", "own kit dig".
The digit-logs have a relative order of "dig1 8 1 5 1", "dig2 3 6".

**Example 2:**

**Input:** logs = ["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]
**Output:** ["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]

**Constraints:**

* `1 <= logs.length <= 100`
* `3 <= logs[i].length <= 100`
* All the tokens of `logs[i]` are separated by a **single** space.
* `logs[i]` is guaranteed to have an identifier and at least one word after the identifier.

# Approaches
## Separate Lists and Sort
This approach involves iterating through the logs, separating them into two distinct lists—one for letter-logs and one for digit-logs. The list of letter-logs is then sorted according to the specified rules. Finally, the sorted letter-logs and the original digit-logs are concatenated to produce the final result.
**Time:** O(N * M * log N). Let N be the number of logs and M be the maximum length of a log. Separating logs takes O(N * M). Sorting L letter-logs takes O(L * log L * M) because each string comparison can take up to O(M). Since L <= N, the total complexity is dominated by sorting, resulting in O(N * M * log N). · **Space:** O(N * M), where N is the number of logs and M is the maximum length of a single log. This is because we create two new lists that, in the worst case, will store all the log strings.
**Pros:** The logic is straightforward and easy to follow.; Separation of concerns is clear: classification, sorting, and merging are distinct steps.
**Cons:** Requires extra space proportional to the input size (`O(N * M)`) to store the separate lists, which can be inefficient for large inputs.; Involves multiple passes over the data: one to separate, one to merge, in addition to the sorting process.
### Explanation
The core idea is to handle the two types of logs separately. We can achieve this by performing a single pass through the input array to classify each log.

1.  **Partitioning**: We create two lists, `letterLogs` and `digitLogs`. We iterate through the input `logs`. For each log, we inspect the character following the first space. If it's a letter, the log is added to `letterLogs`; if it's a digit, it's added to `digitLogs`. This process naturally preserves the relative order of the digit-logs.

2.  **Sorting**: We then sort the `letterLogs` list. A custom sorting logic is required: first, compare logs by their content (the string part after the identifier). If the contents are the same, then compare them by their identifiers.

3.  **Merging**: Finally, we create a new array and populate it first with the sorted `letterLogs` and then with the `digitLogs`.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public String[] reorderLogFiles(String[] logs) {
        List<String> letterLogs = new ArrayList<>();
        List<String> digitLogs = new ArrayList<>();

        for (String log : logs) {
            // The second argument '2' ensures we only split at the first space.
            if (Character.isDigit(log.split(" ", 2)[1].charAt(0))) {
                digitLogs.add(log);
            } else {
                letterLogs.add(log);
            }
        }

        // Sort the letter-logs using a lambda expression for the comparator.
        Collections.sort(letterLogs, (log1, log2) -> {
            String[] split1 = log1.split(" ", 2);
            String[] split2 = log2.split(" ", 2);
            
            // Compare contents first.
            int contentComparison = split1[1].compareTo(split2[1]);
            if (contentComparison != 0) {
                return contentComparison;
            }
            
            // If contents are the same, compare identifiers.
            return split1[0].compareTo(split2[0]);
        });

        // Combine the sorted letter-logs and the original digit-logs.
        String[] result = new String[logs.length];
        int i = 0;
        for (String log : letterLogs) {
            result[i++] = log;
        }
        for (String log : digitLogs) {
            result[i++] = log;
        }

        return result;
    }
}
```
### Algorithm
- Initialize two empty lists, `letterLogs` and `digitLogs`.
- Iterate through each `log` in the input `logs` array.
- For each `log`, split it into an identifier and content part.
- Check the first character of the content. If it's a digit, add the log to `digitLogs`. Otherwise, add it to `letterLogs`.
- After separating all logs, sort the `letterLogs` list using a custom comparator.
  - The comparator first compares the content of two logs.
  - If the contents are identical, it then compares their identifiers.
- Create a new result array.
- Add all elements from the sorted `letterLogs` list to the result array.
- Append all elements from the `digitLogs` list to the result array. The relative order of digit-logs is preserved as they were added sequentially.
- Return the final combined array.

## In-Place Sort with a Custom Comparator
A more efficient and concise approach is to use a single sorting operation on the entire `logs` array with a custom-defined `Comparator`. This comparator encapsulates all the reordering rules, handling the different log types and sorting criteria in one go, leveraging the power and stability of built-in sorting algorithms.
**Time:** O(N * M * log N). The sort function performs O(N * log N) comparisons. Each comparison involves string splitting and comparisons, taking O(M) time, where N is the number of logs and M is the maximum length of a log. · **Space:** O(M * log N). The space is primarily used by the sorting algorithm. Timsort, used in Java's `Arrays.sort`, has a space complexity that can range from O(log N) to O(N) for references. Additionally, each comparison creates temporary strings of size O(M), where M is the max log length. Thus, a conservative estimate is O(M * log N).
**Pros:** More space-efficient as it avoids creating large auxiliary data structures.; Code is more concise and elegant, encapsulating all sorting logic within the comparator.; Leverages powerful, highly-optimized, and stable built-in sorting algorithms.
**Cons:** The comparator logic can be complex to write and debug correctly.; Repeatedly splitting strings inside the comparator for every comparison can be slightly less performant than pre-processing, though this is a minor concern for the given constraints.
### Explanation
Instead of manually separating the logs, we can define all the ordering rules within a single `Comparator` and pass it to a standard sorting function. This is generally more efficient in terms of space and can lead to cleaner code.

The `Comparator` for two logs, `log1` and `log2`, works as follows:
1.  **Split and Classify**: For each log, we split it into its identifier and content. We then check the first character of the content to classify it as a letter-log or a digit-log.
2.  **Comparison Logic**:
    - If both are letter-logs, we compare their content lexicographically. If the contents are identical, we fall back to comparing their identifiers.
    - If one is a letter-log and the other is a digit-log, the letter-log is always considered 'smaller' and thus comes first.
    - If both are digit-logs, we need to preserve their original relative order. A stable sorting algorithm (like the one used in Java's `Arrays.sort` for objects) will not change the relative order of elements that the comparator deems 'equal'. Therefore, for two digit-logs, our comparator should return `0`.

This single, powerful comparison function allows the sort algorithm to arrange the entire array correctly in one pass.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public String[] reorderLogFiles(String[] logs) {
        Comparator<String> myComp = (log1, log2) -> {
            // Split each log into two parts: identifier and content.
            String[] split1 = log1.split(" ", 2);
            String[] split2 = log2.split(" ", 2);

            boolean isDigit1 = Character.isDigit(split1[1].charAt(0));
            boolean isDigit2 = Character.isDigit(split2[1].charAt(0));

            // Case 1: Both are letter-logs.
            if (!isDigit1 && !isDigit2) {
                // Compare the content first.
                int cmp = split1[1].compareTo(split2[1]);
                if (cmp != 0) {
                    return cmp;
                }
                // If content is the same, compare identifiers.
                return split1[0].compareTo(split2[0]);
            }

            // Case 2: log1 is letter, log2 is digit.
            if (!isDigit1) {
                return -1;
            }
            // Case 3: log1 is digit, log2 is letter.
            if (!isDigit2) {
                return 1;
            }
            
            // Case 4: Both are digit-logs.
            return 0;
        };

        Arrays.sort(logs, myComp);
        return logs;
    }
}
```
### Algorithm
- Use a standard library sort function (e.g., `Arrays.sort` in Java) on the entire `logs` array.
- Provide a custom `Comparator` to the sort function to define the ordering rules.
- Inside the `Comparator`'s `compare(log1, log2)` method:
  - Split `log1` and `log2` into their identifier and content parts.
  - Determine if each log is a letter-log or a digit-log.
  - Implement the comparison logic based on four cases:
    1. **Both are letter-logs**: Compare contents first, then identifiers if contents are equal.
    2. **`log1` is letter, `log2` is digit**: `log1` comes first (return -1).
    3. **`log1` is digit, `log2` is letter**: `log2` comes first (return 1).
    4. **Both are digit-logs**: Maintain relative order. A stable sort achieves this if the comparator returns 0.
- The sort function will reorder the array in-place according to the comparator's logic.
- Return the sorted `logs` array.

# Solutions
### Java

```java
class Solution {
public
  String[] reorderLogFiles(String[] logs) {
    Arrays.sort(logs, this ::cmp);
    return logs;
  }
private
  int cmp(String a, String b) {
    String[] t1 = a.split(" ", 2);
    String[] t2 = b.split(" ", 2);
    boolean d1 = Character.isDigit(t1[1].charAt(0));
    boolean d2 = Character.isDigit(t2[1].charAt(0));
    if (!d1 && !d2) {
      int v = t1[1].compareTo(t2[1]);
      return v == 0 ? t1[0].compareTo(t2[0]) : v;
    }
    if (d1 && d2) {
      return 0;
    }
    return d1 ? 1 : -1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<string> reorderLogFiles(vector<string> &logs) {
    stable_sort(logs.begin(), logs.end(),
                [](const string &log1, const string &log2) {
                  int idx1 = log1.find(' ');
                  int idx2 = log2.find(' ');
                  string id1 = log1.substr(0, idx1);
                  string id2 = log2.substr(0, idx2);
                  string content1 = log1.substr(idx1 + 1);
                  string content2 = log2.substr(idx2 + 1);
                  bool isLetter1 = isalpha(content1[0]);
                  bool isLetter2 = isalpha(content2[0]);
                  if (isLetter1 && isLetter2) {
                    if (content1 != content2) {
                      return content1 < content2;
                    }
                    return id1 < id2;
                  }
                  return isLetter1 > isLetter2;
                });
    return logs;
  }
};

```

### Python

```python
class Solution:
    def reorderLogFiles(self, logs: List[str]) -> List[str]: def cmp(x): a, b = x . split(' ', 1) return (0, b, a) if b[0]. isalpha() else (1,) return sorted(logs, key=cmp)

```