[Google Question][LeetCode] 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:

1. Letter-logs: All words (except the identifier) consist of lowercase English letters.
2. 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:

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

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

Approach: The problem is all about the custom comparator. You can just look at the implementation to understand the approach.

Implementation in C#:

    public string[] ReorderLogFiles(string[] logs) 

    {

        List<string> letterList = new List<string>();

        List<string> digitList = new List<string>();    

        this.BuildLetterAndDigitLogsList(logs, letterList, digitList);    

        letterList = new List<string>(this.GetSortedLetterArray(letterList));

        int index = 0;

        foreach (string letter in letterList)

        {

            logs[index++] = letter;

        }

        foreach (string digit in digitList)

        {

            logs[index++] = digit;

        }

        return logs;

    }

    

    private string[] GetSortedLetterArray(List<string> letterList)

    {

        string[] letterArr = letterList.ToArray();

        Array.Sort(letterArr, (letter1, letter2) => {

            int index1 = letter1.IndexOf(' ');

            int index2 = letter2.IndexOf(' ');

            int firstCompare = letter1.Substring(index1 + 1).CompareTo(letter2.Substring(index2 + 1));

            if (firstCompare != 0)

            {

                return firstCompare;

            }

            return letter1.Substring(0, index1).CompareTo(letter2.Substring(0, index2));

        });

        return letterArr;

    }

    

    private void BuildLetterAndDigitLogsList(string[] logs, List<string> letterList, List<string> digitList)

    {

        for (int i = 0; i < logs.Length; ++i)

        {

            if (char.IsDigit(logs[i][logs[i].IndexOf(' ') + 1]))

            {

                digitList.Add(logs[i]);

            }

            else

            {

                letterList.Add(logs[i]);

            }

        }

    }

Complexity: O(n) + O (k logk) if we are n is total length of logs and k is number of letter logs. We are ignoring the complexity of substring method.