Leetcode 256. Paint House

[locked]

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example,costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

Using DP. Try 3 paint ways and get the min.

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def minCost(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        if not costs:
            return 0
        
        min_cost = [costs[0], [0, 0, 0]]
        
        n = len(costs)
        for i in xrange(1, n):
            min_cost[i % 2][0] = costs[i][0] + \
                                 min(min_cost[(i - 1) % 2][1], min_cost[(i - 1) % 2][2])
            min_cost[i % 2][1] = costs[i][1] + \
                                 min(min_cost[(i - 1) % 2][0], min_cost[(i - 1) % 2][2])
            min_cost[i % 2][2] = costs[i][2] + \
                                 min(min_cost[(i - 1) % 2][0], min_cost[(i - 1) % 2][1])

        return min(min_cost[(n - 1) % 2])

Leetcode 255. Verify Preorder Sequence in Binary Search Tree

[locked]

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

It is not easy to achieve O(1) space.

# Time:  O(n)
# Space: O(1)

class Solution:
    # @param {integer[]} preorder
    # @return {boolean}
    def verifyPreorder(self, preorder):
        low, i = float("-inf"), -1
        for p in preorder:
            if p < low:
                return False
            while i >= 0 and p > preorder[i]:
                low = preorder[i]
                i -= 1
            i += 1
            preorder[i] = p
        return True

Leetcode 254. Factor Combinations

[locked]

Numbers can be regarded as product of its factors. For example,

1	8 = 2 x 2 x 2; = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

How to get factors and combine them properly? If we divide the number into as small as possible parts, we can do it. Or we can use DFS directly, which is even better and save a lot of trouble.

# Time:  O(nlogn)
# Space: O(logn)

class Solution:
    # @param {integer} n
    # @return {integer[][]}
    def getFactors(self, n):
        result = []
        factors = []
        self.getResult(n, result, factors)
        return result

    def getResult(self, n, result, factors):
        i = 2 if not factors else factors[-1]
        while i <= n / i:
            if n % i == 0:
                factors.append(i);
                factors.append(n / i);
                result.append(list(factors));
                factors.pop();
                self.getResult(n / i, result, factors);
                factors.pop()
            i += 1

Leetcode 253. Meeting Rooms II

[locked]
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required. 

For example, 
Given [[0, 30],[5, 10],[15, 20]], 
return 2. 

# Time:  O(nlogn)
# Space: O(n)

# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
    # @param {Interval[]} intervals
    # @return {integer}
    def minMeetingRooms(self, intervals):
        starts, ends = [], []
        for i in intervals:
            starts.append(i.start)
            ends.append(i.end)

        starts.sort()
        ends.sort()

        s, e = 0, 0
        min_rooms, cnt_rooms = 0, 0
        while s < len(starts):
            if starts[s] < ends[e]:
                cnt_rooms += 1  # Acquire a room.
                # Update the min number of rooms.
                min_rooms = max(min_rooms, cnt_rooms)
                s += 1
            else:
                cnt_rooms -= 1  # Release a room.
                e += 1

        return min_rooms

Leetcode 252. Meeting Rooms

[locked]

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

For example,

Given [[0, 30],[5, 10],[15, 20]],
return false.

So the thing is clear: detect the overlap. If comparing one by one, it is too low. Actually we can sort the intervals by staring time, if one's end exceeds its next one's start, return False.

# Time:  O(nlogn)
# Space: O(n)
#
# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
    # @param {Interval[]} intervals
    # @return {boolean}
    def canAttendMeetings(self, intervals):
        intervals.sort(key=lambda x: x.start)
    
        for i in xrange(1, len(intervals)):
            if intervals[i].start < intervals[i-1].end:
                return False
        return True

Leetcode 251. Flatten 2D Vector

[locked]

Implement an iterator to flatten a 2d vector.

For example,
Given 2d vector =

[
  [1,2],
  [3],
  [4,5,6]
]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 2, 3, 4, 5, 6].

# Time:  O(1)
# Space: O(1)

class Vector2D:
    x, y = 0, 0
    vec = None

    # Initialize your data structure here.
    # @param {integer[][]} vec2d
    def __init__(self, vec2d):
        self.vec = vec2d
        self.x = 0
        if self.x != len(self.vec):
            self.y = 0
            self.adjustNextIter()

    # @return {integer}
    def next(self):
        ret = self.vec[self.x][self.y]
        self.y += 1
        self.adjustNextIter()
        return ret

    # @return {boolean}
    def hasNext(self):
        return self.x != len(self.vec) and self.y != len(self.vec[self.x])

    def adjustNextIter(self):
        while self.x != len(self.vec) and self.y == len(self.vec[self.x]): 
            self.x += 1
            if self.x != len(self.vec):
                self.y = 0

Leetcode 250. Count Univalue Subtrees

[locked]

Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

For example:

Given binary tree,

1	5 / \ 1 5 / \ \ 5 5 5

return 4.

Based on the description, the tree must consider its all children. So it is easier.

Go recursion with each node, and call a function to judge if it is a uni-value subtree.

# Time:  O(n)
# Space: O(h)
#
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param {TreeNode} root
    # @return {integer}
    def countUnivalSubtrees(self, root):
        [is_uni, count] = self.isUnivalSubtrees(root, 0);
        return count;

    def isUnivalSubtrees(self, root, count):
        if not root:
            return [True, count]

        [left, count] = self.isUnivalSubtrees(root.left, count)
        [right, count] = self.isUnivalSubtrees(root.right, count)
        if self.isSame(root, root.left, left) and \
           self.isSame(root, root.right, right):
                count += 1
                return [True, count]

        return [False, count]
    
    def isSame(self, root, child, is_uni):
        return not child or (is_uni and root.val == child.val)

Leetcode 249.Group Shifted Strings

[locked]

Given a string, we can “shift” each of its letter to its successive letter, for example: “abc” -> “bcd”. We can keep “shifting” which forms the sequence:

1	"abc" -> "bcd" -> ... -> "xyz"

Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example,

given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"], Return:

1	[ ["abc","bcd","xyz"], ["az","ba"], ["acef"], ["a","z"] ]

Note: For the return value, each inner list’s elements must follow the lexicographic order.

So the thing is quite clear: for one char or only one word of the length, they are in the list. For others, get the differences of ord() to the first char, if it is negative, plus 26, then pick strings that have the same list of differences. For example, for "abc", "bcd" and "xyz", their difference lists should be [1,1]. Or we can use a string to replace the list.

# Time:  O(nlogn)
# Space: O(n)

class Solution:
    # @param {string[]} strings
    # @return {string[][]}
    def groupStrings(self, strings):
        groups = {};
        for s in strings:  # Grouping.
            if self.hashStr(s) not in groups:
                groups[self.hashStr(s)] = [s]
            else:
                groups[self.hashStr(s)].append(s)

        result = []
        for key, val in groups.iteritems():
            result.append(sorted(val))
        
        return result

    def hashStr(self, s):
        base = ord(s[0])
        hashcode = ""
        for i in xrange(len(s)):
            if ord(s[i]) - base >= 0:
                hashcode += unichr(ord('a') + ord(s[i]) - base)
            else:
                hashcode += unichr(ord('a') + ord(s[i]) - base + 26)
        return hashcode

