Tree - Lowest Common Ancestor

Algorithms
tree

235. Lowest Common Ancestor of a Binary Search Tree

  • Use the Definition of BST !!!
1
2
3
4
5
6
7
8
9
10
11
12
# Time : O(h)
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        if not root or root == p or root == q:
            return root

        if root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

236. Lowest Common Ancestor of a Binary Tree

“The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

  • Case1 if a is NOT the ancestor of b
  1. if left subtree returns None and right subtree returns None, return None
  2. if left subtree AND right subtree return NOT NULL, return c
  3. either left or right returns NOT null, return not null
  • Case2 if a is the ancestor of b (same thing)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        # 1 Base case : root is q or p
        if not root or root is q or root is p:
            return root

        # 2 Recursion : ask value from left and right subtree
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        # Case: return c
        if left and right:
            return root

        return left if left else right

Follow up 1 Not Exist

  • What if the node p or q is NOT in the tree ?
  1. case1: if return c, no worries! a and b are in the tree
  2. case2: if return None, both a and b not in the tree
  3. case3: if sol == p or sol == q FindNode in B or A
1
2
3
4
5
6
7
sol = LowestCommonAncestor(root, p, q)
if sol is None:
    return None
elif sol != p and sol != q:
    return sol
else:
    return LowestCommonAncestor(sol, q, q) if sol == p else LowestCommonAncestor(sol, p, p)

Follow up 2 Parent Pointer

What if we have parent pointers ?

  • Method1:
  1. step1. keep looking up from a and b, to find height(a) and height(b)
  2. step2. move the one with larger height value by abs(height(a)-height(b))
  3. step3. move a and b together one step by one step until a == b
  • Method2: HashSet
    => interaction of two linked list

Follow up 3 k Nodes (No parent pointers)

General Idea to solve k-something …

  1. Method1: Binary Reduction
    • eg. Merge Sort
    • Call how many times of LCA(nodea, nodeb)? O(kn)
  2. Method2: Iterative
    • 12 -> 3, 13 -> 4, 14 -> 5 …
    • Call how many times of LCA(nodea, nodeb)? O(kn)
  3. Method3: k way all together O(n)
1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def lowestCommonAncestor(self, root, nodes):
        if not root or root in nodes:
            return root

        left = self.lowestCommonAncestor(root.left, nodes)
        right = self.lowestCommonAncestor(root.right, nodes)

        if left and right:
            return root

        return left if left else right

Follow up 4 k-nary Tree

1
2
3
4
5
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.children = []

Follow up 5 k node in k-nary tree

Combine 3 & 4

Follow up 6 very large tree

LCA for two nodes a and b in a very large tree that contains billions of nodes, given 10000 machies.(32 machines)

  • Mapper : 1 job -> distribute to 10000 machines.
  • Reducer : collect results from each mapper (machines) to do aggregation/post-processing

Solution Map-reduce
Assume we hace 32 machines 2 ^ 5 = 32, so we have 32 nodes in level 5.

  1. Case 1: both nodes a and b are within top 5 layers (we can run BFS1 within top 5 layers) Call LCA(root, a, b, level_limit = 5)

  2. Case 2: either node a or node b is within top 5 layers.

  • Assume a is on top 5 layers, Call Find(M1, b), Find(M2, b), …, Find(M32, b)
  • Say, M7 return s that I found b in my sub-tree. Call LCA(root, a, M7, level_limit = 5)
  1. Case 3: neither node a nor node b is within top 5 layers.
  • Call LCA(M1, a, b), LCA(M2, a, b), …, LCA(M32, a, b)
  • Case3.1 a and b are in different machines.
    • In this case, there must be exactly two machines that find non-null
    • Say they’re M3, M7, Call LCA(root, M3, M7, level_limit=5)
  • Case3.2 a and b are in the same machine.
    • In this case, ONLY ONE machine returns non null
    • Case3.2.1 if it returns a or b: one node is the ancestor of the other node
    • Case3.2.2 if it returns c: a and b are both in the tree and c is the LCA
Share

Sampling & Randomization

Algorithms

Reservoir Sampling

Shuffling Algorithm

pokers(spades, hearts, diamonds, clubs)

  1. Iteration 1
    Call random(0-51), lets say, random_numbers1 = 5
    P(every card can showup in position 51) = 1/52

  2. Iteration 2
    Call random(0-50), lets say, random_numbers2 = 8
    Every card was NOT selected during previous iteration = 1 - 1/52
    P(every card showup in position 50) = (1-1/52) * 1/51 = 1/52

  3. Iteration 3
    Every card was NOT selected during previous iteration = 1 - 1/52
    Every card was NOT selected during previous iteration = 1 - 1/51
    P(every card showup in position 50) = (1-1/52) (1-1/51) 1/50 = 1/52

…..

  • Select random k elements in an array of size n

Sampling for an unlimited data flow

How to do sampling for an unlimited data flow and when reading the n-th element we are required to return one random number among all numbers read so far, such that the probability of returning any element read so far is 1/n.

  • O(1) sapce complexity
  1. t = 0 call random[0-0] = random_num1, if random_num1 == 0 -> solu = input[0]
    P(input[0] will be returned as the solu) = 100%
  2. t = 1 call random[0-1] = random_num2, if random_num2 == 0 -> solu = input[1]
    P(input[0] will be returned as the solu) = 1 - 50%
    P(input[1] will be returned as the solu) = 50%
  3. t = 2 call random[0-2] = random_num3, if random_num3 == 0 -> solu = input[2]
    P(input[0] will be returned as the solu) = 1/2 (1 - 1/3) = 1/3
    P(input[1] will be returned as the solu) = 1/2     (1 - 1/3) = 1/3
    P(input[2] will be returned as the solu) = 1/3
    ….

