Reorder Data in Log Files

Med

#0891Time: 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.1 company

Algorithms

Sorting

Data structures

Array String

Companies

Snap

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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.
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.
Merging: Finally, we create a new array and populate it first with the sorted letterLogs and then with the digitLogs.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public String[] reorderLogFiles(String[] logs) {7        List<String> letterLogs = new ArrayList<>();8        List<String> digitLogs = new ArrayList<>();9 10        for (String log : logs) {11            // The second argument '2' ensures we only split at the first space.12            if (Character.isDigit(log.split(" ", 2)[1].charAt(0))) {13                digitLogs.add(log);14            } else {15                letterLogs.add(log);16            }17        }18 19        // Sort the letter-logs using a lambda expression for the comparator.20        Collections.sort(letterLogs, (log1, log2) -> {21            String[] split1 = log1.split(" ", 2);22            String[] split2 = log2.split(" ", 2);23            24            // Compare contents first.25            int contentComparison = split1[1].compareTo(split2[1]);26            if (contentComparison != 0) {27                return contentComparison;28            }29            30            // If contents are the same, compare identifiers.31            return split1[0].compareTo(split2[0]);32        });33 34        // Combine the sorted letter-logs and the original digit-logs.35        String[] result = new String[logs.length];36        int i = 0;37        for (String log : letterLogs) {38            result[i++] = log;39        }40        for (String log : digitLogs) {41            result[i++] = log;42        }43 44        return result;45    }46}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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:

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

1import java.util.Arrays;2import java.util.Comparator;3 4class Solution {5    public String[] reorderLogFiles(String[] logs) {6        Comparator<String> myComp = (log1, log2) -> {7            // Split each log into two parts: identifier and content.8            String[] split1 = log1.split(" ", 2);9            String[] split2 = log2.split(" ", 2);10 11            boolean isDigit1 = Character.isDigit(split1[1].charAt(0));12            boolean isDigit2 = Character.isDigit(split2[1].charAt(0));13 14            // Case 1: Both are letter-logs.15            if (!isDigit1 && !isDigit2) {16                // Compare the content first.17                int cmp = split1[1].compareTo(split2[1]);18                if (cmp != 0) {19                    return cmp;20                }21                // If content is the same, compare identifiers.22                return split1[0].compareTo(split2[0]);23            }24 25            // Case 2: log1 is letter, log2 is digit.26            if (!isDigit1) {27                return -1;28            }29            // Case 3: log1 is digit, log2 is letter.30            if (!isDigit2) {31                return 1;32            }33            34            // Case 4: Both are digit-logs.35            return 0;36        };37 38        Arrays.sort(logs, myComp);39        return logs;40    }41}

Complexity

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

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  String[] reorderLogFiles(String[] logs) {4    Arrays.sort(logs, this ::cmp);5    return logs;6  }7private8  int cmp(String a, String b) {9    String[] t1 = a.split(" ", 2);10    String[] t2 = b.split(" ", 2);11    boolean d1 = Character.isDigit(t1[1].charAt(0));12    boolean d2 = Character.isDigit(t2[1].charAt(0));13    if (!d1 && !d2) {14      int v = t1[1].compareTo(t2[1]);15      return v == 0 ? t1[0].compareTo(t2[0]) : v;16    }17    if (d1 && d2) {18      return 0;19    }20    return d1 ? 1 : -1;21  }22}

1class Solution {2public:3  vector<string> reorderLogFiles(vector<string> &logs) {4    stable_sort(logs.begin(), logs.end(),5                [](const string &log1, const string &log2) {6                  int idx1 = log1.find(' ');7                  int idx2 = log2.find(' ');8                  string id1 = log1.substr(0, idx1);9                  string id2 = log2.substr(0, idx2);10                  string content1 = log1.substr(idx1 + 1);11                  string content2 = log2.substr(idx2 + 1);12                  bool isLetter1 = isalpha(content1[0]);13                  bool isLetter2 = isalpha(content2[0]);14                  if (isLetter1 && isLetter2) {15                    if (content1 != content2) {16                      return content1 < content2;17                    }18                    return id1 < id2;19                  }20                  return isLetter1 > isLetter2;21                });22    return logs;23  }24};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem