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.

  1. 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).

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

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