Return k out of n log

  • same thing as above!
  • first k element put into the reservoir
  • when new element comes in, generate a random number from 0 to its index
  • if index < k, replace the new element with the k postion element

398. Random Pick Index

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

    def __init__(self, nums):
        self.nums = nums

    def pick(self, target):
        cnt = 0
        res = 0
        for i in xrange(len(self.nums)):
            if self.nums[i] != target:
                continue
            if random.randint(0, cnt) == 0:
                res = i
            cnt += 1
        return res

Return a random largest number’s index

Randomization

Random(5) -> Random(25) -> Random(7)
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24

  1. call Random(5) for the 1st time = random_num1[0—4] = row number
  2. call Random(5) for the 2nd time = random_num2[0—4] = col number
    generated_number = r1 * 5 + r2

470. Implement Rand10() Using Rand7()

1
2
3
4
5
6
7
8
9
class Solution(object):
    def rand10(self):
        r1 = rand7()
        r2 = rand7()
        num = (r1-1) * 7 + (r2-1)
        if num <= 39:
            return (num % 10) + 1
        else:
            return self.rand10()

Design Random(1,000,000) with Random(5)

  • $log_5(1000000)$

528. Random Pick with Weight

  • PreSum + Binary Search
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution(object):

        def __init__(self, w):
            if not w: return

            s = [w[0]]
            for weight in w[1:]:
                s.append(s[-1] + weight)
            self.sum = s
            print(self.sum)

        def pickIndex(self):
            num = random.randint(1, self.sum[-1])
            start, end = 0, len(self.sum)-1
            while start < end:
                mid = (start + end) / 2
                if self.sum[mid] < num:
                    start = mid + 1
                else:
                    end = mid
            return start

Random

380. Insert Delete GetRandom O(1)

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 RandomizedSet(object):

    def __init__(self):
        self.nums = []
        self.dic = {}

    def insert(self, val):
        if val in self.dic:
            return False
        self.nums.append(val)
        idx = len(self.nums) - 1
        self.dic[val] = idx
        return True

    def remove(self, val):
        if val not in self.dic:
            return False
        last = len(self.nums) - 1
        idx = self.dic[val]
        if last != idx:
            self.nums[last], self.nums[idx] = self.nums[idx], self.nums[last]
            self.dic[self.nums[idx]] = idx
        del self.dic[val]
        self.nums.pop()
        return True

    def getRandom(self):
        return random.choice(self.nums)
Share

String Advanced

Algorithms
sliding window, string

Sliding Window in a String

  • Hash table

3. Longest Substring Without Repeating Characters

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        visited = set()
        left = right = 0
        cnt = 0
        n = len(s)
        while right < n:
            if s[right] not in visited:
                visited.add(s[right])
                right += 1
                cnt = max(cnt, right-left)
            else:
                visited.remove(s[left])
                left += 1
        return cnt

###159. Longest Substring with At Most Two Distinct Characters

  • Two pointers: i - traversal, start - shrink to meet the condition!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def lengthOfLongestSubstringTwoDistinct(self, s):
        chars = [0] * 256
        start = 0
        res = cnt = 0
        for i in xrange(len(s)):
            idx = ord(s[i])
            if chars[idx] == 0:
                cnt += 1
            chars[idx] += 1

            while cnt > 2: # shrink
                idx = ord(s[start])
                chars[idx] -= 1
                if chars[idx] == 0:
                    cnt -= 1
                start += 1
            res = max(res, i-start+1)
        return res

340. Longest Substring with At Most K Distinct Characters

  • care about variables!!! always miss some statements
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def lengthOfLongestSubstringKDistinct(self, s, k):
        chars = [0] * 256
        start = 0
        res = cnt = 0
        for i in xrange(len(s)):
            idx = ord(s[i])
            if chars[idx] == 0:
                cnt += 1
            chars[idx] += 1

            while cnt > k:
                idx = ord(s[start])
                chars[idx] -= 1
                if chars[idx] == 0:
                    cnt -= 1
                start += 1
            res = max(res, i-start+1)
        return res

438. Find All Anagrams in a String

Sol1. Sort

Time : O(n m logm)

Sol2.Sliding Window

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
class Solution(object):
    def findAnagrams(self, s, p):
        m, n = len(s), len(p)

        char_dic = collections.defaultdict(int)
        cnt = 0

        # Init p : count char in p
        for ch in p:
            char_dic[ch] += 1
            if char_dic[ch] == 1:
                cnt += 1

        # Init sliding window
        for ch in s[:n]:
            if ch not in char_dic:
                continue

            char_dic[ch] -= 1
            if char_dic[ch] == 0:
                cnt -= 1

        res = []
        if cnt == 0:
            res.append(0)

        # move the Fixed size sliding window
        for i in xrange(m-n):
            if s[i] in char_dic:
                char_dic[s[i]] += 1
                if char_dic[s[i]] == 1:
                    cnt += 1
            if s[i+n] in char_dic:
                char_dic[s[i+n]] -= 1
                if char_dic[s[i+n]] == 0:
                    cnt -= 1
            if cnt == 0:
                res.append(i+1)

        return res

Flip 0 to 1

Given a 0-1 array, you can flip at most k ‘0’s to ‘1’s.Please find the longest subarray that consists of all ‘1’s.

  • Solution : Find a slinding window that contains at most k zeros.
  1. When to move the right border: when the counter of zeros <=k
  2. When to move the left border: when the counter of zeros >k
  • Clarify the information contains in the sliding window
  • when to move the pointer/border

Read4

157. Read N Characters Given Read4

  • fixed size 4 temp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def read(self, buf, n):
        cnt = 0
        while cnt < n:
            temp = [''] * 4
            rd = read4(temp)
            to_copy = min(rd, n-cnt)
            for i in range(to_copy):
                buf[cnt] = temp[i]
                cnt += 1

            if to_copy == 0:
                return cnt
        return cnt

