937. Reorder Data in Log Files

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:

1. The letter-logs come before all digit-logs.
2. The letter-logs are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers.
3. 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.

From: LeetCode
Link: 937. Reorder Data in Log Files

Solution:

Ideas:

• Step 1: Separate logs into two groups:

  • Letter-logs → contain letters after the identifier.
  • Digit-logs → contain digits after the identifier.

• Step 2: Sort only the letter-logs using custom rules:

  • Compare by content (the part after the identifier).
  • If contents are the same, compare by identifier.

• Step 3: Keep digit-logs in their original order (no sorting).

• Step 4: Combine the sorted letter-logs followed by digit-logs to form the result.

• Step 5: Return the reordered array of logs.

Code:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
static int first_space_pos(const char *s) {
    const char *p = strchr(s, ' ');
    return (int)(p - s);
}

static int is_digit_log(const char *s) {
    int i = first_space_pos(s);
    return isdigit((unsigned char)s[i + 1]);
}

static int cmp_letter_logs(const void *pa, const void *pb) {
    const char *a = *(const char * const *)pa;
    const char *b = *(const char * const *)pb;

    int sa = first_space_pos(a);
    int sb = first_space_pos(b);

    const char *ca = a + sa + 1; // content after identifier
    const char *cb = b + sb + 1;

    int c = strcmp(ca, cb);
    if (c != 0) return c;

    // contents equal -> compare identifiers lexicographically
    int la = sa, lb = sb;
    int lmin = la < lb ? la : lb;
    int idcmp = memcmp(a, b, lmin);
    if (idcmp != 0) return idcmp;
    // if prefixes equal, shorter identifier comes first
    return (la > lb) - (la < lb);
}

char** reorderLogFiles(char** logs, int logsSize, int* returnSize) {
    *returnSize = logsSize;
    if (logsSize == 0) {
        return NULL;
    }

    // Collect letter-logs and digit-logs (preserve original order for digit-logs)
    char **letters = (char **)malloc(sizeof(char*) * logsSize);
    char **digits  = (char **)malloc(sizeof(char*) * logsSize);
    int lc = 0, dc = 0;

    for (int i = 0; i < logsSize; ++i) {
        if (is_digit_log(logs[i])) digits[dc++] = logs[i];
        else                        letters[lc++] = logs[i];
    }

    // Sort only letter-logs by content then identifier
    qsort(letters, lc, sizeof(char*), cmp_letter_logs);

    // Build result: letters first, then digits (digits keep relative order)
    char **res = (char **)malloc(sizeof(char*) * logsSize);
    for (int i = 0; i < lc; ++i) res[i] = letters[i];
    for (int i = 0; i < dc; ++i) res[lc + i] = digits[i];

    free(letters);
    free(digits);
    return res;
}