Reorder Data in Log Files

LeetCode 974 | Difficulty: Medium

Medium

Problem Description

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:

- The **letter-logs** come before all **digit-logs**.

- The **letter-logs** are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers.

- 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.

Topics: Array, String, Sorting

---

Approach

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 272 ms)

Metric	Value
Runtime	272 ms
Memory	32.3 MB
Date	2019-02-24

Solution

public class Solution {
    public string[] ReorderLogFiles(string[] logs) {
    List<string> letterLogs = new List<string>(); 
    List<string> digitLogs = new List<string>();
    foreach (var log in logs)
    {
        if (char.IsDigit(log[log.IndexOf(' ') + 1]))
        {
            digitLogs.Add(log);
        }
        else
        {
            letterLogs.Add(log);
        }
    }

    letterLogs.Sort((a, b) =>
    {
        string a_substr = a.Substring(a.IndexOf(' ') + 1);
        string b_substr = b.Substring(b.IndexOf(' ') + 1);
        return a_substr.CompareTo(b_substr);
    });
      
    letterLogs.AddRange(digitLogs);
    return letterLogs.ToArray();
        }
}

📜 1 more C# submission(s)

Submission (2019-08-03) — 280 ms, 32.8 MB

public class Solution {
    public string[] ReorderLogFiles(string[] logs) {
    List<string> letterLogs = new List<string>(); 
    List<string> digitLogs = new List<string>();
    foreach (var log in logs)
    {
        if (char.IsDigit(log[log.IndexOf(' ') + 1]))
        {
            digitLogs.Add(log);
        }
        else
        {
            letterLogs.Add(log);
        }
    }

    letterLogs.Sort((a, b) =>
    {
        string a_substr = a.Substring(a.IndexOf(' ') + 1);
        string b_substr = b.Substring(b.IndexOf(' ') + 1);
        var result = a_substr.CompareTo(b_substr);
        if (result == 0)
            result =  a.Substring(0, a.IndexOf(' ')).CompareTo(b.Substring(0, b.IndexOf(' ')));
        return result;  
    });
      
    letterLogs.AddRange(digitLogs);
    return letterLogs.ToArray();
        }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.