158. Read N Characters Given Read4 II - Call multiple times

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def __init__(self):
        self.queue = collections.deque()

    def read(self, buf, n):
        cnt = 0
        queue = self.queue
        while queue and cnt < n:
            buf[cnt] = queue.popleft()
            cnt += 1

        while cnt < n:
            temp = [''] * 4
            rd = read4(temp)
            for i in range(rd):
                queue.append(temp[i])

            k = min(rd, n-cnt)
            for _ in range(k):
                buf[cnt] = self.queue.popleft()
                cnt += 1
            if k == 0:
                return cnt
        return cnt
Share

Binary Search Advanced

Algorithms
binary search

Advanced Topic

162. Find Peak Element

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def findPeakElement(self, nums):
        nums = [-float('inf')] + nums + [-float('inf')]
        start, end = 1, len(nums) - 2
        while start <= end:
            mid = start + (end - start) / 2
            if nums[mid] <= nums[mid-1]:
                end = mid - 1
            elif nums[mid] <= nums[mid+1]:
                start = mid + 1
            else:
                return mid-1
        return -1

4. Median of Two Sorted Arrays

  • Input Two Sorted Array. How to do Binary Search?
  • Stick with the edge case, like len(nums) <= 1 and len is odd or even!!!
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
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        m, n = len(nums1), len(nums2)
        if m > n:
            return self.findMedianSortedArrays(nums2, nums1)

        start, end = 0, m
        k = (m + n) // 2
        while start <= end:
            cut1 = start + (end - start) // 2
            cut2 = k - cut1
            # Deal with edge case 1 : length
            l1 = nums1[cut1-1] if cut1 > 0 else -float('inf')
            l2 = nums2[cut2-1] if cut2 > 0 else -float('inf')
            r1 = nums1[cut1] if cut1 < m else float('inf')
            r2 = nums2[cut2] if cut2 < n else float('inf')
            if l1 > r2:
                end = cut1 - 1
            elif l2 > r1:
                start = cut1 + 1
            else:
                # Deal with the edge case 2 : odd or even!
                if (m+n) % 2:
                    return min(r1, r2)
                else:
                    return (max(l1,l2) + min(r1,r2)) / 2.0

29. Divide Two Integers

Division simply requires us to find how many times we can subtract the divisor from the the dividend without making the dividend negative

  • i 1, 2, 4, 8, 16, 32, 64 …
  • i 1, 2, 4, 8, …
  • i …
  • i 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Same Thought
class Solution(object):
    def divide(self, dividend, divisor):
        np = (dividend < 0) ^ (divisor < 0)
        dividend = abs(dividend)
        divisor = abs(divisor)
        res = 0
        while dividend >= divisor:
            tmp, i = divisor, 1
            while dividend >= tmp:
                dividend -= tmp
                res += i
                i = i << 1
                tmp = tmp << 1
        if np:
            res = -res
        return min(max(-2147483648, res), 2147483647)
  • clean
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def divide(self, dividend, divisor):
        sign = (dividend > 0) ^ (divisor > 0)
        dividend, divisor = abs(dividend), abs(divisor)
        res = 0
        i = 1
        div = divisor
        while dividend >= div:
            dividend -= div
            res += i
            i = i << 1
            div = div << 1
            if dividend < div: # when div bigger enough that dividend can not minus it
                i = 1
                div = divisor

        if sign: res = -res
        return min(max(-2147483648, res), 2147483647)

658. Find K Closest Elements

  • two pointers + binary search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def findClosestElements(self, arr, k, x):
        if x <= arr[0]:
            return arr[:k]
        elif x >= arr[-1]:
            return arr[-k:]
        else:
            index = bisect.bisect_left(arr, x)
            left = max(0, index-k)
            right = min(len(arr)-1, index+k-1)
            while right - left > k-1:
                if arr[right] - x >= x - arr[left]:
                    right -= 1
                else:
                    left += 1
            return arr[left:right+1]

300. Longest Increasing Subsequence

  • Use DP, we can have the O(n^2). It is hard to give the O(nlogn) solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def lengthOfLIS(self, nums):
        if not nums: return 0

        n = len(nums)
        ends = [nums[0]]
        for i in xrange(1, n):
            if nums[i] > ends[-1]:
                ends.append(nums[i])
                continue

            start, end = 0, len(ends)-1
            while start < end:
                mid = start + (end - start) / 2
                if ends[mid] < nums[i]:
                    start = mid + 1
                else:
                    end = mid
            ends[start] = nums[i]
        return len(ends)

275. H-Index II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def hIndex(self, citations):
        if not citations:
            return 0

        n = len(citations)
        if citations[-1] < 1:
            return 0

        start, end = 0, n-1
        while start < end:
            mid = start + (end - start) // 2
            if citations[mid] >= n - mid:
                end = mid
            else:
                start = mid + 1
        return n-start

774. Minimize Max Distance to Gas Station

  • use valid function => Binary Search the results!!!
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution(object):
        def minmaxGasDist(self, stations, K):
            def valid(D):
                return sum([int((p2-p1) / D) for p1, p2 in zip(stations, stations[1:])]) <= K

            start, end = 0, stations[-1]-stations[0]
            while end - start > 1e-6:
                mid = (start + end) / 2.0
                if valid(mid):
                    end = mid
                else:
                    start = mid
            return start
Share

Greedy Schedule

Algorithms
greedy

Interval Schedule

435. Non-overlapping Intervals

  • minimum number of removed intervels, maximum number of compatible intervals
  • sort by end time !!! Why?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def eraseOverlapIntervals(self, intervals):
        if not intervals: return 0

        intervals.sort(key = lambda x: x.end)
        cnt = 0
        prev_end = -float('inf')
        for inter in intervals:
            start, end = inter.start, inter.end
            if start >= prev_end:
                prev_end = end
            else:
                cnt += 1
        return cnt