Leetcode 248. Strobogrammatic Number III

[locked]
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

---

This problem is way harder than the previous two. Reference: kamyu104's GitHub.

# Time:  O(5^(n/2))
# Space: O(n)

class Solution:
    lookup = {'0':'0', '1':'1', '6':'9', '8':'8', '9':'6'}
    cache = {}

    # @param {string} low
    # @param {string} high
    # @return {integer}
    def strobogrammaticInRange(self, low, high):
        count = self.countStrobogrammaticUntil(high, False) - \
                self.countStrobogrammaticUntil(low, False) + \
                self.isStrobogrammatic(low)
        return count if count >= 0 else 0

    def countStrobogrammaticUntil(self, num,  can_start_with_0):
        if can_start_with_0 and num in self.cache:
            return self.cache[num]

        count = 0
        if len(num) == 1:
            for c in ['0', '1', '8']:
                if num[0] >= c:
                    count += 1
            self.cache[num] = count
            return count
        
        for key, val in self.lookup.iteritems():
            if can_start_with_0 or key != '0':
                if num[0] > key:
                    if len(num) == 2:  # num is like "21"
                        count += 1
                    else:  # num is like "201"
                        count += self.countStrobogrammaticUntil('9' * (len(num) - 2), True)
                elif num[0] == key:
                    if len(num) == 2:  # num is like 12".
                        if num[-1] >= val:
                            count += 1 
                    else:
                        if num[-1] >= val:  # num is like "102".
                            count += self.countStrobogrammaticUntil(self.getMid(num), True);
                        elif (self.getMid(num) != '0' * (len(num) - 2)):  # num is like "110".
                            count += self.countStrobogrammaticUntil(self.getMid(num), True) - \
                                     self.isStrobogrammatic(self.getMid(num))

        if not can_start_with_0: # Sum up each length.
            for i in xrange(len(num) - 1, 0, -1):
                count += self.countStrobogrammaticByLength(i)
        else:
            self.cache[num] = count

        return count

    def getMid(self, num):
        return num[1:len(num) - 1]

    def countStrobogrammaticByLength(self, n):
        if n == 1:
            return 3
        elif n == 2:
            return 4
        elif n == 3:
            return 4 * 3
        else:
            return 5 * self.countStrobogrammaticByLength(n - 2)

    def isStrobogrammatic(self, num):
        n = len(num)
        for i in xrange((n+1) / 2):
            if num[n-1-i] not in self.lookup or \
               num[i] != self.lookup[num[n-1-i]]:
                return False
        return True

Leetcode 247. Strobogrammatic Number II

[locked]
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Find all strobogrammatic numbers that are of length = n.

---

Using DFS. All 5 numbers can be used for each half position except the single position(6 and 9 can not be used while there is only one position), and the other half are decided in this way. So we have nearly 5^(n/2) such numbers!

# Time:  O(n^2 * 5^(n/2))
# Space: O(n)

class Solution:
    lookup = {'0':'0', '1':'1', '6':'9', '8':'8', '9':'6'}

    # @param {integer} n
    # @return {string[]}
    def findStrobogrammatic(self, n):
        return self.findStrobogrammaticRecu(n, n)

    def findStrobogrammaticRecu(self, n, k):
        if k == 0:
            return ['']
        elif k == 1:
            return ['0', '1', '8']
        
        result = []
        for num in self.findStrobogrammaticRecu(n, k - 2):
            for key, val in self.lookup.iteritems():
                if n != k or key != '0':
                    result.append(key + num + val)

        return result

Leetcode 246. Strobogrammatic Number

[locked]
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Write a function to determine if a number is strobogrammatic. The number is represented as a string.
For example, the numbers "69", "88", and "818" are all strobogrammatic.

---

Interesting problem. So we have to find out all single strobogrammatic numbers first. 0, 1, 6, 8, 9, and that's all. To convert, just create a mapping relationship. Also this number should be symmetric from both sides.

# Time:  O(n)
# Space: O(1)

class Solution:
    lookup = {'0':'0', '1':'1', '6':'9', '8':'8', '9':'6'}

    # @param {string} num
    # @return {boolean}
    def isStrobogrammatic(self, num):
        n = len(num)
        for i in xrange((n+1) / 2):
            if num[n-1-i] not in self.lookup or \
               num[i] != self.lookup[num[n-1-i]]:
                return False
            i += 1
        return True

Leetcode 245. Shortest Word Distance III

[locked]
This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.
Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
word1 and word2 may be the same and they represent two individual words in the list.
For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “makes”, word2 = “coding”, return 1.
Given word1 = "makes", word2 = "makes", return 3.
Note:
You may assume word1 and word2 are both in the list.

---

Still easy. Just divide to two cases: word1 equals word2 or not.

# Time:  O(n)
# Space: O(1)

class Solution:
    # @param {string[]} words
    # @param {string} word1
    # @param {string} word2
    # @return {integer}
    def shortestWordDistance(self, words, word1, word2):
        dist = float("inf")
        i, index1, index2 = 0, None, None
        while i < len(words):
            if words[i] == word1:
                if index1 is not None and word1 == word2:
                    dist = min(dist, abs(index1 - i))
                index1 = i
            elif words[i] == word2:
                index2 = i

            if index1 is not None and index2 is not None:
                dist = min(dist, abs(index1 - index2))
            i += 1

        return dist

Leetcode 244. Shortest Word Distance II

[locked]
This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it? 
Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list. 
For example, 
Assume that words = ["practice", "makes", "perfect", "coding", "makes"]. 
Given word1 = “coding”, word2 = “practice”, return 3. 
Given word1 = "makes", word2 = "coding", return 1. 
Note: 

You may assume that word1 does not equal to word2, and word1 and word2 are both in the list. 

---

When the operations are frequent, we should enhance the time performance. So hash table now is a better idea. Also we can do better than comparing all of i and j when finding out the min distance.

# Time:  init: O(n), lookup: O(a + b), a, b is occurences of word1, word2
# Space: O(n)

class WordDistance:
    # initialize your data structure here.
    # @param {string[]} words
    def __init__(self, words):
        self.wordIndex = {}
        for i in xrange(len(words)):
            if words[i] not in self.wordIndex:
                self.wordIndex[words[i]] = [i]
            else:
                self.wordIndex[words[i]].append(i)

    # @param {string} word1
    # @param {string} word2
    # @return {integer}
    # Adds a word into the data structure.
    def shortest(self, word1, word2):
        indexes1 = self.wordIndex[word1]
        indexes2 = self.wordIndex[word2]

        i, j, dist = 0, 0, float("inf")
        while i < len(indexes1) and j < len(indexes2):
            dist = min(dist, abs(indexes1[i] - indexes2[j]))
            if indexes1[i] < indexes2[j]:
                i += 1
            else:
                j += 1

        return dist

Leetcode 243. Shortest Word Distance

[locked]
Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.

---

This definition of distance is a little bit strange indeed. However this problem is not very hard and we have many ways to solve it. For example, hash table. Or we can save space by using two indexes to record and calculate distance every time and get the min distance.

# Time:  O(n)
# Space: O(1)

