Reorder Data in Log Files

medium array string sorting

Problem

Each log is a string of words. Letter-logs come first (sorted lexicographically by body then identifier); digit-logs stay in original order.

Inputlogs = ["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"]

Split each log on the first space; classify by whether the body starts with a digit.

logs (one per ';')

def reorderLogFiles(logs):
    letters, digits = [], []
    for log in logs:
        ident, body = log.split(" ", 1)
        (digits if body[0].isdigit() else letters).append((ident, body, log))
    letters.sort(key=lambda x: (x[1], x[0]))
    return [x[2] for x in letters] + [x[2] for x in digits]

function reorderLogFiles(logs) {
  const letters = [], digits = [];
  for (const log of logs) {
    const sp = log.indexOf(' ');
    const body = log.slice(sp + 1);
    if (body[0] >= '0' && body[0] <= '9') digits.push(log);
    else letters.push([log.slice(0, sp), body, log]);
  }
  letters.sort((a, b) => a[1] === b[1] ? a[0].localeCompare(b[0]) : a[1].localeCompare(b[1]));
  return [...letters.map(x => x[2]), ...digits];
}

class Solution {
    public String[] reorderLogFiles(String[] logs) {
        List<String[]> letters = new ArrayList<>();
        List<String> digits = new ArrayList<>();
        for (String log : logs) {
            int sp = log.indexOf(' ');
            String body = log.substring(sp + 1);
            if (Character.isDigit(body.charAt(0))) digits.add(log);
            else letters.add(new String[]{ log.substring(0, sp), body, log });
        }
        letters.sort((a, b) -> a[1].equals(b[1]) ? a[0].compareTo(b[0]) : a[1].compareTo(b[1]));
        String[] out = new String[logs.length];
        int k = 0;
        for (String[] e : letters) out[k++] = e[2];
        for (String d : digits) out[k++] = d;
        return out;
    }
}

vector<string> reorderLogFiles(vector<string>& logs) {
    vector<tuple<string, string, string>> letters;
    vector<string> digits;
    for (auto& log : logs) {
        auto sp = log.find(' ');
        string body = log.substr(sp + 1);
        if (isdigit(body[0])) digits.push_back(log);
        else letters.push_back({log.substr(0, sp), body, log});
    }
    sort(letters.begin(), letters.end(), [](auto& a, auto& b) {
        if (get<1>(a) != get<1>(b)) return get<1>(a) < get<1>(b);
        return get<0>(a) < get<0>(b);
    });
    vector<string> out;
    for (auto& e : letters) out.push_back(get<2>(e));
    for (auto& d : digits) out.push_back(d);
    return out;
}

Explanation

There are two kinds of logs: letter-logs (their body is words) and digit-logs (their body is numbers). The rule is that all letter-logs come first, sorted by their content, and all digit-logs stay in their original order at the end. The cleanest approach is to split them into two buckets and treat each bucket separately.

For each log we split off the identifier (the first word) from the body using the first space. We peek at body[0]: if it is a digit, the log goes into digits; otherwise into letters as a tuple of (identifier, body, original).

We then sort only the letter-logs by body first, then identifier as the tie-breaker (key=lambda x: (x[1], x[0])). Digit-logs are never sorted — appending them in the order we saw them preserves their original sequence.

Finally we return the sorted letter-log originals followed by the digit-log originals.

Example: with "let1 art can" and "let3 art zero", both bodies start with "art", so the identifiers "let1" vs "let3" break the tie, putting let1 before let3. The two digit-logs "dig1 ..." and "dig2 ..." trail at the end unchanged.

Time: O(n · m · log n) Space: O(n · m)