Reorder Data in Log Files — Day 13(Python)

Photo by Viktor Talashuk on Unsplash

Today we will be looking into one of Amazon’s popular coding questions.

937. Reorder Data in Log Files

You have an array of logs. Each log is a space-delimited string of words.

For each log, the first word in each log is an alphanumeric identifier. Then, either:

• Each word after the identifier will consist only of lowercase letters, or;
• Each word after the identifier will consist only of digits.

We will call these two varieties of logs letter-logs and digit-logs. It is guaranteed that each log has at least one word after its identifier.

Reorder the logs so that all of the letter-logs come before any digit-log. The letter-logs are ordered lexicographically ignoring identifiers, with the identifier used in case of ties. The digit-logs should be put in their original order.

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

Constraints:

1. 0 <= logs.length <= 100
2. 3 <= logs[i].length <= 100
3. logs[i] is guaranteed to have an identifier and a word after the identifier.

Solution

The significant part of solving this problem is learning to use the split function and lambda in python.

1. Create two lists; letter_log and digit_log, one that includes letters and the other that includes numerals. We will use the split function to separate the identifier and the next part.
2. Using the isdigit function, identify if the second part is digit or alphabets and accordingly place it in the letter_log list or digit_log list.

for l in logs:
    if l.split()[1].isdigit():
        digit_log.append(l)
    else:
        letter_log.append(l)

3. Sort the letter_log list based on the part after the identifier. I have used lambda to do so.

letter_log = sorted(letter_log, key = lambda x: (x.split(' ',1)[1], x.split(' ',1)[0]))

4. Append the sorted letter_log list and the digit_log list to the output list.

output += letter_log + digit_log

The complete code is as below

class Solution:
    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        digit_log = []
        letter_log = []
        output = []
        for l in logs:
            if l.split()[1].isdigit():
                digit_log.append(l)
            else:
                letter_log.append(l)
        
        letter_log = sorted(letter_log, key = lambda x: (x.split(' ',1)[1], x.split(' ',1)[0]))
        output += letter_log + digit_log
        return output

Complexity Analysis

Time Complexity

The time complexity to sort string takes O(NlogN). Hence time complexity of the above algorithm is O(NlogN).

Space Complexity

We are using additional storage space while separating the digit log and letter log and the size of both the lists will not exceed N. Hence Space complexity is O(N).