class Solution:
    # @param {string[]} words
    # @param {string} word1
    # @param {string} word2
    # @return {integer}
    def shortestDistance(self, words, word1, word2):
        dist = float("inf")
        i, index1, index2 = 0, None, None
        while i < len(words):
            if words[i] == word1:
                index1 = i
            elif words[i] == word2:
                index2 = i

            if index1 is not None and index2 is not None:
                dist = min(dist, abs(index1 - index2))
            i += 1

        return dist

Leetcode 242. Valid Anagram

https://leetcode.com/problems/valid-anagram/

return sorted(s) == sorted(t)
Run time is 96 ms.

Leetcode 241. Different Ways to Add Parentheses

https://leetcode.com/problems/different-ways-to-add-parentheses/

The main thought is to divide two parts when encountering a operator. And to avoid repeated calculation, we establish a lookup table to store calculated result.

Solution:

# T:O(n * Catalan numbers) S:O(n * Catalan numbers)
class Solution(object):
    def diffWaysToCompute(self, input):
        """
        :type input: str
        :rtype: List[int]
        """
        lookup = [[None for _ in xrange(len(input) + 1)] for _ in xrange(len(input) + 1)]
        ops = {'+': operator.add, '-': operator.sub, '*': operator.mul}

        def diffWaysToComputeRecu(left, right):
            if lookup[left][right]:
                return lookup[left][right]
            result = []
            for i in xrange(left, right):
                if input[i] in ops:
                    for x in diffWaysToComputeRecu(left, i):
                        for y in diffWaysToComputeRecu(i + 1, right):
                            result.append(ops[input[i]](x, y))
            
            if not result:
                result = [int(input[left:right])]
            lookup[left][right] = result     
            return lookup[left][right]
            
        return diffWaysToComputeRecu(0, len(input))

Run Time: 60 ms

Leetcode 240. Search a 2D Matrix II

https://leetcode.com/problems/search-a-2d-matrix-ii/

Solution:

# T:O(m+n) S:O(1)
class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        m, n = len(matrix), len(matrix[0])
        i, j = 0, n - 1
        while i < m and j > -1:
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] > target:
                j -= 1
            else: i += 1
        return False

Run Time: 128 ms

Leetcode 239. Sliding Window Maximum

https://leetcode.com/problems/sliding-window-maximum/

The hard point is to achieve O(n) time. Actually we can smell a sense of queue here. Python has a quite powerful deque data structure, and we can use that. Still using max() is too slow, we should link the whole process.

Solution:

# T:O(n) S:O(k)
from collections import deque

class Solution:
    # @param {integer[]} nums
    # @param {integer} k
    # @return {integer[]}
    def maxSlidingWindow(self, nums, k):
        q = deque()
        max_numbers = []

        for i in xrange(k):
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)

        for i in xrange(k, len(nums)):
            max_numbers.append(nums[q[0]])

            while q and nums[i] >= nums[q[-1]]:
                q.pop()

            while q and q[0] <= i - k:
                q.popleft()

            q.append(i)

        if q:
            max_numbers.append(nums[q[0]])

        return max_numbers

Run Time: 208 ms

Leetcode 238. Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/

Because division is not allowed, so we should use multiplying only. The thought is to scan twice, first multiply left side, second multiply right.

Solution:

# T:O(n) S:O(1)
class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums: return []
            
        left_product = [1 for _ in xrange(len(nums))]
        for i in xrange(1, len(nums)):
            left_product[i] = left_product[i - 1] * nums[i - 1]
            
        right_product = 1
        for i in xrange(len(nums) - 2, -1, -1):
            right_product *= nums[i + 1]
            left_product[i] = left_product[i] * right_product

        return left_product

Run Time: 180 ms

Leetcode 237. Delete Node in a Linked List

https://leetcode.com/problems/delete-node-in-a-linked-list/

Very basic operation.

node.val = node.next.val
node.next = node.next.next

Run time is 68 ms.

Leetcode 236. Lowest Common Ancestor of a Binary Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

The elegant solution is using recursion. If p and q are in left and right, this is the node; or it will be in the subtree that has p and q.

Solution:

# T:O(h) S:O(h)
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if root in (None, p, q):
            return root

        left, right = [self.lowestCommonAncestor(child, p, q) \
                         for child in (root.left, root.right)]
        # 1. If the current subtree contains both p and q,
        #    return their LCA.
        # 2. If only one of them is in that subtree,
        #    return that one of them.
        # 3. If neither of them is in that subtree,
        #    return the node of that subtree.
        return root if left and right else left or right

Run Time: 156 ms

Leetcode 235. Lowest Common Ancestor of a Binary Search Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Because BST is a knid of binary tree, so if we use the result of binary tree, it is also correct but not that fast.

If we use BST's feature, the thing is clear: when the three nodes are on the same tree, there should be
s <= root.val <= b. If not, the two nodes must be on left  or right subtree, then use the value to decide go left or right.

Solution:

# T:O(n) S:O(1)
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        s, b = sorted([p.val, q.val])
        while not s <= root.val <= b:
            # Keep searching since root is outside of [s, b].
            root = root.left if s <= root.val else root.right
        # s <= root.val <= b.
        return root

Run Time: 132 ms

Leetcode 234. Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/

The task is easy, while O(1) space needs some thinking. We can get the length, then how to check? Because there is no way back in single linked list, we should reverse the first or last half and then do the check. Restoring the list is optional.

Solution:

# T:O(n) S:O(1)
class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        reverse, fast = None, head
        while fast and fast.next:
            fast = fast.next.next
            head.next, reverse, head = reverse, head, head.next

        # If the number of the nodes is odd,
        # set the head of the tail list to the next of the median node.
        tail = head.next if fast else head

        # Compare the reversed first half list with the second half list.
        # And restore the reversed first half list.
        is_palindrome = True
        while reverse:
            is_palindrome = is_palindrome and reverse.val == tail.val
            reverse.next, head, reverse = head, reverse, reverse.next
            tail = tail.next

        return is_palindrome

Run Time: 136 ms

Leetcode 233. Number of Digit One

https://leetcode.com/problems/number-of-digit-one/

The key point is to get the law.

Solution:

