Trie

Algorithms
tree

Trie from the word Retrieve

  • A data structure, it is a tree and a search tree.

Introduction

Search Trees

  • Usually ordered data structure
  • search for some kind of “keys”

Example of Search Tree we are already very familiar: Binary Search Tree

  • the keys are associsated with each node in the tree
  • the keys can be any comparable type
  • main the order of the keys by topological property(leftsubtree < root < rightsubtree)

Design a Dictionary

n - # of words
m - length of the string/word

  1. What is the requirement of this dictionary?
  • search(word)
  • delete
  • add
  • find all words with give prefix
  1. Options of data structures
  • Hash Map
  • Balanced BST
  • ArrayList(sorted)

Time

  • Looking up data in a trie is faster in the worst case, O(m) time (where m is the length of a search string)
  • hashmap, remember we may need to calculate the hashCode() and compare eaquals, that is O(m).
  • Array List (sorted) - O(logn) * O(m)
  • Binary Search Tree - O(logn) * O(m)

DrawBack: if stored on disk, more random disk accesses (very expensive)

Space

  • if the tire is not too sparse, since reusing the common prefix as many as possible, less space required. worst case O(nm), but usually much better than this.

DrawBack:

  1. Every TrieNode has extra space comsumption -> extra space usage
  2. memory allocation fragmentation, especially when the trie is sparse.

Use Case

  • String or sequence typed elements
  • fast worst search/add/delete
  • grouping common prefix, both for time/space efficency
  • problems related to prefix/matching

208. Implement Trie (Prefix Tree)

  • Node <val, children>
    TODO: delete!!!!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Node(object):
    def __init__(self, val):
        self.val = val
        self.children = {}
        # self.parent = None ?
        # self.isWord = False ?

