Reorder Data in Log Files

Problem

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.

Examples

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"]

Solution

Method 1 – Custom Sorting

Intuition

Divide the logs into letter-logs and digit-logs. Letter-logs are sorted by their content and, if needed, by their identifier, while digit-logs retain their original sequence. This is possible because the type of log can be identified by the first character after the identifier.

Approach

1. Separate each log into its identifier and the rest of its content.
2. Determine whether the content begins with a letter or a digit.
3. Group letter-logs and digit-logs into different lists.
4. Sort the letter-logs lexicographically by content, and by identifier if the contents are the same.
5. Combine the sorted letter-logs with the digit-logs, preserving the original order of digit-logs.
6. Return the final merged list.

We can use java's String split function with limit: Java String split method.

Code

C++

class Solution {
public:
	 vector<string> reorderLogFiles(vector<string>& logs) {
		  vector<string> let, dig;
		  for (auto& log : logs) {
				int pos = log.find(' ');
				if (isdigit(log[pos + 1]))
					 dig.push_back(log);
				else
					 let.push_back(log);
		  }
		  sort(let.begin(), let.end(), [](const string& a, const string& b) {
				int i1 = a.find(' '), i2 = b.find(' ');
				string c1 = a.substr(i1 + 1), c2 = b.substr(i2 + 1);
				if (c1 != c2) return c1 < c2;
				return a.substr(0, i1) < b.substr(0, i2);
		  });
		  let.insert(let.end(), dig.begin(), dig.end());
		  return let;
	 }
};

Go

func reorderLogFiles(logs []string) []string {
    let := []string{}
    dig := []string{}
    for _, log := range logs {
        idx := 0
        for i, c := range log {
            if c == ' ' {
                idx = i
                break
            }
        }
        if log[idx+1] >= '0' && log[idx+1] <= '9' {
            dig = append(dig, log)
        } else {
            let = append(let, log)
        }
    }
    sort.Slice(let, func(i, j int) bool {
        i1 := strings.IndexByte(let[i], ' ')
        i2 := strings.IndexByte(let[j], ' ')
        c1 := let[i][i1+1:]
        c2 := let[j][i2+1:]
        if c1 != c2 {
            return c1 < c2
        }
        return let[i][:i1] < let[j][:i2]
    })
    return append(let, dig...)
}

Java

class Solution {
	 public String[] reorderLogFiles(String[] logs) {
		  List<String> let = new ArrayList<>(), dig = new ArrayList<>();
		  for (String log : logs) {
				int idx = log.indexOf(' ');
				if (Character.isDigit(log.charAt(idx + 1)))
					 dig.add(log);
				else
					 let.add(log);
		  }
		  let.sort((a, b) -> {
				int i1 = a.indexOf(' '), i2 = b.indexOf(' ');
				String c1 = a.substring(i1 + 1), c2 = b.substring(i2 + 1);
				if (!c1.equals(c2)) return c1.compareTo(c2);
				return a.substring(0, i1).compareTo(b.substring(0, i2));
		  });
		  let.addAll(dig);
		  return let.toArray(new String[0]);
	 }
}

Kotlin

class Solution {
    fun reorderLogFiles(logs: Array<String>): Array<String> {
        val let = mutableListOf<String>()
        val dig = mutableListOf<String>()
        for (log in logs) {
            val idx = log.indexOf(' ')
            if (log[idx + 1].isDigit()) dig.add(log)
            else let.add(log)
        }
        let.sortWith(Comparator { a, b ->
            val i1 = a.indexOf(' ')
            val i2 = b.indexOf(' ')
            val c1 = a.substring(i1 + 1)
            val c2 = b.substring(i2 + 1)
            if (c1 != c2) c1.compareTo(c2)
            else a.substring(0, i1).compareTo(b.substring(0, i2))
        })
        return (let + dig).toTypedArray()
    }
}

Python

from typing import List

class Solution:
    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        let, dig = [], []
        for log in logs:
            idx = log.find(' ')
            if log[idx + 1].isdigit():
                dig.append(log)
            else:
                let.append(log)
        let.sort(key=lambda x: (x[x.find(' ') + 1:], x[:x.find(' ')]))
        return let + dig

Rust

impl Solution {
    pub fn reorder_log_files(logs: Vec<String>) -> Vec<String> {
        let mut let_logs = Vec::new();
        let mut dig_logs = Vec::new();
        for log in logs {
            let idx = log.find(' ').unwrap();
            if log.as_bytes()[idx + 1].is_ascii_digit() {
                dig_logs.push(log);
            } else {
                let_logs.push(log);
            }
        }
        let_logs.sort_by(|a, b| {
            let i1 = a.find(' ').unwrap();
            let i2 = b.find(' ').unwrap();
            let c1 = &a[i1 + 1..];
            let c2 = &b[i2 + 1..];
            if c1 != c2 {
                c1.cmp(c2)
            } else {
                a[..i1].cmp(&b[..i2])
            }
        });
        let_logs.extend(dig_logs);
        let_logs
    }
}

Complexity

• ⏰ Time complexity: O(n log n), where n is the number of logs (sorting letter-logs dominates).
• 🧺 Space complexity: O(n), for storing separated logs.