Leetcode - Episode 6 - Progressively Harder (3x E)

I've been going through the problems roughly sorted by their acceptance rate: higher -> lower. Today, the difficulty is slowly creeping up. I'm looking forward to tackling some Mediums soon.

Keyboard Row

Problem: Given a list of words, return only those that can be typed using one keyboard row

This was a neat problem to solve. At one point, I was lower()ing the words to account for capitalization but simply adding capital letters to the Sets decreased the runtime by ~13%.

class Solution(object):
    def findWords(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
        rows = [set('qwertyuiopQWERTYUIOP'),
                set('asdfghjklASDFGHJKL'),
                set('zxcvbnmZXCVBNM')]
        one_row_words = []
        
        for word in words:
            for row in rows:
                if word[0] in row:
                    if all(char in row for char in word[1:]):
                        one_row_words.append(word)
                    break
        return one_row_words

I made sure to break once the word's row had been found to save on loop cycles over 'dead' words.

Runtime complexity: O(n).

Spacetime complexity: O(1).

Reorder Log Files

Problem: Given an array of logs with alphanumeric identifiers at the start, sort them so that letter-only logs come before digit-only logs.

I've added in some comments where there are specific rules but I recommend checking their description as this one's problem statement is harder to understand than any solution.

This was a fun one to solve.

class Solution(object):
    def reorderLogFiles(self, logs):
        """
        :type logs: List[str]
        :rtype: List[str]
        """
        letter_logs = []
        digit_logs = []
        for log in logs:
            log = log.split()
            # check ascii value to determine digit or letter log
            if ord(log[1][0]) < 66:
                # the digit-logs should be put in their original order
                digit_logs.append(log)
            else:
                letter_logs.append(log)
        
        # the letter-logs are ordered lexicographically ignoring identifier,
        # with the identifier used in case of ties
        letter_logs.sort(key=lambda x: x[1:] + x[0:1])
                         
        return [' '.join(log) for log in letter_logs + digit_logs]

I'm getting a little better with Python generators. I really like how they feel to use, and how they affect the structure of these programs.

Runtime complexity: Separate logs O(n), sort letter logs O(n log n), join logs O(n). Ergo: O(n).

Spacetime complexity: O(n).

Single Number

Problem: Given an array N of integers, numbers all appear twice except for one. Return that integer.

I knew this could be XORed but I couldn't remember so implemented it with a Set and made a note to check after.

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums_set = set()
        for i in nums:
            if i in nums_set:
                nums_set.remove(i)
            else:
                nums_set.add(i)
        for i in nums_set:
            return i

Runtime complexity: O(n).

Space complexity: O(n).

And now without that extra space, using XOR.

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = 0
        for i in nums:
            result ^= i
        return result

Runtime complexity: O(n).

Space complexity: -.

See you next time.