Reorder Data in Log Files
MedPrompt
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 <= 1003 <= 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,
letterLogsanddigitLogs. - Iterate through each
login the inputlogsarray. - 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 toletterLogs. - After separating all logs, sort the
letterLogslist 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
letterLogslist to the result array. - Append all elements from the
digitLogslist 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,
letterLogsanddigitLogs. We iterate through the inputlogs. For each log, we inspect the character following the first space. If it's a letter, the log is added toletterLogs; if it's a digit, it's added todigitLogs. This process naturally preserves the relative order of the digit-logs. -
Sorting: We then sort the
letterLogslist. 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
letterLogsand then with thedigitLogs.
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; }}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.
Solutions
Solution
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; }}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.