252. Meeting Rooms

1
2
3
4
5
6
7
8
class Solution:
    def canAttendMeetings(self, intervals):
        intervals.sort(key = lambda x:x.end)

        for i in range(1, len(intervals)):
            if intervals[i].start < intervals[i-1].end:
                return False
        return True

253. Meeting Rooms II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def minMeetingRooms(self, intervals):
        times = []
        for inter in intervals:
            times.append((inter.start, 1))
            times.append((inter.end, 0))

        times.sort()
        cnt = 0
        res = 0
        for t, f in times:
            if f:
                cnt += 1
            else:
                cnt -= 1
            res = max(res, cnt)
        return res

Deadline Schedule

630. Course Schedule III

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def scheduleCourse(self, courses):
        start = 0
        heap = []
        for t, d in sorted(courses, key = lambda (t,d):d):
            start += t
            heapq.heappush(heap, -t)
            while start > d:
                start += heapq.heappop(heap)
        return len(heap)

Arrive

55. Jump Game

  • Use reach array will cause TLE
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution(object):
        def canJump(self, nums):
            n = len(nums)
            reach = 0
            for i in xrange(n):
                if i > reach:
                    return False
                else:
                    reach = max(reach, i+nums[i])
            return reach >= n-1

134. Gas Station

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        if sum(cost) > sum(gas):
            return -1

        n = len(gas)
        balance = 0
        start = 0
        for i in range(n):
            balance += gas[i] - cost[i]
            if balance < 0:
                start = i + 1
                balance = 0
        return start
Share

Hash Table

Algorithms
TODO, hash table

A hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

  • Hash Fucntion
  • Hash Collision
  1. Separate chaining
  2. Open addressing

Implement a Hash Table

TODO

347. Top K Frequent Elements

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def topKFrequent(self, nums, k):
        cnt = collections.defaultdict(int)
        for n in nums:
            cnt[n] += 1

        heap = []
        for key in cnt.keys():
            heapq.heappush(heap, (cnt[key], key))
            if len(heap) == k+1:
                heapq.heappop(heap)
        return [key for c, key in heap]

268. Missing Number

1
2
3
4
5
6
7
class Solution(object):
    def missingNumber(self, nums):
        nset = set(nums)
        n = len(nums)
        for i in xrange(n+1):
            if i not in nset:
                return i

349. Intersection of Two Arrays

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

1
2
3
class Solution(object):
    def intersection(self, nums1, nums2):
        return list(set(nums1)&set(nums2))

Follow up : two sorted array

  • Binary Search, Time : O(mlogn), Space : O(1)
  • Two pointers, Time : O(m + n), Space : O(1)

Find common elements in 3 sorted Arrays

  1. Solution1: three Pointers
    How to move each pointer

  2. Solution2: find common elements a1,a2 then a3

Counter

299. Bulls and Cows

We usually use hash table to do things like counter!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def getHint(self, secret, guess):
        bulls = 0
        for ch1, ch2 in zip(secret, guess):
            if ch1 == ch2:
                bulls += 1

        cnt = [0] * 10
        for ch in secret:
            cnt[ord(ch)-ord('0')] += 1
        common = 0
        for ch in guess:
            if cnt[ord(ch)-ord('0')] != 0:
                common += 1
                cnt[ord(ch)-ord('0')] -= 1
        cows = common - bulls
        return str(bulls) + "A" + str(cows) + "B"

Share

Depth First Search

Algorithms
dfs

Basic

We use DFS a lot in Tree or Graph.

  • DFS can only be implemented by using recursion?
  1. No. It can be implemented by using either iterative way, or in a recursive way.
  2. it is easier to use recursion to implement. (pre,in,post order traversal iteration in tree)
  • Method
  1. What dose it store on each level?
  2. How many different states should we try to put on the level?

Subset

O(2^n)

78. Subsets

Different recursion ways with different recursion Tree!

Sol1. Exist or not

Each node has two braching subtree!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Time : O(2^n)
class Solution(object):
    def subsets(self, nums):
        if not nums: return []

        res = []
        self.dfs(nums, 0, [], res)
        return res

    def dfs(self, nums, idx, path, res):
        if idx == len(nums):
            res.append(path)
            return

        # Other programming language, we have to append,than pop in the path
        # But in python, we just add it as parameter!
        self.dfs(nums, idx + 1, path + [nums[idx]], res)
        self.dfs(nums, idx + 1, path, res)

Sol2. Position

Each level nodes have different number subtree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Time : Hard to Analyze!
class Solution(object):
    def subsets(self, nums):
        if not nums: return []

        res = []
        self.dfs(nums, 0, [], res)
        return res

    def dfs(self, nums, idx, path, res):
        res.append(path)

        for i in xrange(idx, len(nums)):
            self.dfs(nums, i+1, path+[nums[i]], res)

Sol3. Iteration

1
2
3
4
5
6
class Solution(object):
    def subsets(self, nums):
        res = [[]]
        for num in nums:
            res += [item+[num] for item in res]
        return res

90. Subsets II

