#937

Medium

LeetCode Problem Workspace

Reorder Data in Log Files

Reorder Data in Log Files requires sorting letter-logs lexicographically while keeping digit-logs in original order for arrays of strings.

array string sorting

Problem Statement

You are given an array of logs, where each log is a space-delimited string with the first word as an identifier. Logs are classified as either letter-logs containing alphabetic words or digit-logs containing numeric words after the identifier.

Reorder the logs so that all letter-logs come before any digit-logs. Letter-logs should be sorted lexicographically by their content, with identifiers breaking ties. Digit-logs must remain in their original relative order. Return the array of logs after this reordering.

Examples

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"]

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"]

Example details omitted.

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.

Solution Approach

Separate Letter-Logs and Digit-Logs

Iterate through the array and classify each log by inspecting the first character of the second word. Append letter-logs to one list and digit-logs to another. This separation ensures sorting only affects letter-logs, preserving the original sequence of digit-logs.

Sort Letter-Logs Lexicographically

Sort the letter-logs by comparing the content portion of each log. Use the identifier as a tie-breaker if two logs have identical content. This approach guarantees correct lexicographical ordering without disturbing digit-logs.

Concatenate Sorted Letter-Logs with Digit-Logs

After sorting, append the digit-logs list to the end of the sorted letter-logs. This final array maintains the required order: sorted letter-logs first and original-sequence digit-logs last, completing the reorder efficiently.

Complexity Analysis

Metric	Value
Time	\mathcal{O}(M \cdot N \cdot \log N)
Space	\mathcal{O}(M \cdot N)

Time complexity is O(M * N * log N) because sorting letter-logs requires comparing strings of average length M over N logs. Space complexity is O(M * N) to store separated lists and handle string comparisons.

What Interviewers Usually Probe

Are you maintaining the relative order of digit-logs?
Can you efficiently sort based on content while handling tie-breakers?
How do you handle logs that have identical contents but different identifiers?

Common Pitfalls or Variants

Common pitfalls

Sorting digit-logs accidentally along with letter-logs, which breaks relative order.
Using only identifiers for sorting letter-logs instead of the full content.
Failing to split logs correctly when a log contains both letters and numbers in content.

Follow-up variants

Reorder logs but reverse the lexicographical order of letter-logs while keeping digit-logs stable.
Reorder logs allowing mixed content but only prioritizing logs starting with letters.
Reorder logs in-place without using extra space for separated lists.

FAQ

What is the main idea behind Reorder Data in Log Files?

The key idea is to separate letter-logs from digit-logs, sort letter-logs lexicographically, then append digit-logs in their original order.

How do I handle ties when two letter-logs have the same content?

Use the identifiers as tie-breakers to determine the relative order between logs with identical content.

Can I sort digit-logs as well?

No, digit-logs must retain their original relative order according to the problem's requirements.

What is the time complexity of the solution?

The solution runs in O(M * N * log N) time, where N is the number of logs and M is the maximum length of a log content.

Which data structure helps manage letter-log and digit-log separation efficiently?

Using two separate lists or arrays ensures letter-logs can be sorted independently without affecting digit-logs.

terminal

Solution

Solution 1: Custom Sorting

We can use a custom sorting method to divide the logs into two categories: letter logs and digit logs.

1

2

3

4

5

6

7

class Solution:
    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        def f(log: str):
            id_, rest = log.split(" ", 1)
            return (0, rest, id_) if rest[0].isalpha() else (1,)

        return sorted(logs, key=f)

Continue Practicing

#893 groups of special equivalent strings #833 find and replace in string #1048 longest string chain