This blog is now live! A lot of these posts were just sitting on my computer but it's now hooked up to GitHub Pages via Jekyll. GitHub Pages was very pleasant to use and extend.
In solving news: I'm focusing on using more Python languages features at the moment.
- Two Sum
Problem: Given an array of integers and a target, return the indices of the two numbers that add up to the target.
I really like the solution to this problem because it's so simple when you think about it. When faced with the problem initially it can be hard to see any route to a
class Solution(object):def twoSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""num_dict = dict()for idx, val in enumerate(nums):if target - val in num_dict:return [num_dict[target - val], idx]else:num_dict[val] = idx
We iterate through the array adding everything to a Dictionary (after checking that the other number we're looking for hasn't been added yet). Awkwardly, we store the value as the key and the indice as the value.
- Valid Anagram
Problem: Given two strings
s, dermine if
t is an anagram of
While I was working through my solution here, I felt like I was doing too much work to solve the problem, which turned out to be true.
from collections import Counterclass Solution(object):def isAnagram(self, s, t):""":type s: str:type t: str:rtype: bool"""if len(s) != len(t):return Falses_count = Counter()t_count = Counter()for i in s:s_count[i] += 1for i in t:t_count[i] += 1for key, val in s_count.items():if key not in t_count:return Falseif s_count[key] != t_count[key]:return Falsereturn True
Runtime complexity: Once through the string with
O(1) Dictonary additions, once through the
s Dictionary with
O(1) Dictionary checks:
After researching, it seems that the fastest solution would be to use two arrays of size 26, incrementing and decrementing the values per each character. Then we check the arrays against each other.
Fastest algorithm would be to map each of the 26 English characters to a unique prime number. Then calculate the product of the string. By the fundamental theorem of arithmetic, 2 strings are anagrams if and only if their products are the same.
- Length of Last Word
Problem: Given a string, return the length of the last word.
I start from the end of the string and work backwards and take care to perform a low number of checks (about
s[i]) per character. (It turns out that it wasn't a low enough number of checks!)
class Solution(object):def lengthOfLastWord(self, s):""":type s: str:rtype: int"""word_len = 0for i in range(len(s)-1, -1, -1):if s[i] != ' ':word_len += 1elif word_len != 0:breakif word_len == 0:return 0return word_len
Tricky test cases with this one, like
' ' and
Some people used two loops, one starting from the end to find the last space character, and one to walk back through towards the end counting the non-space characters. This is more optimal because less checks are performed. For example:
'a b '. When there is extra whitespace on the end, my algoritm performs roughly 1.5x as many operations.