Reorder Data in Log Files LeetCode Solution

Difficulty Level Easy
Frequently asked in Amazon Audible GoogleViews 3274

Problem Statement

Reorder Data in Log Files LeetCode Solution – 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.

Reorder Data in Log Files LeetCode Solution

Example

Test Case 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”.

Approach:

  1. First, move all the dig-log to the end while keeping the original order.
  2. Sort the rest let-log by using a customized comparator.

my solution takes advantage of what we’re guaranteed in the problem:

  1. guaranteed to have a word following an identifier (allows me to use indexOf ‘ ‘ freely).
  2. letter logs need to be ordered lexicographically, so we can use the built-in compare function when we know we have two.
  3. number logs need to be sorted naturally, so we just say they’re all “equal” to each other and trust java’s built-in sort feature to be stable.
  4. number logs need to be after letter logs, so once we find out they’re different, we return one of the other and short-circuit.

Code for Reorder Data in Log Files

Java Program

class Solution {
    public String[] reorderLogFiles(String[] logs) {
        Comparator<String> myComp = new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                int s1SpaceIndex = s1.indexOf(' ');
                int s2SpaceIndex = s2.indexOf(' ');
                char s1FirstCharacter = s1.charAt(s1SpaceIndex+1);
                char s2FirstCharacter = s2.charAt(s2SpaceIndex+1);
                
                if (s1FirstCharacter <= '9') {
                    if (s2FirstCharacter <= '9') return 0;
                    else return 1;
                }
                if (s2FirstCharacter <= '9') return -1;
                
                int preCompute = s1.substring(s1SpaceIndex+1).compareTo(s2.substring(s2SpaceIndex+1));
                if (preCompute == 0) return s1.substring(0,s1SpaceIndex).compareTo(s2.substring(0,s2SpaceIndex));
                return preCompute;
            }
        };
        
        Arrays.sort(logs, myComp);
        return logs;
    }
}

C++ Program

class Solution {
public:
   static bool custsort(const string &A, const string& B){
    string sa = A.substr(A.find(' ') + 1);
    string sb = B.substr(B.find(' ') + 1);
    if(isdigit(sa[0]))
        return false;
    else if(isdigit(sb[0]))
        return true;
       else if(sa.compare(sb)==0){
           string fa=A.substr(0,A.find(' '));
           string fb = B.substr(0,B.find(' '));
           
           return fa.compare(fb)<0;
       }
    return sa.compare(sb) < 0;
}

vector<string> reorderLogFiles(vector<string> &logs) {
    stable_sort(logs.begin(), logs.end(), custsort);
    return logs;
    }
};

Complexity Analysis for Reorder Data in Log Files LeetCode Solution

Time complexity: O(n*logn) as we are sorting the array.

Space complexity: O(1) as we are not using any extra space.

Translate »