Linear Structures - Overview

Posted on | In , |

List/Array

  • Max/Min subarray
    • prefix sum array: pre calculate the sum
    • track the current sum and max sum (min product and max product) + greedy
    • two pointers (visit each num at most twice)
    • use hash table to cache previous state (sum, index, count)

K-sum

  • Use dict
  • Sort + pointers
  • Skip duplications
  • Reduce to smaller problems
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
# 1. Two Sum
# hash table
# Time: O(N) Space: O(N)
# https://leetcode.com/problems/two-sum/description/
def twoSum(self, nums, target):
    dct = {}
    for i in range(len(nums)):
        if nums[i] in dct:
            return [dct.get(nums[i]), i]
        else:
            dct[target-nums[i]] = i
# Three Sum
# sort + two pointers
# time: O(N^2) space: O(1)
# https://leetcode.com/problems/3sum/description/
def threeSum(self, nums):
    if len(nums)<3:
        return []
    nums = sorted(nums)
    res = []
    s, l, r = 0, 1, len(nums) -1 
    for s in range(len(nums)-2):
        if s > 0 and nums[s] == nums[s-1]:
            continue
        l, r = s + 1, len(nums) - 1
        while l < r:
            curr_sum = nums[s] + nums[l] + nums[r]
            if curr_sum < 0:
                l += 1
            elif curr_sum > 0:
                r -= 1
            else:
                res.append([nums[s], nums[l], nums[r]])
                # Skip duplications
                while l<r and nums[l] == nums[l+1]:
                    l += 1
                while l<r and nums[r] == nums[r-1]:
                    r -= 1
                l, r = l + 1, r - 1
    return res
# Four Sum
# sort + two pointers (reduce to three sums)
# time: O(N^3) space: O(1)
# https://leetcode.com/problems/4sum/description/
def fourSum(self, nums, target):
    # time O(N^3)
    nums = sorted(nums)
    res = []
    if len(nums)<4:
        return []
    for l1 in range(len(nums)-3):
        # skip dup in l1
        if l1 > 0 and nums[l1] == nums[l1-1]:
            continue
        for r1 in reversed(range(l1+3, len(nums))): 
            # skip dup in r1
            if r1 < len(nums) - 1 and nums[r1] == nums[r1+1]:
                continue
            l2, r2 = l1 + 1, r1 - 1
            remain = target - nums[l1] - nums[r1]
            while l2 < r2:
                curr_sum = nums[l2] + nums[r2]
                if curr_sum < remain:
                    l2 += 1
                elif curr_sum > remain:
                    r2 -= 1
                else:
                    res.append([nums[l1], nums[l2], nums[r2], nums[r1]])
                    # skip dup in l2, r2 (use while to skip all duplications)
                    while l2 < r2 and nums[l2] == nums[l2 + 1]:
                        l2 += 1
                    while l2 < r2 and nums[r2] == nums[r2 - 1]:
                        r2 -= 1
                    l2, r2 = l2 + 1, r2 - 1
    return res

Hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# https://leetcode.com/problems/minimum-window-substring/description/
def minWindow(self, s, t):
    target = Counter(t)
    cnt = len(t)
    start = 0
    res_s, res_e = 0, len(s) + 1
    
    for i in range(len(s)):
        if target[s[i]] > 0:
            cnt -= 1
        target[s[i]] -= 1
        
        # checkpoint when cnt == 0, remove as many as possible (greedy)
        while cnt == 0:
            if i - start < res_e - res_s:
                res_s, res_e = start, i
            if target[s[start]] == 0:
                cnt += 1
            target[s[start]] += 1
            start += 1
    if res_e - res_s + 1 > len(s):
        return ''
    else:
        return ''.join(s[res_s:res_e+1])

Subarray

  • Make sure to use different kind of prefix sum array

    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
    #1 https://leetcode.com/problems/maximum-subarray/description/
    def maxSubArray(self, nums):
        max_sum = nums[0]
        curr_sum = nums[0]
        
        for i in range(1, len(nums)):
            curr_sum = max(nums[i], curr_sum + nums[i])
            max_sum = max(max_sum, curr_sum)
        
        return max_sum         
    # 2.
    def maxProduct(self, nums):
        max_product = nums[0]
        curr_min = nums[0]
        curr_max = nums[0]
        
        for i in range(1, len(nums)):
            a = nums[i] * curr_min
            b = nums[i] * curr_max
            c = nums[i]
            curr_min = min(min(a,b), c)
            curr_max = max(max(a,b), c)
            max_product = max(max_product, curr_min, curr_max)
        return max_product
    # 3 use hash + prefix sum O(n) O(n)
    def maxSubArrayLen(self, nums, k):
        res = 0
        sums = 0
        dct = {}
        for i, num in enumerate(nums):
            if sums not in dct:
                dct[sums] = i
            sums += num
            if sums-k in dct:
                res = max(res, i-dct[sums-k] + 1)
        return res
    # https://leetcode.com/problems/range-addition/description/
    def getModifiedArray(self, length, updates):
        # range cache O(N + K) O(1)
        res = [0] * length
        for l, r, add in updates:
            res[l] += add
            if r + 1 <= length - 1:
                res[r+1] -= add
        
        curr_sum = 0
        for i in range(length):
            curr_sum += res[i]
            res[i] = curr_sum
        return res

  • Max rectangle

Linked List

https://www.jianshu.com/p/490cb181946f

  • fast, slow pointer (cyclic detection, find middle node, find intersection of linked list)
  • reverse linked list to simplify problems
  • create dummy node pointing to the head
  • use prev node to reverse / track
  • list with index 0 ~ n-1 can be treated as linked list (next method: nums[curr_index])
  • add tmp link to reduce problems (intersection -> detect cycle)
  • use dict to achieve O(1) read/delete time for node
    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
    # use prev Node
    # Time: O(N) Space: O(1)
    def reverseList(self, head):
        prev, curr = None, head
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        return prev
    # fast - slow pointers
    # Time O(N) Space O(1)
    def detectCycle(self, head):
        if not head or not head.next:
            return
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                slow2 = head
                while slow != slow2:
                    slow = slow.next
                    slow2 = slow2.next
                return slow
        return
    # remove element
    # 第一种是向后比较结点，发现重复就删掉。因为可能会删掉后面的结点，所以一定要注意cur的判空条件。当正常遍历时，cur可能为空，当删掉了后面结点时cur.next可能为空，都要判断。
    if node.next.val == val:
        node.next = node.next.next

Collections of helper functions

  1. reversed linked list

stack

  • in_stack and out_stack to build queue
  • stack to check valid syntax, brackets, …
  • append index and sign to stack

queue

  • one queue to build stack (popleft all but the last one)

deque

  • stack + queue 
    1
    2
    3
    from collections import deque
    dq = deque([])
    # could specify the length of deque

Questions Review

Intervals:

Evidently, two events [s1, e1) and [s2, e2) do not conflict if and only if one of them starts after the other one ends: either e1 <= s2 OR e2 <= s1. By De Morgan’s laws, this means the events conflict when s1 < e2 AND s2 < e1.

https://leetcode.com/problems/my-calendar-i/description/
https://leetcode.com/problems/my-calendar-ii/description/
https://leetcode.com/problems/my-calendar-iii/description/