class Trie:

    def __init__(self):
        self.root = Node(-1)

    def insert(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                cur.children[ch] = Node(ch)
            cur = cur.children[ch]
        cur.children['#'] = True

    def search(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        return '#' in cur.children

    def startsWith(self, prefix):
        cur = self.root
        for ch in prefix:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        return True

211. Add and Search Word - Data structure design

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class TrieNode(object):
    def __init__(self, val):
        self.val = val
        self.children = {}
        self.isWord = False

class WordDictionary:

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

    def addWord(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                cur.children[ch] = TrieNode(ch)
            cur = cur.children[ch]
        cur.isWord = True

    def search(self, word):
        return self.exist(word, self.root)

    def exist(self, word, root):
        if len(word) == 0:
            return root.isWord

        cur = root
        ch = word[0]
        if ch == '.':
            for nxt in cur.children.keys():
                if self.exist(word[1:], cur.children[nxt]):
                    return True
            return False
        else:
            if ch not in cur.children:
                return False
            return self.exist(word[1:], cur.children[ch])
Share

DP - Game

Algorithms
dfs, dp

DFS + Memorization

464. Can I Win

  • DFS + Memorization + Pruning
  • If there exist one way that the other one will NOT win, then I win!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def canIWin(self, maxChoosableInteger, desiredTotal):
        if maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal:
            return False
        self.memo = {}
        return self.helper(list(range(1, maxChoosableInteger + 1)), desiredTotal)

    def helper(self, nums, desiredTotal):
        key = tuple(nums)
        if key in self.memo:
            return self.memo[key]

        if nums[-1] >= desiredTotal:
            return True

        for i in range(len(nums)):
            if not self.helper(nums[:i]+nums[i+1:], desiredTotal-nums[i]):
                self.memo[key] = True
                return True

        self.memo[key] = False
        return False

293. Flip Game

1
2
3
4
5
6
7
class Solution:
    def generatePossibleNextMoves(self, s):
        res = []
        for i in range(len(s)-1):
            if s[i] == '+' and s[i+1] == '+':
                res.append(s[:i] + "-" + "-" + s[i+2:])
        return res

294. Flip Game II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def canWin(self, s):
        self.memo = {}
        return self.win(s)

    def win(self, s):
        if s in self.memo:
            return self.memo[s]

        for i in range(len(s)-1):
            if s[i] == '+' and s[i+1] == '+':
                news = s[:i] + "-" + "-" + s[i+2:]
                if not self.win(news):
                    self.memo[s] = True
                    return True

        self.memo[s] = False
        return False

DP

LintCode 394. Coins in a Line

Solution1. DFS + Memorization

  • TLE
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution:
        def firstWillWin(self, n):
            self.memo = {}
            return self.helper(n)

        def helper(self, n):
            if n <= 2:
                return True

            if n in self.memo:
                return self.memo[n]

            if not self.firstWillWin(n-1) or not self.firstWillWin(n-2):
                self.memo[n] = True
                return True

            self.memo[n] = False
            return False

Solution2. DP

  • Time : O(n), Space : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def firstWillWin(self, n):
        if n == 0:
            return False

        if n <= 2:
            return True

        dp = [False] * (n+1)
        dp[1] = dp[2] = True
        for i in range(3, n+1):
            dp[i] = not dp[i-1] or not dp[i-2]
        return dp[n]

Solution3. Math

1
2
3
class Solution:
    def firstWillWin(self, n):
        return bool(n % 3)

LintCode 395. Coins in a Line II

  • dp[i], preSum[i]-dp[i] represent how many i get and how many other one get!!!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def firstWillWin(self, values):
        n = len(values)
        if n <= 2:
            return True

        values.reverse()
        psum = self.preSum(values)

        dp = [0] * n
        dp[0] = psum[0]
        dp[1] = psum[1]
        for i in range(2, n):
            dp[i] = max(psum[i] - dp[i-1], psum[i] - dp[i-2])
        return dp[n-1] > psum[n-1] - dp[n-1]

    def preSum(self, values):
        psum = [values[0]]
        for i in range(1, len(values)):
            psum.append(psum[-1] + values[i])
        return psum

LintCode 396. Coins in a Line III

TODO!!!

Follow up

DP[i][j] represents from i-th coin to the j-th coin, the largest sum of pizza that i can pick.

  • case1 : if i take the left coin,
  1. if input[i+1] < input[j], input[i] + DP[i+1][j-1]
  2. if input[i+1] > input[j], input[i] + DP[i+2][j]
  • case2 : if i take the right coin,
  1. if input[i] < input[j-1], input[j] + DP[i][j-2]
  2. if input[i] > input[j-1], input[j] + DP[i+1][j-1]
  • Base Case:
  1. 2 coins, DP[i][i+1] = max(input[i], input[i+1])
  2. 1 coin, DP[i][i] = input[i]

Coin Game

Let us understand the problem with few examples:

  1. 5, 3, 7, 10 : The user collects maximum value as 15(10 + 5)
  2. 8, 15, 3, 7 : The user collects maximum value as 22(7 + 15)
    Does choosing the best at each move give an optimal solution?
  • F(i, j) represents the maximum value the user can collect from i’th coin to j’th coin.
  1. If I take Ai, Vi + min(F(i+2, j), F(i+1, j-1)
  2. If I take Ak, Vj + min(F(i+1, j-1), F(i, j-2)
    $$F(i, j) = Max(Vi + min(F(i+2, j), F(i+1, j-1) ), Vj + min(F(i+1, j-1), F(i, j-2) ))$$
  • Base Cases
  1. F(i, j) = Vi If j == i
  2. F(i, j) = max(Vi, Vj) If j == i+1
Share

Data Stream

Algorithms
heap, queue, topic

Data Stream

703. Kth Largest Element in a Stream

  • heap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class KthLargest(object):

    def __init__(self, k, nums):
        self.size = k
        heapq.heapify(nums)
        self.heap = nums
        while len(self.heap) > k:
            heapq.heappop(self.heap)

    # Time : O(log k), Space : O(k)
    def add(self, val):
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.size:
            heapq.heappop(self.heap)
        return self.heap[0]

346. Moving Average from Data Stream

  • sliding window : deque - double queue
1
2
3
4
5
6
7
8
9
10
11
12
13
class MovingAverage(object):

    def __init__(self, size):
        self.sum = 0
        self.size = size
        self.queue = collections.deque()

    def next(self, val):
        self.queue.append(val)
        self.sum += val
        if len(self.queue) > self.size:
            self.sum -= self.queue.popleft()
        return self.sum / (1.0 * len(self.queue))

295. Find Median from Data Stream

  • min Heap, max Heap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class MedianFinder(object):

    def __init__(self):
        self.maxHeap = []
        self.minHeap = []

    def addNum(self, num):
        heapq.heappush(self.maxHeap, -num)
        heapq.heappush(self.minHeap, -heapq.heappop(self.maxHeap))
        m1, m2 = len(self.maxHeap), len(self.minHeap)
        if m1 < m2:
            heapq.heappush(self.maxHeap, -heapq.heappop(self.minHeap))

    def findMedian(self):
        m1, m2 = len(self.maxHeap), len(self.minHeap)
        if m1 == m2:
            return (self.minHeap[0] - self.maxHeap[0]) / 2.0
        else:
            return -self.maxHeap[0] * 1.0
  • follow up : what if the number of element is toooo large to be stored into the memory?

Find the first non-repeating character from a Stream

Use Case:

  1. We need to somehow record which one is the First (order)
    When a new element comes in
  • we found that previous solution is now not the solution any more, we need to update the solution to the next one.(Use a doubl linked list)
  1. We also need to record what kind of letters that have appeared (non-repeating)
  • Hash Map <key:character, val:Node>

(Same with LRU!!!)

Sliding Window

Slinding Window Average

  • Time : O(1), Space :(window size)
  • Queue to maintain the window
  • variable sum to record sum , update O(1)

239. Sliding Window Maximum

total data - n, window size - k

Solution1. Naive

Time : O((n-k)k), (O(k) for online data stream)

Solution2. Heap

Time : O((n-k)logk)

  1. Initialization:insert all first k elements into the max-heap.
  2. Then: when the sliding window moves to the right side step by step
    1 new element comes in.
    1 left-most element should be removed from the sliding window. bu we can temoporarily keep it in the heap, until it becomes the top element in the heap. lazy deletion
    (value, index)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def maxSlidingWindow(self, nums, k):
        if not nums or k == 0:
            return []

        maxHeap = []
        for i in xrange(k-1):
            heapq.heappush(maxHeap, (-nums[i], i))

        res = []
        for i in xrange(k-1, len(nums)):
            heapq.heappush(maxHeap, (-nums[i], i))
            while maxHeap[0][1] <= i-k:
                heapq.heappop(maxHeap)
            res.append(-maxHeap[0][0])
        return res
  • When we want to call max_heap.top(), the only thing we should be careful about is to check, whether this top elemtns’s index is < left border of the sliding window. If so, keep poping it out.

Solution3. Deque

Time : O(n)

  • We must maintain all the values in the dequeue to keep them in a descending order.
  • because when a new element X comes in, if it is bigger and newer than the right most element r, then r cannot be the solution. whatsoever, we can just delete r
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def maxSlidingWindow(self, nums, k):
        queue = collections.deque()
        res = []
        for i, num in enumerate(nums):
            if queue and queue[0] <= i-k:
                queue.popleft()

            while queue and num > nums[queue[-1]]:
                queue.pop()

            queue.append(i)
            if i >= k - 1:
                res.append(nums[queue[0]])
        return res
  • So the dequeue[left-most] is the final result to return whenever the window slides one step to the right.

480. Sliding Window Median

  • double heap + lazy clear
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution(object):
    def medianSlidingWindow(self, nums, k):
        if k == 1:
            return map(float, nums)

        minHeap, maxHeap = [], []
        for i in xrange(k):
            heapq.heappush(maxHeap, (-nums[i], i))

        for _ in xrange(k/2):
            val, idx = heapq.heappop(maxHeap)
            heapq.heappush(minHeap, (-val, idx))

        res = []
        for i in xrange(k, len(nums)):
            res.append(-maxHeap[0][0]*1.0 if k % 2 else (minHeap[0][0]-maxHeap[0][0])/2.0)

            if nums[i] >= minHeap[0][0]:
                heapq.heappush(minHeap, (nums[i], i))
                if nums[i-k] <= -maxHeap[0][0]:
                    val, idx = heapq.heappop(minHeap)
                    heapq.heappush(maxHeap, (-val, idx))
            else:
                heapq.heappush(maxHeap, (-nums[i], i))
                if nums[i-k] >= minHeap[0][0]:
                    val, idx = heapq.heappop(maxHeap)
                    heapq.heappush(minHeap, (-val, idx))

            while maxHeap[0][1] <= i-k:
                heapq.heappop(maxHeap)
            while minHeap[0][1] <= i-k:
                heapq.heappop(minHeap)
        res.append(-maxHeap[0][0]*1.0 if k % 2 else (minHeap[0][0]-maxHeap[0][0])/2.0)
        return res
Share

Math

750. Number Of Corner Rectangles

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def countCornerRectangles(self, grid):
        m, n = len(grid), len(grid[0])
        res = 0
        corner = []
        for i in range(m):
            layer = {j for j in range(n) if grid[i][j] == 1}
            for prev in corner:
                cnt = len(layer & prev)
                res += cnt * (cnt - 1) // 2
            corner.append(layer)
        return res

836. Rectangle Overlap

1
2
3
4
5
class Solution(object):
    def isRectangleOverlap(self, rec1, rec2):
        x1, y1, x2, y2 = rec1
        x3, y3, x4, y4 = rec2
        return x2 > x3 and x1 < x4 and y2 > y3 and y1 < y4

Prime Number

A prime number (or a prime) is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.

is Prime

1
2
3
4
5
6
7
def isPrime(m):
    i = 2
    while(i*i <= m):
        if m % i == 0:
            return False
        i += 1
    return True

204. Count Primes

  • Time : O(n)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution:
        def countPrimes(self, n):
            if n <= 2:
                return 0

            primes = [True] * n
            primes[0] = primes[1] = False
            for i in range(2, int(n**0.5)+1):
                if not primes[i]:
                    continue
                k = 2
                while i * k < n:
                    primes[i * k] = False
                    k += 1
            return sum(primes)
Share

Boyer-Moore Voting Algorithm

Algorithms
topic

169. Majority Element

Solution1. Hash Table

  • Time : O(n), Space : O(n)
    1
    2
    3
    4
    5
    6
    7
    8
    class Solution(object):
        def majorityElement(self, nums):
            n = len(nums)
            dic = collections.defaultdict(int)
            for num in nums:
                dic[num] += 1
                if dic[num] > n/2:
                    return num

Solution2. Voting Algorithm

  • Time : O(n), Space :O(1)
  1. Maintain a pair candidate, counter
  2. When a new element x comes in,
  • if counter == 0, just set candidate = x, counter = 1
  • else if x == candidate, counter ++ else counter –
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution(object):
        def majorityElement(self, nums):
            candidate = None
            counter = 0

            for num in nums:
                if counter == 0:
                    candidate = num
                    counter = 1
                else:
                    counter += 1 if candidate == num else -1
            return candidate

229. Majority Element II

Solution1. Hash table

Time : O(n), Space : O(n)

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def majorityElement(self, nums):
        n = len(nums)
        dic = collections.defaultdict(int)
        res = set()
        for num in nums:
            dic[num] += 1
            if dic[num] > n / 3:
                res.add(num)
        return list(res)

Solution2. Voting Algorithm

  • Time : O(n), Space : O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def majorityElement(self, nums):
        if not nums:
            return []
        n = len(nums)
        can1, can2 = 0, 1
        cnt1, cnt2 = 0, 0
        for num in nums:
            if can1 == num:
                cnt1 += 1
            elif can2 == num:
                cnt2 += 1
            else:
                if cnt1 == 0:
                    cnt1, can1 = 1, num
                elif cnt2 == 0:
                    cnt2, can2 = 1, num
                else:
                    cnt1 -= 1
                    cnt2 -= 1

        return [can for can in [can1,can2] if nums.count(can) > n // 3]

Majority Element III

duplicates > [1/k], we need k-1 candidates, so the space complexity is O(k)

Majority Element IV

  • what if the input in sorted, you wanna find the majority number appears n / 4 times!

277. Find the Celebrity

Solution1. Divede and Conquer O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):
    def findCelebrity(self, n):
        if n <= 1: return n

        cand = self.find_cands(range(n))
        for i in range(n):
            if i == cand:
                continue

            if knows(cand, i):
                return -1

            if not knows(i, cand):
                return -1
        return cand

    def find_cands(self, nums):
        n = len(nums)
        # Base Case
        if n == 1:
            return nums[0]

        if n == 2:
            if knows(nums[0], nums[1]):
                return nums[1]
            else:
                return nums[0]

        p1 = self.find_cands(nums[:n//2+1])
        p2 = self.find_cands(nums[n//2+1:])

        return p2 if knows(p1, p2) else p1

Solution2. Voting O(n)

  • Something like the Voting algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def findCelebrity(self, n):
        if n <= 1:
            return n

        cand = 0
        for i in range(1, n):
            if knows(cand, i):
                cand = i

        if any(knows(cand, i) for i in range(cand)):
            return -1

        if any(not knows(i, cand) for i in range(n)):
            return -1

        return cand
Share

Cache

Design
hash table, linked list, topic

Design + Operatin System + Data Structure

OrderedDict

An OrderedDict is a dict that remembers the order that keys were first inserted.

1
2
3
4
cache = collections.OrderedDict()
cache.popitem(last=True)
# The popitem() method for ordered dictionaries returns and removes a (key, value) pair.
# The pairs are returned in LIFO order if last is true or FIFO order if false.

146. LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache.

  1. we need to be able to add an entry to the cache and delete the oldest entry from the cache.(including when the cache is full)
  2. we need to find out quickly whether an entry is in the cache or not.
  • hash map :
  1. we need to adjust the priority efficiently of each entry in the cache.
  • double linked list or singly linked list node

Solution1. Built-In

  • python built-in datastructure OrderedDict!!! record the order when they put in the dictionary
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class LRUCache(object):

    def __init__(self, capacity):
        self.cap = capacity
        self.cache = collections.OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        val = self.cache.pop(key)
        self.cache[key] = val
        return val


    def put(self, key, value):
        if key in self.cache:
            self.cache.pop(key)
            self.cache[key] = value
        else:
            if len(self.cache) >= self.cap:
                self.cache.popitem(last=False)
            self.cache[key] = value

Solution2. Doublely Linked List + Hash map

  • Key Point
  1. DummyNode, head and tail
  2. helper function, remove and addHead
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Node(object):
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.cap = capacity
        self.cache = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _addHead(self, node):
        nxt = self.head.next
        self.head.next = node
        node.prev = self.head
        node.next = nxt
        nxt.prev = node

    def _remove(self, node):
        prev = node.prev
        nxt = node.next
        prev.next = nxt
        nxt.prev = prev

    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._addHead(node)
        self.cache[key] = node
        return node.val

    def put(self, key, value):
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._remove(node)
            self._addHead(node)
        else:
            if len(self.cache) >= self.cap:
                lastKey = self.tail.prev.key
                self._remove(self.tail.prev)
                del self.cache[lastKey]
            node = Node(key, value)
            self.cache[key] = node
            self._addHead(node)

460. LFU Cache

TODO!!!

Share

K Sum

Algorithms
sort
  • Assumption
  1. unsorted or sorted
  2. return index ? or value ?
  3. duplicate ?
  4. size, data type, data range ?
  5. optimize time or space ?
  6. How many time are we going to call this function?

2 Sum

$O(n^2)$

###1.Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

  • HashTable
    1
    2
    3
    4
    5
    6
    7
    8
    9
    # Time : O(n), Space : O(n)
    class Solution(object):
        def twoSum(self, nums, target):
            coml = {}
            for i in xrange(len(nums)):
                c = target-nums[i]
                if c in coml:
                    return [coml[c], i]
                coml[nums[i]] = i
  • Why not Sort + Two Pointers ?
    • after sort, lost the information of indices
    • return indice instead of values

167. Two Sum II - Input array is sorted

  • Not Zero-Based Index
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution(object):
        def twoSum(self, nums, target):
            l = 0
            r = len(nums) - 1
            while l < r:
                s = nums[l] + nums[r]
                if s > target:
                    r -= 1
                elif s < target:
                    l += 1
                else:
                    return [l+1, r+1]

170. Two Sum III - Data structure design

  1. HashTable, consider duplicates
  2. Trade Off, quick add or quick find ?
1
2
3
4
5
6
7
8
9
10
11
12
13
class TwoSum(object):

    def __init__(self):
        self.nums = collections.defaultdict(int)

    def add(self, number):
        self.nums[number] += 1

    def find(self, value):
        for num in self.nums.keys():
            if value - num in self.nums and (value - num != num or self.nums[num] > 1):
                return True
        return False

653. Two Sum IV - Input is a BST

  • This is a general idea for binary tree instead of BST!!!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def findTarget(self, root, k):
        self.visited = set()
        return self.dfs(root, k)

    def dfs(self, root, k):
        if not root:
            return False

        if self.dfs(root.left, k):
            return True

        if k - root.val in self.visited:
            return True
        self.visited.add(root.val)

        if self.dfs(root.right, k):
            return True

        return False

3 Sum

$O(n^3)$

15. 3Sum

  • only one results ? no
  • duplicates ? yes
  • The solution set must not contain duplicate triplets.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def threeSum(self, nums):
        nums.sort()
        res = []
        for i in xrange(len(nums)-2):
            # Skip Duplicate nums at 1st place
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l = i + 1
            r = len(nums)-1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s > 0:
                    r -= 1
                elif s < 0:
                    l += 1
                else:
                    res.append([nums[i], nums[l], nums[r]])
                    # Remove Dupilcate Results
                    while l < r and nums[l] == nums[l+1]:
                        l += 1
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    # Forget to add following 2 lines =.=
                    l += 1
                    r -= 1
        return res

16. 3Sum Closest

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def threeSumClosest(self, nums, target):
        res = float('inf')
        nums.sort()
        for i in xrange(len(nums)-2):
            l = i + 1
            r = len(nums) - 1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                # only append this line
                if abs(s - target) < abs(res - target):
                    res = s
                if s > target:
                    r -= 1
                elif s < target:
                    l += 1
                else:
                    return target
        return res

4 Sum

$O(n^4)$

Share

Directed Graph

Algorithms
graph

399. Evaluate Division

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def calcEquation(self, equations, values, queries):
        graph = collections.defaultdict(dict)
        n = len(equations)
        for i in range(n):
            src, dst = equations[i]
            graph[src][dst] = values[i]
            graph[dst][src] = 1.0 / values[i]

        ans = []
        for start, end in queries:
            self.res = -1.0
            self.dfs(start, end, set(), 1.0, graph)
            ans.append(self.res)
        return ans

    def dfs(self, start, end, visited, path, graph):
        if start == end and start in graph:
            self.res = path
            return

        if start in visited:
            return

        visited.add(start)

        for nei in graph[start].keys():
            self.dfs(nei, end, visited, path*graph[start][nei], graph)

Time Analysis

  • Construct the Graph O(Edges), numbers of equations
  • Query, O(Edges)

Follow up

  1. Follow up1: if there are different path from start node to end node ?
  • calcaulate the lowest and highest exchange rate
  1. Follow up2: if we have many queries, how to speed up queries?
  • use hash table to save the results
  • add connected line in the graph!

332. Reconstruct Itinerary

  • DFS post order traversal!
  • a little like topological sort, but different dependency!!!
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def findItinerary(self, tickets):
        graph = collections.defaultdict(list)
        for f, t in sorted(tickets, reverse = True):
            graph[f].append(t)

        res = []
        def dfs(node):
            while graph[node]:
                dfs(graph[node].pop())
            res.append(node)
        dfs('JFK')
        return res[::-1]
Share

DP - Cut Sequence

Algorithms
dp

Analysis

Question Type

  • Seperate an sequence to several nonoverlapping subarray
  • no limit or limited k on the number of the subarray
  • Each subarray meet or meet some requirement!

Solution Type

  • Normally, dp[i][j]represents previous i elements seperate k subarray

Split Array

410. Split Array Largest Sum

Solution1. DP

  • DP[i][j] represents that the largest sum for previous i elements seperated to j group
  • DP[i][j] = min{max{dp[k][j-1], sum(k+1, i)}} ($0<= k <i$)
  • Time : O($mn^2$), Space : O(mn)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution:
        def splitArray(self, nums, m):
            n = len(nums)
            # Prefix Sum
            preSum = [0]
            for i in range(n):
                preSum.append(preSum[-1] + nums[i])

            dp = [[float('inf')] * m for _ in range(n+1)]

            # Init
            dp[0][0] = 0
            for i in range(n+1):
                dp[i][0] = preSum[i]
            for j in range(m):
                dp[0][j] = 0

            # DP
            for i in range(1, n+1):
                for j in range(i):
                    for k in range(1, m):
                        dp[i][k] = min(dp[i][k], max(dp[j][k-1], preSum[i]-preSum[j]))
            return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def splitArray(self, nums, m):
        start, end = max(nums), sum(nums)
        while start < end:
            mid = start + (end - start) // 2
            if self.isValid(mid, nums, m):
                end = mid
            else:
                start = mid + 1
        return start

    def isValid(self, mid, nums, m):
        cur = 0
        cnt = 0
        for num in nums:
            cur += num
            if cur > mid:
                cur = num
                cnt += 1
                if cnt >= m:
                    return False
        return True

Split String

139. Word Break

Solution1. DFS

  • TLE
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    # Worst Case : Time O(n!)
    class Solution(object):
        def wordBreak(self, s, wordDict):
            wset = set(wordDict)
            return self.isWordBreak(s, wset)

        def isWordBreak(self, s, wset):
            if len(s) == 0:
                return True

            for i in xrange(len(s)):
                if s[i:] in wset:
                    if self.isWordBreak(s[:i], wset):
                        return True
            return False

Solution2. DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Time : O(n^2)
class Solution(object):
    def wordBreak(self, s, wordDict):
        wset = set(wordDict)
        n = len(s)
        dp = [False] * (n+1)
        dp[0] = True

        for i in xrange(n):
            for j in xrange(i+1):
                if s[j:i+1] in wset and dp[j]:
                    dp[i+1] = True
                    break
        return dp[-1]

140. Word Break II

  • DFS + Memorization
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def wordBreak(self, s, wordDict):
        words = set(wordDict)
        return self.dfs(s, words, {})

    def dfs(self, s, words, dic):
        if len(s) == 0:
            return ['']

        if s in dic:
            return dic[s]

        res = []
        for i in xrange(len(s)):
            if s[:i+1] in words:
                ans = self.dfs(s[i+1:], words, dic)
                for item in ans:
                    if item == '':
                        res.append(s[:i+1])
                    else:
                        res.append(s[:i+1] + ' ' + item)
        dic[s] = res
        return res

91. Decode Ways

  • care about edge cases
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution(object):
        def numDecodings(self, s):
            n = len(s)
            dp = [0] * n
            dp[0] = 1 if s[0] != '0' else 0
            for i in range(1, n):
                # case1 : 1 letter
                if s[i] != '0':
                    dp[i] += dp[i-1]

                # case2 : 2 letter
                if 10 <= int(s[i-1:i+1]) <= 26:
                    dp[i] += dp[i-2] if i >= 2 else 1
            return dp[-1]

639. Decode Ways II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def numDecodings(self, s):
        MOD = 10**9 + 7
        e0, e1, e2 = 1, 0, 0
        for c in s:#xrange(len(s)):
            if c == '*':
                f0 = 9*e0 + 9*e1 + 6*e2
                f1 = e0
                f2 = e0
            else:
                f0 = (c!='0')*e0 + e1 + (c<='6')*e2
                f1 = (c=='1')*e0
                f2 = (c=='2')*e0
            e0, e1, e2 = f0 % MOD, f1, f2
        return e0

132. Palindrome Partitioning II

  • isPalindrome can also use the DP way to solve!!!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def minCut(self, s):
        if len(s) == 0:
            return 0

        n = len(s)
        isPalin = [[False] * n for _ in range(n)]
        for j in range(n):
            for i in range(j, -1, -1):
                if s[i] == s[j] and (j-i <= 2 or isPalin[i+1][j-1]):
                    isPalin[i][j] = True

        dp = [n-1] * (n+1)
        dp[0] = 0
        for i in range(1, n+1):
            for j in range(i):
                if isPalin[j][i-1]:
                    if j == 0:
                        dp[i] = 0
                    else:
                        dp[i] = min(dp[i], dp[j] + 1)
        return dp[-1]

410. Split Array Largest Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def splitArray(self, nums, m):
        n = len(nums)
        if m >= n:
            return max(nums)

        dp = [[float('inf')] * m for _ in range(n)]
        for k in range(m):
            dp[0][k] = nums[0]

        pre_sum = [0]
        cur = 0
        for i in range(n):
            cur += nums[i]
            pre_sum.append(cur)
            dp[i][0] = cur

        for i in range(1, n):
            for j in range(i):
                for k in range(1, m):
                    dp[i][k] = min(dp[i][k], max(dp[j][k-1], pre_sum[i+1]-pre_sum[j+1]))

        return dp[-1][-1]
Share

Google High Frequency Summary

DP

Matrix Path

from (0, 0) to (0, n-1), traverse to right, right bottom and right top!

  • Follow Up1 : Must go through some points
  • Follow Up2 : Must go through a certain height

Graph -> Tree

Redundant Connection

684. Redundant Connection

Undirected Graph!

  1. Union Find
  • when the inputs are edges, you do not need to construct the graph
  • path compression, but how about the balanced part?
  1. DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def findRedundantConnection(self, edges):
        root = range(1001)

        def find(x):
            if root[x] == x:
                return x
            root[x] = find(root[x])
            return root[x]

        for i, j in edges:
            rooti = find(i)
            rootj = find(j)
            if rooti == rootj:
                return [i, j]
            root[rooti] = rootj

685. Redundant Connection II

Directed Graph

  1. Case1: There is a loop in the graph, and no vertex has more than 1 parent.
  • => Union Find
  1. Case2: A vertex has more than 1 parent, but there isn’t a loop in the graph.
  • => last node (indegree > 1)
  1. Case3: A vertex has more than 1 parent, and is part of a loop.
  • Delete the second edge!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):
    def findRedundantDirectedConnection(self, edges):
        n = len(edges)
        parent = [0] * (n+1)
        ans = None
        # Step1 : find the node with indegree > 1
        for i in xrange(n):
            u, v  = edges[i]
            if parent[v] == 0:
                parent[v] = u
            else:
                ans = [[parent[v], v], [u, v]]
                # !!! Delete the second Edge
                edges[i][1] = 0

        # Step2 : Union Find detect cycle
        root = range(n+1)
        def find(x):
            if root[x] == x:
                return x
            return find(root[x])

        for u, v in edges:
            rootu = find(u)
            rootv = find(v)
            if rootu == rootv: # Detect Cycle
                if not ans:
                    return [u, v]
                else:
                    return ans[0]
            root[rootu] = rootv
        return ans[1]

Other

843. Guess the Word

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def match(self, s1, s2):
        matches = 0
        for i in range(len(s1)):
            if s1[i] == s2[i]:
                matches += 1
        return matches

    def findSecretWord(self, wordlist, master):
        cnt = 10
        while cnt:
            guessWord = random.choice(wordlist)
            matches = master.guess(guessWord)
            newList = []
            for word in wordlist:
                if self.match(guessWord, word) == matches:
                    newList.append(word)
            wordlist = newList
            cnt -= 1

DFS

Remove Marble

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def dfs(board, x, y, row_visited, col_visited):
    m, n = len(board), len(board[0])
    if x in row_visited and y in col_visited:
        return False

    if x not in row_visited:
        row_visited.add(x)
        for j in range(n):
            if board[x][j] == 1:
                dfs(board, x, j, row_visited, col_visited)

    if y not in col_visited:
        col_visited.add(y)
        for i in range(m):
            if board[i][y] == 1:
                dfs(board, i, y, row_visited, col_visited)
    return True

def remove_number(board):

	cnt = 0 # Count the number of marble
	m, n = len(board), len(board[0])

	# Count the number of cluster
	row_visited = set()
	col_visited = set()
	cluster = 0
	for i in range(m):
		for j in range(n):
			if board[i][j] == 1:
				cnt += 1
				if dfs(board, i, j, row_visited, col_visited):
				    cluster += 1
	return cnt - cluster



board = [[1, 0, 0, 0],
        [0, 1, 0, 1],
        [0, 0, 0, 1],
        [0, 0, 1, 0]]
print(remove_number(board))
Share