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

January 06, 2019

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.

500. 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'),
        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:]):
        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).

937. 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
        # 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).

136. 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:
        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.

Join the newsletter

Join 200+ people signed up to my newsletter on programming and personal growth!

Andrew Healey

Hey, I'm Andrew Healey. I'm a software engineer in London, UK. I write about things I wanted to read when I was a beginner.