Sol1. 2 Branching

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def subsetsWithDup(self, nums):
        res = []
        nums.sort()
        self.dfs(nums, 0, [], res)
        return res


    def dfs(self, nums, idx, path, res):
        if idx == len(nums):
            res.append(path)
            return

        self.dfs(nums, idx + 1, path + [nums[idx]], res)

        while idx < len(nums)-1 and nums[idx] == nums[idx+1]:
            idx += 1

        self.dfs(nums, idx + 1, path, res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def subsetsWithDup(self, nums):
        nums.sort()
        pairs = []
        for num in nums:
            if not pairs or num != pairs[-1][0]:
                pairs.append([num, 1])
            else:
                pairs[-1][1] += 1
        self.res = []
        self.dfs(pairs, 0, [])
        return self.res

    def dfs(self, pairs, idx, path):
        if idx == len(pairs):
            self.res.append(path)
            return

        num, cnt = pairs[idx]
        for k in range(cnt+1):
            self.dfs(pairs, idx+1, path + ([num] * k))

Sol2. Position

  • Position recursion can remove duplicates by removing same brachings!
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(object):
    def subsetsWithDup(self, nums):
        if not nums:
            return []
        res = []
        self.dfs(sorted(nums), 0, [], res)
        return res

    def dfs(self, nums, idx, path, res):
        res.append(path)

        for i in xrange(idx, len(nums)):
            if i > idx and nums[i] == nums[i-1]:
                continue
            self.dfs(nums, i+1, path+[nums[i]], res)

    # Why we can not just append and pop new elements?
    # we should deep copy the results!!!
    def dfs1(self, nums, idx, path, res):
        res.append(copy.deepcopy(path))

        for i in xrange(idx, len(nums)):
            if i > idx and nums[i] == nums[i-1]:
                continue

            path.append(nums[i]) # python not suggested this way!
            self.dfs1(nums, i+1, path, res)
            path.pop()

Permutation

O(n!)

46. Permutations

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def permute(self, nums):
        res = []
        self.dfs(res, nums, [])
        return res

    def dfs(self, res, nums, path):
        if not nums:
            res.append(path)

        for i in xrange(len(nums)):
            self.dfs(res, nums[:i]+nums[i+1:], path+[nums[i]])
  • TODO : Space Consuming

47. Permutations II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def permuteUnique(self, nums):
        res = []
        self.dfs(sorted(nums), res, [])
        return res

    def dfs(self, nums, res, path):
        if not nums:
            res.append(path)
            return

        for i in xrange(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            self.dfs(nums[:i]+nums[i+1:], res, path+[nums[i]])

22. Generate Parentheses

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def generateParenthesis(self, n):
        self.res = []
        self.dfs( n, n, [])
        return self.res

    def dfs(self, left, right, path):
        if left == right == 0:
            self.res.append(''.join(path))
            return

        if left > 0:
            self.dfs(left - 1, right, path + ['('])

        if right > left:
            self.dfs(left, right - 1, path + [')'])
Share

Heap

Algorithms
heap

Heap, also called “Priority Queue”

Basic

Definition

  • value in any node is less than its decendent and root is the least element
  • complete binary tree
  • Max Heap means root is maximum element, Min Heap means root is minimum element
  • unsorted bu follow rules above

Operation

  • insert, put the element in the last and swap up, O(logn)
  • update, O(logn)
  • get/top, get the root element, O(1)
  • pop, delete the root element, O(logn) put the last element to the root
  • heapify: transform unsorted array to a heap, O(n)

Python Lib

  • min heap
  1. heapq.heapify(iterable), O(c * n)
    This function is used to convert the iterable into a heap data structure. i.e. in heap order.
  2. heapq.heappush(heap, ele), O(logn)
    This function is used to insert the element mentioned in its arguments into heap. The order is adjusted, so as heap structure is maintained.
  3. heapq.heappop(heap), O(logn)
    This function is used to remove and return the smallest element from heap. The order is adjusted, so as heap structure is maintained.
  4. heapq.heappushpop(heap, ele)
    This function combines the functioning of both push and pop operations in one statement, increasing efficiency. Heap order is maintained after this operation.
  5. heapq.heapreplace(heap, ele)
    This function also inserts and pops element in one statement, but it is different from above function. In this, element is first popped, then element is pushed.i.e, the value larger than the pushed value can be returned.
  6. heapq.nlargest(k, iterable, key = fun)
    This function is used to return the k largest elements from the iterable specified and satisfying the key if mentioned.
  7. heapq.nsmallest(k, iterable, key = fun)
    This function is used to return the k smallest elements from the iterable specified and satisfying the key if mentioned.
1
import heapq

LintCode 544. Top k Largest Numbers

Sol1. Sort

  • Time : O(nlogn)
    1
    2
    3
    class Solution:
        def topk(self, nums, k):
            return sorted(nums)[-k:][::-1]

Sol2. Min heap

  • Time : O(k + (n-k)logk)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import heapq
class Solution:
    def topk(self, nums, k):
        heap = []

        # Heapify k elements, O(k)
        heap = heapq.heapify(nums[:k])
        #for i in xrange(k):
        #    heapq.heappush(heap, nums[i])

        # Keep pop out n-k elements, O((n-k)logk)
        n = len(nums)
        for i in xrange(k, n):
            heapq.heappush(heap, nums[i])
            heapq.heappop(heap)

        return sorted(heap, reverse=True)

Sol3. Max heap

  • Time : O(n + klog(n))
  • Step1. Heapify, O(n)
  • Step2. pop k elements, O(klogn)

Sol4. Quick Partition

  • Time : Amortized O(n), Worst Case : O(n^2)

218. The Skyline Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def getSkyline(self, buildings):
        positions = set([b[0] for b in buildings] + [b[1] for b in buildings])
        res = [[0, 0]]
        live = []
        i = 0
        for p in sorted(positions):
            # Keep all the position before p to the heap "live"
            while i < len(buildings) and buildings[i][0] <= p:
                heapq.heappush(live, (-buildings[i][2], buildings[i][1]))
                i += 1

            # Keep the maximum height's position > p
            while live and live[0][1] <= p:
                heapq.heappop(live)

            h = -live[0][0] if live else 0
            if h != res[-1][1]:
                res.append([p, h])
        return res[1:]

857. Minimum Cost to Hire K Workers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def mincostToHireWorkers(self, quality, wage, K):
        workers = sorted([(float(w)/q, q) for q, w in zip(quality, wage)])

        pool = []
        qsum = 0
        res = float('inf')
        for r, q in workers:
            heapq.heappush(pool, -q)
            qsum += q
            if len(pool) > K:
                qsum += heapq.heappop(pool)

            if len(pool) == K:
                res = min(res, r * qsum)
        return res
Share

String Basic

Algorithms
string

Popular representation of characters:

  1. ASCII representation of a letter: A==65, a==97
  2. Unicode : the latest version of Unicode contains a repertoire of more than 110,000 charaters covering 100 scripts and various symbols.

Removol

Char Removal

Remove a/some particular chars from a String. Example: string input = “student”, remove “u and n” -> output:”stdet”

  • Attention : String and Array erase API!!!
1
2
3
4
5
6
7
8
9
class Solution:
    def charRemoval(self, s, ch):
        chs = list(s)
        start = 0
        for i in xrange(len(chs)):
            if chs[i] not in ch:
                chs[start] = chs[i]
            start += 1
        retrun ''.join(chs[:start])

27. Remove Element

1
2
3
4
5
6
7
8
class Solution(object):
    def removeElement(self, nums, val):
        start = 0
        for i in xrange(len(nums)):
            if nums[i] != val:
                nums[start] = nums[i]
                start += 1
        return start

Char Removal II

Remove all leading/trailing and duplicate empty spaces(only leave one empty space if duplicated spaces happen) from the input string.

De-duplication

26. Remove Duplicates from Sorted Array

What’s the phisical definition of the two pointers???

  • slow: all elements to the left hand side of slow pointer(excluding slow) are the final results to return
  • fast: current index
1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def removeDuplicates(self, nums):
        if not nums:
            return 0

        start = 1
        for i in xrange(1, len(nums)):
            if nums[i] != nums[start-1]:
                nums[start] = nums[i]
                start += 1
        return start
  • follow up : what if we want to reserve 2 duplicate elements?

80. Remove Duplicates from Sorted Array II

  • you can just compare the current pointer with slow - 2 position
1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def removeDuplicates(self, nums):
        if len(nums) <= 2:
            return len(nums)

        slow = 2
        for i in xrange(2, len(nums)):
            if nums[i] != nums[slow-2]:
                nums[slow] = nums[i]
                slow += 1
        return slow
  • follow up : what if we want to reserve k duplicate elements?

Remove adjacent letters repeatedly

  • Stack or Two pointers

Reversal

344. Reverse String

  • two pointers : left, right or start, end
    1
    2
    3
    4
    5
    6
    7
    8
    9
    class Solution(object):
        def reverseString(self, s):
            chs = list(s)
            s, e = 0, len(s)-1
            while s < e:
                chs[s], chs[e] = chs[e], chs[s]
                s += 1
                e -= 1
            return ''.join(chs)

557. Reverse Words in a String III

1
2
3
4
5
6
class Solution(object):
    def reverseWords(self, s):
        words = s.split()
        for i in xrange(len(words)):
            words[i] = words[i][::-1]
        return ' '.join(words)

186. Reverse Words in a String II

e.g. “I love Google” - “Google love I”

  • sol1. split and reverse
    but not in-place in thie way!

  • sol2. reverse twice(trick)

  1. reverse each words “I love Google” - “I evol elgooG”
  2. reverse the string “Google love I”
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def reverseWords(self, str):
        n = len(str)
        # Step 1. reverse each word
        start = 0
        for i in xrange(n+1):
            if i == n or str[i] == " ":
                end = i-1
                while start < end:
                    str[start], str[end] = str[end], str[start]
                    start += 1
                    end -= 1
                start = i + 1

        # Step 2. reverse all the sentences
        start, end = 0, n-1
        while start < end:
            str[start], str[end] = str[end], str[start]
            start += 1
            end -= 1
  • Dicussion
  1. The idea for “I LOVE GOOGLE” can be combined to form more complex prblem. e.g., if we have empty/leading/trailing spaces in the input.
  2. The idea can be extended to other probem as well!
    • “abcdef” sift to the left by two steps “cdefab”
    • step1. seperate reverse “bafedc”
    • step2. reverse the word “cdefab”

189. Rotate Array

  • use the same trick as we used in the reverse words in sentence!
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution(object):
        def rotate(self, nums, k):
            n = len(nums)
            k = k % n
            self._reverse(nums, 0, n-k-1)
            self._reverse(nums, n-k, n-1)
            self._reverse(nums, 0, n-1)

        def _reverse(self, nums, start, end):
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1

Char Replace

Word Replacement

“student” -> “stuXXt”(den -> XX)

  • Two Pointers
  1. slow: all letters to the left hand side of slow are the results to return
  2. fast: fast index to scan the whole string
  • follow up
    s1 = “_“, s2 = “20%”

833. Find And Replace in String

  • Replaced String part is longer than original part, How do you deal with that?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def findReplaceString(self, S, indexes, sources, targets):
        n = len(indexes)
        res = []
        prev = 0
        for idx, src, target in sorted(zip(indexes, sources, targets)):
            if idx > prev:
                res.append(S[prev:idx])
                prev = idx

            if S[idx:idx+len(src)] != src:
                continue
            res.append(target)
            prev = idx + len(src)

        res.append(S[prev:])
        return ''.join(res)

844. Backspace String Compare

  • Traverse Backwards!!!
    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
    class Solution(object):
        def backspaceCompare(self, S, T):
            m, n = len(S), len(T)
            ps, pt = m-1, n-1
            while ps >= 0 or pt >= 0:
                # S
                backS = 0
                while ps >= 0 and (backS > 0  or S[ps] == '#'):
                    backS += 1 if S[ps] == '#' else -1
                    ps -= 1

                # T
                backT = 0
                while pt >= 0 and (backT > 0 or T[pt] == '#'):
                    backT += 1 if T[pt] == '#' else -1
                    pt -= 1

                if (pt < 0) ^ (ps < 0):
                    return False

                if pt >= 0 and ps >= 0 and S[ps] != T[pt]:
                    return False

                pt -= 1
                ps -= 1
            return True

String to Number

8. String to Integer (atoi)

  • Take Care of Edge Cases!!!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def myAtoi(self, str):
        n = len(str)        
        p = 0
        # filter the space
        while p < n and str[p] == ' ':
            p += 1

        # positive or negtive
        neg = False
        if p < n and str[p] in "+-":
            if str[p] == '-':
                neg = True
            p += 1

        num = 0
        while p < n and str[p].isnumeric():
            num = num * 10 + int(str[p])
            p += 1

        if neg:
            num = -num

        return min(2**31-1, max(-2**31, num))

65. Valid Number

  • Define the state, Keep in mind : different states!!!
    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
    class Solution:
        def isNumber(self, s):
            s = s.strip()
            states = [{'+-': 2, '0-9': 1, '.': 3},
                      {'0-9': 1, 'e': 5, '.': 4},
                      {'0-9': 1, '.': 3},
                      {'0-9': 4},
                      {'0-9': 4, 'e': 5},
                      {'0-9': 7, '+-': 6},
                      {'0-9': 7},
                      {'0-9': 7}]
            cur = 0
            for ch in s:
                if ch.isdigit():
                    flag = "0-9"
                elif ch in "+-":
                    flag = "+-"
                else:
                    flag = ch

                if flag not in states[cur]:
                    return False
                cur = states[cur][flag]

            return cur in [1, 4, 7]

504. Base 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def convertToBase7(self, num):
        if num == 0:
            return "0"

        sign = True if num < 0 else False
        num = abs(num)
        base7 = []
        while num > 0:
            base7.append(str(num%7))
            num = num // 7
        if sign:
            base7.append("-")
        res = ''.join(base7[::-1])
        return res

12. Integer to Roman

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def intToRoman(self, num):
        roman = {1000:'M', 500:'D', 100:'C', 50:'L', 10:'X', 5:'V', 1:'I'}
        res = []
        ns = [1000, 500, 100, 50, 10, 5, 1]
        for k in range(7):
            t = num // ns[k]
            if t == 0:
                continue

            num = num % ns[k]
            if t == 4:
                if len(res) == 0 or res[-1] != roman[ns[k-1]]:
                    res.append(roman[ns[k]] + roman[ns[k-1]])
                else:
                    res.pop()
                    res.append(roman[ns[k]] + roman[ns[k-2]])
            else:
                res.append(roman[ns[k]] * t)
        return ''.join(res)

Encode and Decode

394. Decode String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def decodeString(self, s):
        stack = [[[], 1]] # repeat string array, times of repeat
        num = 0
        for ch in s:
            if ch.isdigit():
                num = num * 10 + (ord(ch) - ord('0'))
            elif ch == '[':
                stack.append([[], num])
                num = 0
            elif ch == ']':
                chs, k = stack.pop()
                stack[-1][0] += (chs * k)
            else:
                stack[-1][0].append(ch)
        return ''.join(stack[0][0])

Strobogrammatic Number

246. Strobogrammatic Number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def isStrobogrammatic(self, num):
        dic = {0:0, 1:1, 6:9, 8:8, 9:6}
        left, right = 0, len(num)-1
        while left <= right:
            l, r = int(num[left]), int(num[right])
            if l not in dic or r not in dic:
                return False

            if dic[l] != r:
                return False

            left += 1
            right -= 1
        return True

247. Strobogrammatic Number II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def findStrobogrammatic(self, n):
        self.n = n
        return self.helper(n)

    def helper(self, m):
        if m == 0:
            return [""]

        if m == 1:
            return ["0", "1", "8"]

        sub = self.helper(m - 2)
        res = []
        for s in sub:
            if m != self.n:
                res.append("0" + s + "0")

            for can in ["11", "88", "69", "96"]:
                res.append(can[0] + s + can[1])
        return res

248. Strobogrammatic Number III

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 Solution(object):
    def strobogrammaticInRange(self, low, high):
        m, n = len(low), len(high)
        self.temp = {0:[""], 1:["1", "0", "8"]}
        self.memo = {1:["1", "0", "8"]}
        res = []
        for i in range(m, n+1):
            self.helper(i)

        cnt = 0
        blow, bhigh = int(low), int(high)
        for i in range(n, m-1, -1):
            temp = self.memo[i]
            for item in temp:
                if blow <= int(item) <= bhigh:
                    cnt += 1
        return cnt


    def helper(self, k):
        if k in self.temp:
            return self.temp[k]

        sub = self.helper(k-2)
        res = []
        for s in sub:
            for can in ("11", "88", "69", "96"):
                res.append(can[0] + s + can[1])

        self.memo[k] = res

        ans = []
        for s in sub:
            ans.append("0" + s + "0")

        self.temp[k] = res + ans
        return res + ans

String continuous count

38. Count and Say

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def countAndSay(self, n):
        if n == 1:
            return "1"

        prev = self.countAndSay(n-1)
        ans = []
        for ch in prev:
            if not ans or ch != ans[-1][0]:
                ans.append([ch, 1])
            else:
                ans[-1][1] += 1

        res = []
        for ch, cnt in ans:
            res.append(str(cnt) + ch)

        return ''.join(res)
Share

Stack

Algorithms
stack

Logic Data Structure

Queue

  • FIFO == First In First Out, e.g. waith in a line
  • Usages
    • BFS related problems, Tree printout by levels
    • Sliding Window problems(Deque)

225. Implement Stack using Queues

  • Only use one Queue, O(n)push, O(1)pop
  • Two Queues, O(1)push, O(n)pop
    1
    2
    3
    4
    5
    queue = collections.deque()
    queue.append(1)
    queue.appendleft(2)
    queue.pop()
    queue.popleft()

What is Stack?

  • LIFO == Last in First Out, e.g. like a box
  • All operation available: push(), pop(), top()
  • Iterative DFS

Discussion

  • When do we consider “stack” in our algorithm?
  • Answer: when we linear scan an array/a string from left to right, and we need to look back the top element!
      1. Find the biggest Rectangle in Histogram
      1. Reverse Polish notation, a (b + c) -> abc+
      1. String repeatedly deduplication. cabba -> caa -> c

Design Data Structure

232.Implement Queue using Stacks

Implement a Queue by using two stacks

  • Key Point : When we pop all the elements from stack1 to stack2, we do not need to pop all the elements to stack1 again! Just put them to stack2 waiting for pop() function!
  • Time : pop(),amortized O(1); push(),O(1)
  • Space : O(n)
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
class MyQueue(object):

    def __init__(self):
        self.stack1 = [] # Buffer all the new elements
        self.stack2 = [] # Pop out the 1st element

    def push(self, x):
        self.stack1.append(x)


    def pop(self):
        if len(self.stack2) == 0:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()


    def peek(self):
        if len(self.stack2) == 0:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2[-1]

    def empty(self):
        return len(self.stack1) == 0 and len(self.stack2) == 0

155. Min Stack

  • Two Stack: original stack & min stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Keep the push and pop function in sync between two stacks
class MinStack(object):

    def __init__(self):
        self.stack = []
        self.minstack = []

    def push(self, x):
        self.stack.append(x)
        cmin = min(x, self.minstack[-1]) if self.minstack else x
        self.minstack.append(cmin)

    def pop(self):
        self.stack.pop()
        self.minstack.pop()

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.minstack[-1]

Min Stack Follow Up

  • How to optimize the space usage of minstack? (Assume there are a lot of duplicates)
    Try to make the elements in stack2 a descending order and store an element in stack2 <value, size of the stack1 when elements add to stack2>
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class MinStack:

        def __init__(self):
            self.stack = []
            self.minStack = []

        def push(self, x):
            self.stack.append(x)
            if not self.minStack or x < self.minStack[-1][0]:
                self.minStack.append((x, len(self.stack)))

        def pop(self):
            self.stack.pop()
            if len(self.stack) < self.minStack[-1][1]:
                self.minStack.pop()


        def top(self):
            return self.stack[-1]


        def getMin(self):
            return self.minStack[-1][0]

716. Max Stack

  • popMax() – Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.
  • TreeMap in Java!!!
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
class MaxStack(object):

    def __init__(self):
        self.stack = []

    def push(self, x):
        self.stack.append((x, max(x, self.stack[-1][1] if self.stack else None)))        

    def pop(self):
        return self.stack.pop()[0]

    def top(self):
        return self.stack[-1][0]

    def peekMax(self):
        return self.stack[-1][1]

    def popMax(self):
        m = self.stack[-1][1]
        temp = []
        while self.stack[-1][0] != m:
            temp.append(self.pop()) # temp.insert(0, self.stack.pop())
        self.stack.pop()
        map(self.push, reversed(temp))
        return m
  • TODO : Using Stack for Selection Sort; Implement Deque using stacks

20. Valid Parentheses

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def isValid(self, s):
        stack = []
        pdic = {'(':')', '{':'}', '[':']'}
        for ch in s:
            if ch in "({[":
                stack.append(pdic[ch])
            else:
                if len(stack) == 0 or stack[-1] != ch:
                    return False
                stack.pop()
        return len(stack) == 0

O(1) Stack

Remove 3 or more duplicates repeatedly

  • Stack + traversal pointer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def removeDuplicates(s):
    stack = []
    i = 0
    print(s)
    while i < len(s):
        if len(stack) > 1 and s[i] == stack[-1] == stack[-2]:
            while i < len(s) and s[i] == stack[-1]:
                i += 1
            stack.pop()
            stack.pop()
        else:
            stack.append(s[i])
            i += 1
    return stack

# TEST
if __name__ == "__main__":
    string = raw_input()
    res = removeDuplicates(string)
    print(res)
  • Use Two pointers to imitate the stack!
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    def removeDuplicates(s):
        i = 0
        slow = -1
        while i < len(s):
            if slow > 0  and s[i] == s[slow] == s[slow-1]:
                while i < len(s) and s[i] == s[slow]:
                    i += 1
                slow -= 2
            else:
                slow += 1
                s[i], s[slow] = s[slow], s[i]
                i += 1
        return s[:slow+1]

    # TEST
    if __name__ == "__main__":
        string = raw_input()
        res = removeDuplicates(list(string))
        print(res)

844. Backspace String Compare

  • Stack, Space : O(m + n)
  • Two Pointers, 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
23
24
25
class Solution(object):
    def backspaceCompare(self, S, T):
        p1, p2 = len(S)-1, len(T)-1
        while p1 >= 0 or p2 >= 0:
            back1 = 0
            while (p1 >= 0 and S[p1] == '#') or back1 > 0:
                back1 += 1 if S[p1] == '#' else -1
                p1 -= 1

            back2 = 0
            while (p2 >= 0 and T[p2] == '#') or back2 > 0:
                back2 += 1 if T[p2] == '#' else -1
                p2 -= 1

            if p1 < 0 and p2 < 0:
                return True
            elif p1 < 0 or p2 < 0:
                return False
            else:
                if S[p1] != T[p2]:
                    return False
                else:
                    p1 -= 1
                    p2 -= 1
        return p1 == p2
Share