# T:O(lgn) S:O(1)
class Solution(object):
    def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int
        """
        res = 0
        left = right = len = 1
        if n <= 0: return 0
        while n >= len:
            left = n / len
            right = n % len
            if left % 10 >= 2:
                res += (left / 10 + 1) * len
            elif left % 10 == 1:
                res += (left / 10) * len + (right + 1)
            else: res += (left / 10) * len
            len *= 10
        return res

Run Time: 44 ms

Leetcode 232. Implement Queue using Stacks

https://leetcode.com/problems/implement-queue-using-stacks/

Solution:

# T:O(1) S:O(n)
class Queue:
    # initialize your data structure here.
    def __init__(self):
        self.A, self.B = [], []

    # @param x, an integer
    # @return nothing
    def push(self, x):
        self.A.append(x)

    # @return nothing
    def pop(self):
        self.peek()
        self.B.pop()
        
    # @return an integer
    def peek(self):
        if not self.B:
            while self.A:
                self.B.append(self.A.pop())
        return self.B[-1]
        
    # @return an boolean
    def empty(self):
        return not self.A and not self.B

Run Time: 40 ms

Leetcode 231. Power of Two

https://leetcode.com/problems/power-of-two/

2 one line solutions.

Solution 1:
return bin(n)[2:].count('1') == 1 and n > 0
Run time 64 ms;

Solution 2:
return n > 0 and (n & (n - 1)) == 0
Run time: 60 ms.

Leetcode 230. Kth Smallest Element in a BST

https://leetcode.com/problems/kth-smallest-element-in-a-bst/

We know that for a BST, left < root < right. So if we go left to the end, this is the smallest node, its root is the 2nd, and its root's right is the 3rd. In this way, we can get the kth smallest node. In order to go back, we need a stack.

Solution:

# T:O(max(h,k)) S:O(h)
class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        s, cur, rank = [], root, 0

        while s or cur:
            if cur:
                s.append(cur)
                cur = cur.left
            else:
                cur = s.pop()
                rank += 1
                if rank == k:
                    return cur.val
                cur = cur.right

        return float("-inf")

Run Time: 80 ms

Leetcode 229. Majority Element II

https://leetcode.com/problems/majority-element-ii/

Remember Majority Element one? In that problem, only one number can occur over n/2 times, and we solve it by +1 when it occurs and -1 when others occur, when count value equals 0 we change to the next number and set count 1, so in the end the current number is what we want.

So can we use the same thought here? For n/3, there will be at most two such numbers. Hence we can play the exactly same trick again, while this time there are two numbers.

Solution:

# T:O(n) S:O(1)
class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n1 = n2 = None
        c1 = c2 = 0
        for num in nums:
            if n1 == num:
                c1 += 1
            elif n2 == num:
                c2 += 1
            elif c1 == 0:
                n1, c1 = num, 1
            elif c2 == 0:
                n2, c2 = num, 1
            else:
                c1, c2 = c1 - 1, c2 - 1
        size = len(nums)
        return [n for n in (n1, n2) 
                   if n is not None and nums.count(n) > size / 3]

Run Time: 64 ms

Leetcode 228. Summary Ranges

https://leetcode.com/problems/summary-ranges/

Solution:

# T:O(n) S:O(n)
class Solution(object):
    def summaryRanges(self, nums):
        """
        :type nums: List[int]
        :rtype: List[str]
        """
        if not nums: return []
        i, ret = 0, []
        while i < len(nums):
            start = i
            while i < len(nums) - 1 and nums[i] == nums[i+1] - 1:
                i += 1
            end = i
            if start == end:
                ret.append(str(nums[i]))
            else:
                ret.append(str(nums[start])+"->"+str(nums[end]))
            i += 1
        return ret

Run Time: 56 ms

Leetcode 227. Basic Calculator II

https://leetcode.com/problems/basic-calculator-ii/

When there are '*' and '/', priority should be concerned.

Solution:

# T:O(n) S:O(n)
class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        operands, operators = [], []
        operand = ""
        for i in reversed(xrange(len(s))):
            if s[i].isdigit():
                operand += s[i]
                if i == 0  or not s[i-1].isdigit():
                    operands.append(int(operand[::-1]))
                    operand = ""
            elif s[i] == ')' or s[i] == '*' or s[i] == '/':
                operators.append(s[i])
            elif s[i] == '+' or s[i] == '-':
                while operators and \
                      (operators[-1] == '*' or operators[-1] == '/'):
                    self.compute(operands, operators)
                operators.append(s[i])
            elif s[i] == '(':
                while operators[-1] != ')':
                    self.compute(operands, operators)
                operators.pop()
                
        while operators:
            self.compute(operands, operators)
            
        return operands[-1]

    def compute(self, operands, operators):
        left, right = operands.pop(), operands.pop()
        op = operators.pop()
        if op == '+':
            operands.append(left + right)
        elif op == '-':
            operands.append(left - right)
        elif op == '*':
            operands.append(left * right)
        elif op == '/':
            operands.append(left / right)         

Run Time: 420 ms

Leetcode 226. Invert Binary Tree

https://leetcode.com/problems/invert-binary-tree/

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

Solution:

# T:O(n) S:O(h)
class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root: return None
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

Run Time: 40 ms

Leetcode 225. Implement Stack using Queues

https://leetcode.com/problems/implement-stack-using-queues/

Solution:

# T:push: O(n), pop: O(1), top: O(1) S:O(n)
class Queue:
    def __init__(self):
        self.data = collections.deque()
        
    def push(self, x):
        self.data.append(x)
    
    def peek(self):
        return self.data[0]
    
    def pop(self):
        return self.data.popleft()
    
    def size(self):
        return len(self.data)
    
    def empty(self):
        return len(self.data) == 0


class Stack:
    # initialize your data structure here.
    def __init__(self):
        self.q_ = Queue()

    # @param x, an integer
    # @return nothing
    def push(self, x):
        self.q_.push(x)
        for _ in xrange(self.q_.size() - 1):
            self.q_.push(self.q_.pop())

    # @return nothing
    def pop(self):
        self.q_.pop()

    # @return an integer
    def top(self):
        return self.q_.peek()

    # @return an boolean
    def empty(self):
        return self.q_.empty()

Run Time: 40 ms

Leetcode 224. Basic Calculator

https://leetcode.com/problems/basic-calculator/

For problems concerning sequence, stack is a good choice. Here we can build two stacks, one for operators, one for operands. Note the numbers might be greater than 9, so converting string to integer needs more attention.

Another problem is the process direction. For instance, 2-1+2=3, but if we use stack from left to right, N=[2,1,2], S=[-,+], we cannot use pop because in that way it would be 2-2+1=-1, so we have to reverse both N and S. Therefore we could reverse s and use pop operation.

Solution:

# T:O(n) S:O(n)
class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        operands, operators = [], []
        operand = ""
        for i in reversed(xrange(len(s))):
            if s[i].isdigit():
                operand += s[i]
                if i == 0  or not s[i-1].isdigit():
                    operands.append(int(operand[::-1]))
                    operand = ""
            elif s[i] == ')' or s[i] == '+' or s[i] == '-':
                operators.append(s[i])
            elif s[i] == '(':
                while operators[-1] != ')':
                    self.compute(operands, operators)
                operators.pop()
                
        while operators:
            self.compute(operands, operators)
            
        return operands[-1]

    def compute(self, operands, operators):
        left, right = operands.pop(), operands.pop()
        op = operators.pop()
        if op == '+':
            operands.append(left + right)
        elif op == '-':
            operands.append(left - right)

Run Time: 392 ms

Leetcode 223. Rectangle Area

https://leetcode.com/problems/rectangle-area/

The thought is simple: two areas of rectangles subtract overlapping area. The key is to get the overlapping area.

Solution:

# T:O(1) S:O(1)
class Solution(object):
    def computeArea(self, A, B, C, D, E, F, G, H):
        """
        :type A: int
        :type B: int
        :type C: int
        :type D: int
        :type E: int
        :type F: int
        :type G: int
        :type H: int
        :rtype: int
        """
        return (D - B) * (C - A) + \
               (G - E) * (H - F) - \
               max(0, (min(C, G) - max(A, E))) * \
               max(0, (min(D, H) - max(B, F)))

Run Time: 148 ms

Leetcode 222. Count Complete Tree Nodes

https://leetcode.com/problems/count-complete-tree-nodes/

If use recursion ignoring the feature of completed binary tree, the run time will get TLE.

First we should get the level of this tree. Because the left node will be there first, we can go along the left and gain the level. Then we must decide how many nodes are in this level. This is not very easy, and we can use binary search to find the most right node.

Solution:

# T:O((logn)^2) S:O(1)
class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None: return 0
        
        node, level = root, 0
        while node.left is not None:
            node = node.left
            level += 1
        
        # Binary search.
        left, right = 2 ** level, 2 ** (level + 1)
        while left < right:
            mid = left + (right - left) / 2
            if not self.exist(root, mid):
                right = mid
            else:
                left = mid + 1
                
        return left - 1
    
    # Check if the nth node exist.
    def exist(self, root, n):
        k = 1
        while k <= n:
            k <<= 1
        k >>= 2
        
        node = root
        while k > 0:
            if (n & k) == 0:
                node = node.left
            else:
                node = node.right
            k >>= 1
        return node is not None

Run Time: 188 ms

Leetcode 221. Maximal Square

https://leetcode.com/problems/maximal-square/

DP with sliding window.

Solution:

# T:O(n^2) S:O(n)
class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:
            return 0

        m, n = len(matrix), len(matrix[0])
        size = [[0 for j in xrange(n)] for i in xrange(2)]
        max_size = 0
        
        for j in xrange(n):
            if matrix[0][j] == '1':
                size[0][j] = 1
            max_size = max(max_size, size[0][j])
            
        for i in xrange(1, m):
            if matrix[i][0] == '1':
                size[i % 2][0] = 1
            else:
                size[i % 2][0] = 0
            for j in xrange(1, n):
                if matrix[i][j] == '1':
                    size[i % 2][j] = min(size[i % 2][j - 1], \
                                         size[(i - 1) % 2][j], \
                                         size[(i - 1) % 2][j - 1]) + 1
                    max_size = max(max_size, size[i % 2][j])
                else:
                    size[i % 2][j] = 0
                    
        return max_size * max_size

Run Time: 136 ms

Leetcode 220. Contains Duplicate III

https://leetcode.com/problems/contains-duplicate-iii/

Window and bucket!

if： | nums[i] - nums[j] | <= t
namely： | nums[i] / t - nums[j] / t | <= 1
then： | floor(nums[i] / t) - floor(nums[j] / t) | <= 1
​therefore： floor(nums[j] / t) ∈ {floor(nums[i] / t) - 1, floor(nums[i] / t), floor(nums[i] / t) + 1}

Solution:

# T:O(n*t) S:O(max(k,t))
class Solution:
    # @param {integer[]} nums
    # @param {integer} k
    # @param {integer} t
    # @return {boolean}
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        if k < 0 or t < 0:
            return False
        window = collections.OrderedDict()
        for n in nums:
            # Make sure window size
            if len(window) > k:
                window.popitem(False)
                
            bucket = n if not t else n // t
            # At most 2t items.
            for m in (window.get(bucket - 1), window.get(bucket), window.get(bucket + 1)):
                if m is not None and abs(n - m) <= t:
                    return True
            window[bucket] = n
        return False

Run Time: 144 ms

Leetcode 219. Contains Duplicate II

https://leetcode.com/problems/contains-duplicate-ii/

Solution:

# T:O(n) S:O(n)
class Solution:
    # @param {integer[]} nums
    # @param {integer} k
    # @return {boolean}
    def containsNearbyDuplicate(self, nums, k):
        if k >= len(nums) - 1:
            return len(nums) > len(set(nums))
        for i in xrange(k, len(nums)):
            tmp = nums[i-k:i+1]
            if len(tmp) > len(set(tmp)):
                return True
        else:
            return False

Run Time: 60 ms

Leetcode 218. The Skyline Problem

https://leetcode.com/problems/the-skyline-problem/

This problem is indeed not very easy, while the key point is to keep efficient and care about many cases.

Solution:

# T:O(nlgn) S:O(n)
# Divide and conquer solution.
start, end, height = 0, 1, 2
class Solution:
    # @param {integer[][]} buildings
    # @return {integer[][]}
    def getSkyline(self, buildings):
        intervals = self.ComputeSkylineInInterval(buildings, 0, len(buildings))
        
        res = []
        last_end = -1
        for interval in intervals:
            if last_end != -1 and last_end < interval[start]:
                res.append([last_end, 0])
            res.append([interval[start], interval[height]])
            last_end = interval[end]
        if last_end != -1:
            res.append([last_end, 0])
            
        return res
    
    # Divide and Conquer.
    def ComputeSkylineInInterval(self, buildings, left_endpoint, right_endpoint):
        if right_endpoint - left_endpoint <= 1:
            return buildings[left_endpoint:right_endpoint]
        mid = left_endpoint + ((right_endpoint - left_endpoint) / 2)
        left_skyline = self.ComputeSkylineInInterval(buildings, left_endpoint, mid)
        right_skyline = self.ComputeSkylineInInterval(buildings, mid, right_endpoint)
        return self.MergeSkylines(left_skyline, right_skyline)
    
    # Merge Sort.
    def MergeSkylines(self, left_skyline, right_skyline):
        i, j = 0, 0
        merged = []
        
        while i < len(left_skyline) and j < len(right_skyline):
            if left_skyline[i][end] < right_skyline[j][start]:
                merged.append(left_skyline[i])
                i += 1
            elif right_skyline[j][end] < left_skyline[i][start]:
                merged.append(right_skyline[j])
                j += 1
            elif left_skyline[i][start] <= right_skyline[j][start]:
                i, j = self.MergeIntersectSkylines(merged, left_skyline[i], i,\
                                                   right_skyline[j], j)
            else: # left_skyline[i][start] > right_skyline[j][start].
                j, i = self.MergeIntersectSkylines(merged, right_skyline[j], j, \
                                                   left_skyline[i], i)
        
        # Insert the remaining skylines.
        merged += left_skyline[i:]
        merged += right_skyline[j:]
        return merged
    
    # a[start] <= b[start]
    def MergeIntersectSkylines(self, merged, a, a_idx, b, b_idx):
        if a[end] <= b[end]:
            if a[height] > b[height]:   # |aaa|
                if b[end] != a[end]:    # |abb|b
                    b[start] = a[end]
                    merged.append(a)
                    a_idx += 1
                else:             # aaa
                    b_idx += 1    # abb
            elif a[height] == b[height]:  # abb
                b[start] = a[start]       # abb
                a_idx += 1
            else:  # a[height] < b[height].
                if a[start] != b[start]:                            #    bb
                    merged.append([a[start], b[start], a[height]])  # |a|bb
                a_idx += 1
        else:  # a[end] > b[end].
            if a[height] >= b[height]:  # aaaa
                b_idx += 1              # abba
            else:
                #    |bb|
                # |a||bb|a
                if a[start] != b[start]:
                    merged.append([a[start], b[start], a[height]])
                a[start] = b[end]
                merged.append(b)
                b_idx += 1
        return a_idx, b_idx

Run Time: 148 ms

Leetcode 217. Contains Duplicate

https://leetcode.com/problems/contains-duplicate/

We can use set in Python, which has the feature of getting rid of duplicate automatically.

Solution:

# T:O(n) S:O(n)
class Solution:
    # @param {integer[]} nums
    # @return {boolean}
    def containsDuplicate(self, nums):
        return len(nums) > len(set(nums))

Run Time: 80 ms

Leetcode 216. Combination Sum III

https://leetcode.com/problems/combination-sum-iii/

Nothing but DFS.

Solution:

# T:O(k*C(n,k)) S:O(k)
class Solution:
    # @param {integer} k
    # @param {integer} n
    # @return {integer[][]}
    def combinationSum3(self, k, n):
        result = []
        self.combinationSumRecu(result, [], 1, k, n)
        return result
    
    def combinationSumRecu(self, result, intermediate, start, k, target):
        if k == 0 and target == 0:
            result.append(list(intermediate))
        elif k < 0:
            return
        while start < 10 and start * k + k * (k - 1) / 2 <= target:
            intermediate.append(start)
            self.combinationSumRecu(result, intermediate, start + 1, k - 1, target - start)
            intermediate.pop()
            start += 1

Run Time: 44 ms

Leetcode 215. Kth Largest Element in an Array

https://leetcode.com/problems/kth-largest-element-in-an-array/

The plain thought is to sort, and then give the kth element. Run time of this method is 48 ms. This way is simple and easy. Other ways can achieve better performance while much more complex.

Solution:

# T:O(n) S:O(1)
from random import randint

class Solution:
    # @param {integer[]} nums
    # @param {integer} k
    # @return {integer}
    def findKthLargest(self, nums, k):
        left, right = 0, len(nums) - 1
        while left <= right:
            pivot_idx = randint(left, right)
            new_pivot_idx = self.PartitionAroundPivot(left, right, pivot_idx, nums)
            if new_pivot_idx == k - 1:
                return nums[new_pivot_idx]
            elif new_pivot_idx > k - 1:
                right = new_pivot_idx - 1
            else:  # new_pivot_idx < k - 1.
                left = new_pivot_idx + 1
        
    def PartitionAroundPivot(self, left, right, pivot_idx, nums):
        pivot_value = nums[pivot_idx]
        new_pivot_idx = left
        nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
        for i in xrange(left, right):
            if nums[i] > pivot_value:
                nums[i], nums[new_pivot_idx] =  nums[new_pivot_idx], nums[i]
                new_pivot_idx += 1
            
        nums[right], nums[new_pivot_idx] = nums[new_pivot_idx], nums[right]
        return new_pivot_idx

Run Time: 64 ms

Leetcode 214. Shortest Palindrome

https://leetcode.com/problems/shortest-palindrome/

Using KMP algorithm.

Solution:

# T:O(n) S:O(n)
class Solution:
    # @param {string} s
    # @return {string}
    def shortestPalindrome(self, s):
        if not s:
            return s
            
        A = s + s[::-1]
        prefix = self.getPrefix(A)
        i = prefix[-1]
        while i >= len(s):
            i = prefix[i]
        return s[i+1:][::-1] + s
        
    def getPrefix(self, pattern):
        prefix = [-1] * len(pattern)
        j = -1
        for i in xrange(1, len(pattern)):
            while j > -1 and pattern[j+1] != pattern[i]:
                j = prefix[j]
            if pattern[j+1] == pattern[i]:
                j += 1
            prefix[i] = j
        return prefix

Run Time: 96 ms

Leetcode 213. House Robber II

https://leetcode.com/problems/house-robber-ii/

The majority part is still the same. Actually the difference is clear: if we rob first house, we cannot rob the last house.

Solution:

# T:O(n) S:O(1)
class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def rob(self, nums):
        if len(nums) == 0:
            return 0
            
        if len(nums) == 1:
            return nums[0]
        
        return max(self.robRange(nums, 0, len(nums) - 1),\
                   self.robRange(nums, 1, len(nums)))
    
    def robRange(self, nums, start, end):
        num_i, num_i_1 = nums[start], 0
        for i in xrange(start + 1, end):
            num_i_1, num_i_2 = num_i, num_i_1
            num_i = max(nums[i] + num_i_2, num_i_1);
        
        return num_i

Run Time: 36 ms

Leetcode 212. Word Search II

https://leetcode.com/problems/word-search-ii/

We can use trie to make the problem simple.

Solution:

# T:O(m*n) S:O(1)
class TrieNode:
    # Initialize your data structure here.
    def __init__(self):
        self.is_string = False
        self.leaves = {}

    # Inserts a word into the trie.
    def insert(self, word):
        cur = self
        for c in word:
            if not c in cur.leaves:
                cur.leaves[c] = TrieNode()
            cur = cur.leaves[c]
        cur.is_string = True

class Solution:
    # @param {character[][]} board
    # @param {string[]} words
    # @return {string[]}
    def findWords(self, board, words):
        visited = [[False for j in xrange(len(board[0]))] for i in xrange(len(board))]
        result = {}
        trie = TrieNode()
        for word in words:
            trie.insert(word)
            
        for i in xrange(len(board)):
            for j in xrange(len(board[0])):
                if self.findWordsRecu(board, trie, 0, i, j, visited, [], result):
                    return True
        
        return result.keys()
    
    def findWordsRecu(self, board, trie, cur, i, j, visited, cur_word, result):
        if not trie or i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or visited[i][j]:
            return
        
        if board[i][j] not in trie.leaves:
            return
        
        cur_word.append(board[i][j])
        next_node = trie.leaves[board[i][j]]
        if next_node.is_string:
            result["".join(cur_word)] = True
        
        visited[i][j] = True
        self.findWordsRecu(board, next_node, cur + 1, i + 1, j, visited, cur_word, result)
        self.findWordsRecu(board, next_node, cur + 1, i - 1, j, visited, cur_word, result)
        self.findWordsRecu(board, next_node, cur + 1, i, j + 1, visited, cur_word, result)
        self.findWordsRecu(board, next_node, cur + 1, i, j - 1, visited, cur_word, result)     
        visited[i][j] = False
        cur_word.pop()

Run Time: 840 ms

Leetcode 211. Add and Search Word - Data structure design

https://leetcode.com/problems/add-and-search-word-data-structure-design/

Actually we can do it using the trie data structure that we designed before.

Solution:

# T:O(min(n, h)) S:O(min(n, h))
class TrieNode:
    # Initialize your data structure here.
    def __init__(self):
        self.is_string = False
        self.leaves = {}
        
class WordDictionary:
    def __init__(self):
        self.root = TrieNode()
        
    # @param {string} word
    # @return {void}
    # Adds a word into the data structure.
    def addWord(self, word):
        curr = self.root
        for c in word:
            if not c in curr.leaves:
                curr.leaves[c] = TrieNode()
            curr = curr.leaves[c]
        curr.is_string = True

    # @param {string} word
    # @return {boolean}
    # Returns if the word is in the data structure. A word could
    # contain the dot character '.' to represent any one letter.
    def search(self, word):
        return self.searchHelper(word, 0, self.root)
        
    def searchHelper(self, word, start, curr):
        if start == len(word):
            return curr.is_string
        if word[start] in curr.leaves:
            return self.searchHelper(word, start+1, curr.leaves[word[start]])
        elif word[start] == '.':
            for c in curr.leaves:
                if self.searchHelper(word, start+1, curr.leaves[c]):
                    return True
       
        return False

Run Time: 568 ms

Leetcode 210. Course Schedule II

https://leetcode.com/problems/course-schedule-ii/

Very similar with problem 207.

Solution:

# T:O(|V|+|E|) S:O(|E|)
class Solution:
    # @param {integer} numCourses
    # @param {integer[][]} prerequisites
    # @return {integer[]}
    def findOrder(self, numCourses, prerequisites):
        res, zero_in_degree_queue, in_degree, out_degree =\
[], collections.deque(), {}, {}
        
        for i, j in prerequisites:
            if i not in in_degree:
                in_degree[i] = sets.Set()
            if j not in out_degree:
                out_degree[j] = sets.Set()
            in_degree[i].add(j)
            out_degree[j].add(i)
        
        for i in xrange(numCourses):
            if i not in in_degree:
                zero_in_degree_queue.append(i)
        
        while zero_in_degree_queue:
            prerequisite = zero_in_degree_queue.popleft()
            res.append(prerequisite)
            
            if prerequisite in out_degree:
                for course in out_degree[prerequisite]:
                    in_degree[course].discard(prerequisite)
                    if not in_degree[course]:
                        zero_in_degree_queue.append(course)
            
                del out_degree[prerequisite]
        
        if out_degree:
            return []
        
        return res

Run Time: 112 ms

Leetcode 209. Minimum Size Subarray Sum

https://leetcode.com/problems/minimum-size-subarray-sum/

Rolling window method.

Solution:

# T:O(n) S:O(1)
class Solution:
    # @param {integer} s
    # @param {integer[]} nums
    # @return {integer}
    def minSubArrayLen(self, s, nums):
        start, sum, mid_len = 0, 0, float("inf")
        for i in xrange(len(nums)):
            sum += nums[i]
            while sum >= s:
                min_len = min(min_len, i - start + 1)
                sum -= nums[start]
                start += 1
        if min_len == float("inf"):
            return 0
        return min_len

Run Time: 88 ms

Leetcode 208. Implement Trie (Prefix Tree)

https://leetcode.com/problems/implement-trie-prefix-tree/

Solution:

# T:O(n) S:O(1)
class TrieNode:
    # Initialize your data structure here.
    def __init__(self):
        self.is_string = False
        self.leaves = {}
        

class Trie:

    def __init__(self):
        self.root = TrieNode()

    # @param {string} word
    # @return {void}
    # Inserts a word into the trie.
    def insert(self, word):
        cur = self.root
        for c in word:
            if not c in cur.leaves:
                cur.leaves[c] = TrieNode()
            cur = cur.leaves[c]
        cur.is_string = True

    # @param {string} word
    # @return {boolean}
    # Returns if the word is in the trie.
    def search(self, word):
        res, node = self.childSearch(word)
        if res:
            return node.is_string
        return False        

    # @param {string} prefix
    # @return {boolean}
    # Returns if there is any word in the trie
    # that starts with the given prefix.
    def startsWith(self, prefix):
        return self.childSearch(prefix)[0]

    def childSearch(self, word):
        cur = self.root
        for c in word:
            if c in cur.leaves:
                cur = cur.leaves[c]
            else:
                return False, None
        return True, cur

Run Time: 348 ms

Leetcode 207. Course Schedule

https://leetcode.com/problems/course-schedule/

We can do it using graph.

Solution:

# T:O(|V|+|E|) S:O(|E|)
class Solution:
    # @param {integer} numCourses
    # @param {integer[][]} prerequisites
    # @return {boolean}
    def canFinish(self, numCourses, prerequisites):
        zero_in_degree_queue, in_degree, out_degree = collections.deque(), {}, {}
        
        for i, j in prerequisites:
            if i not in in_degree:
                in_degree[i] = sets.Set()
            if j not in out_degree:
                out_degree[j] = sets.Set()
            in_degree[i].add(j)
            out_degree[j].add(i)
        
        for i in xrange(numCourses):
            if i not in in_degree:
                zero_in_degree_queue.append(i)
        
        while zero_in_degree_queue:
            prerequisite = zero_in_degree_queue.popleft()
            
            if prerequisite in out_degree:
                for course in out_degree[prerequisite]:
                    in_degree[course].discard(prerequisite)
                    if not in_degree[course]:
                        zero_in_degree_queue.append(course)
            
                del out_degree[prerequisite]
        
        if out_degree:
            return False
        
        return True

Run Time: 108 ms

Leetcode 206. Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/

Solution:

# T:O(n) S:O(1)
class Solution:
    # @param {ListNode} head
    # @return {ListNode}
    def reverseList(self, head):
        dummy = ListNode(float("-inf"))
        while head:
            dummy.next, head.next, head = head, dummy.next, head.next
        return dummy.next

Run Time: 60 ms

Leetcode 205. Isomorphic Strings

https://leetcode.com/problems/isomorphic-strings/

This is a thing of mapping. On each occurrence, record the mapping. If one char maps to two chars, False; or two chars map to the same char, False.

Solution:

# T:O(n) S:O(1) At most 26 mappings
class Solution:
    # @param {string} s
    # @param {string} t
    # @return {boolean}
    def isIsomorphic(self, s, t):
        length, dict = len(s), {}
        for i in xrange(length):
            if s[i] not in dict:
                if t[i] in dict.values():
                    return False
                dict[s[i]] = t[i]
            else:
                if dict[s[i]] != t[i]:
                    return False
        return True

Run Time: 64 ms

Leetcode 204. Count Primes

https://leetcode.com/problems/count-primes/

Brute force is not acceptable. The solution is really smart, while there are still spaces to improve.

Solution:

# T:O(n) S:O(n)
class Solution:
    # @param {integer} n
    # @return {integer}
    def countPrimes(self, n):
        if n <= 2:
            return 0
        
        is_prime = [True] * n
        
        num = 0
        for i in xrange(2, n):
            if is_prime[i]:
               num += 1
               for j in xrange(i+i, n, i):
                   is_prime[j] = False
                   
        return num

Run Time: 804 ms

Leetcode 203. Remove Linked List Elements

https://leetcode.com/problems/remove-linked-list-elements/

Solution:

# T:O(n) S:O(1)
class Solution:
    # @param {ListNode} head
    # @param {integer} val
    # @return {ListNode}
    def removeElements(self, head, val):
        dummy = ListNode(float("-inf"))
        dummy.next = head
        prev, curr = dummy, dummy.next
        
        while curr:
            if curr.val == val:
                prev.next = curr.next
            else:
                prev = curr
            
            curr = curr.next
        
        return dummy.next

Run Time: 128 ms

Leetcode 202. Happy Number

https://leetcode.com/problems/happy-number/

Easy problem. Just use some recursion.

Solution:

# T:O(k) S:O(k)
class Solution:
    # @param {integer} n
    # @return {boolean}
    def perform(self, n):
        ret = 0
        while n:
            ret += (n%10)**2
            n /= 10
        return ret
        
    def isHappy(self, n):
        lst = []
        while True:
            if self.perform(n) == 1:
                return True
            if n not in lst:
                lst.append(n)
            n = self.perform(n)
            if n in lst:
                return False

Run Time: 48 ms

Leetcode 201. Bitwise AND of Numbers Range

https://leetcode.com/problems/bitwise-and-of-numbers-range/

Bit operation. The key is to find common part from left side.

Solution:

# T:O(1) S:O(1)
class Solution:
    # @param m, an integer
    # @param n, an integer
    # @return an integer
    def rangeBitwiseAnd(self, m, n):
        i, diff = 0, n-m
        while diff:
            diff >>= 1
            i += 1
        return n&m >> i << i

Run Time: 196 ms

Leetcode 200. Number of Islands

https://leetcode.com/problems/number-of-islands/

The thought is to search for four directions. Note not to search repeatedly.

Solution:

# T:O(m*n) S:O(m*n)
class Solution:
    # @param {boolean[][]} grid a boolean 2D matrix
    # @return {int} an integer
    def numIslands(self, grid):
        if not grid:
            return 0
    
        row = len(grid)
        col = len(grid[0])
        used = [[False for j in xrange(col)] for i in xrange(row)]
    
        count = 0
        for i in xrange(row):
            for j in xrange(col):
                if grid[i][j] == '1' and not used[i][j]:
                    self.dfs(grid, used, row, col, i, j)
                    count += 1
        return count

    def dfs(self, grid, used, row, col, x, y):
        if grid[x][y] == '0' or used[x][y]:
            return
        used[x][y] = True
    
        if x != 0:
            self.dfs(grid, used, row, col, x - 1, y)
        if x != row - 1:
            self.dfs(grid, used, row, col, x + 1, y)
        if y != 0:
            self.dfs(grid, used, row, col, x, y - 1)
        if y != col - 1:
            self.dfs(grid, used, row, col, x, y + 1)

Run Time: 136 ms

Leetcode 199. Binary Tree Right Side View

https://leetcode.com/problems/binary-tree-right-side-view/

The lazy way is to get level order and use the right most element, while it is wasteful. We can do better than that. The key is to put right nodes in if exist.

Solution:

# T:O(n) S:O(h)
class Solution:
    # @param root, a tree node
    # @return a list of integers
    def rightSideView(self, root):
        result = []
        self.rightSideViewDFS(root, 1, result)
        return result
    
    def rightSideViewDFS(self, node, depth, result):
        if not node:
            return
        
        if depth > len(result):
            result.append(node.val)
        
        self.rightSideViewDFS(node.right, depth+1, result)
        self.rightSideViewDFS(node.left, depth+1, result)

Run Time: 60 ms

Leetcode 198. House Robber

https://leetcode.com/problems/house-robber/

Using DP. The key is to get the right formula.

Solution:

# T:O(n) S:O(1)
class Solution:
    # @param num, a list of integer
    # @return an integer
    def rob(self, num):
        if len(num) == 0:
            return 0
            
        if len(num) == 1:
            return num[0]
        
        num_i, num_i_1 = max(num[1], num[0]), num[0]
        for i in xrange(2, len(num)):
            num_i_1, num_i_2 = num_i, num_i_1
            num_i = max(num[i] + num_i_2, num_i_1);
        
        return num_i

Run Time: 36 ms

Leetcode 191. Number of 1 Bits

https://leetcode.com/problems/number-of-1-bits/

Two solutions.

Solution 1:

# T:O(m) S:O(1)
class Solution:
    # @param n, an integer
    # @return an integer
    def hammingWeight(self, n):
        result = 0
        while n:
            n &= n - 1
            result += 1
        return result

Run Time: 56 ms

Solution 2:

# T:O(m) S:O(m)
class Solution:
    # @param n, an integer
    # @return an integer
    def hammingWeight(self, n):
        s = bin(n)[2:]
        cnt = 0
        for ch in s:
            if ch == '1':
                cnt += 1
        return cnt

Run Time: 48 ms

Leetcode 190. Reverse Bits

https://leetcode.com/problems/reverse-bits/

Two solutions. String one and bit operation one.

Solution 1:

# T:O(n) S:O(1)
class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        s = bin(n)
        s = s[2:]
        length = len(s)
        zeros = 32 - len(s)
        s = '0'*zeros + s
        s = s[::-1]
        return int(s,2)

Run Time: 56 ms

Solution 2:

# T:O(n) S:O(1)
class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        result = 0
        for i in xrange(32):
            result <<= 1
            result |= n & 1
            n >>= 1
        return result

Run Time: 60 ms

Leetcode 189. Rotate Array

https://leetcode.com/problems/rotate-array/

Many ways to solve it.

Solution:

# T:O(n) S:O(1)
class Solution:
    # @param nums, a list of integer
    # @param k, num of steps
    # @return nothing, please modify the nums list in-place.
    def rotate(self, nums, k):
        k %= len(nums)
        self.reverse(nums, 0, len(nums))
        self.reverse(nums, 0, k)
        self.reverse(nums, k, len(nums))
    
    def reverse(self, nums, start, end):
        while start < end:
            nums[start], nums[end-1] = nums[end-1], nums[start]
            start += 1
            end -= 1

Run Time: 88 ms

Leetcode 188. Best Time to Buy and Sell Stock IV

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

Here comes the boss. DP for sure. If k is large enough, the whole prices can be covered, which is similar with ii; otherwise the solution is the same principle with iii.

Solution:

# T:O(k*n) S:O(k)
class Solution:
    # @return an integer as the maximum profit 
    def maxProfit(self, k, prices):
        if k >= len(prices) / 2:
            return self.maxAtMostNPairsProfit(prices)

        return self.maxAtMostKPairsProfit(prices, k)

    def maxAtMostNPairsProfit(self, prices):
        profit = 0
        for i in xrange(len(prices) - 1):
            profit += max(0, prices[i + 1] - prices[i])     
        return profit

    def maxAtMostKPairsProfit(self, prices, k):
        max_buy = [float("-inf") for _ in xrange(k + 1)]
        max_sell = [0 for _ in xrange(k + 1)]

        for i in xrange(len(prices)):
            for j in xrange(1, min(k, i/2+1) + 1):
                max_buy[j] = max(max_buy[j], max_sell[j-1] - prices[i])
                max_sell[j] = max(max_sell[j], max_buy[j] + prices[i])

        return max_sell[k]

Run Time: 128 ms

Leetcode 187. Repeated DNA Sequences

https://leetcode.com/problems/repeated-dna-sequences/

Hash table is a clear solution. We can use advanced rolling hash, or just the easiest one.

Solution:

# T:O(n) S:O(n)
class Solution:
    # @param {string} s
    # @return {string[]}
    def findRepeatedDnaSequences(self, s):
        length = len(s)
        if length <= 10: return []
        dict, ret = {}, []
        for i in xrange(10, length+1):
            if s[i-10 : i] in dict:
                dict[s[i-10:i]] += 1
                if s[i-10:i] not in ret:
                    ret.append(s[i-10:i])
            else:
                dict[s[i-10:i]] = 1
        return ret

Run Time: 124 ms