Array

Kadane’s Algorithm

how to find the maximum sum of a contiguous subarray in an array of integers.

# Brute Force
def max_subarray_sum(arr):
    max_sum = float('-inf')
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            current_sum = sum(arr[i:j+1])
            max_sum = max(max_sum, current_sum)
    return max_sum

The complexity of this algorithm is O(n^3) because we have two nested loops and the sum function takes O(n) time.

# sliding window O(n)
def maxSubArray(self, nums: List[int]) -> int:
    left = 0
    right = 0
    n = len(nums)
    cur = nums[left]
    m_sum = cur
    while True:
        if cur < 0:
            left = right + 1
            right = left
            cur = 0
            if left >= n:
                break
            cur = nums[left]
        else:
            right += 1
            if right >= n:
                break
            cur += nums[right]
        if cur > m_sum:
            m_sum = cur
    return m_sum

But it is not very elegant.

# Kadane's Algorithm O(n)
def kadanes(nums):
  max_sum = nums[0]
  cur_sum = 0
  for n in nums:
    cur_sum = max(0, cur_sum)
    cur_sum += n
    max_sum = max(max_sum, cur_sum)
  return max_sum

Kadane’s algorithm has a big overlape with the sliding window. but if we want to get he left and right pointers for the maximum subarray, we need to use the sliding window one to track the left and right pointers.

Sliding Window

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Get the max element for each window. leetcode 239

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    max_sw = []
    left, right = 0, 0
    n = len(nums) 
    while right < n:
        e_r = nums[right]
        if e_r in win:
            win[e_r] += 1
        else:
            win[e_r] = 1
        if right - left + 1 == k:
            max_sw.append(max(win))
            e_l = nums[left]
            if win[e_l] > 1:
                win[e_l] -= 1
            else:
                del win[e_l]
            left += 1
        right += 1
    return max_sw

But this one will have O(nk), if n and k are both big, we will have time limit issue.

dq = deque()   # stores indices
result = []
for i in range(len(nums)):
    # 1️⃣ Remove indices out of window
    if dq and dq[0] == i - k:
        dq.popleft()
    # 2️⃣ Maintain decreasing order
    while dq and nums[dq[-1]] < nums[i]:
        dq.pop()
    # 3️⃣ Add current index
    dq.append(i)
    # 4️⃣ Window formed
    if i >= k - 1:
        result.append(nums[dq[0]])
return result

We put element in order in the deque and when a new element comes in, we remove all smaller elements before it. O(n), we remove max n element, so keep order do not effect the complexity.

Two pointers

sliding window is a subset of two pointers and in two points, we concentrate more on the two elements on each side. There are questions like Check if an array is a palindrome, two sum, target sum.

Q1

Given a sorted of integers, return the indixes of two elements (in different positions) that sum up to the target value. Assume there is exactly one solution.

def targerSum(nums, target):
  L,R = 0, len(nums) - 1
  while L < R:
    if nums[L] + nums[R] > target:
      R -= 1
    elif nums[L] + nums[R] < target:
      L += 1
    else:
      return [L, R]

Prefix Sums

Prefix: sublist that start at the beginning. prefix sum and prefix product can be presented by the recursive pattern. Postfix is like the prefix and they are two sides of the same coin.

Prefix sum can used to optimise the calculation. For example to calculate the sum of an subarray. we can

class prefix_sum:
    def __init__(self, nums):
        self.prefix = []
        total = 0
        for n in nums:
            total += n
            self.prefix.append(total)
    
    def subsum(self, left, right):
        pre_right = self.prefix[right]
        pre_left = self.prefix[left-1] if left > 0 else 0
        return pre_right - pre_left

Q1

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation. Leetcode 238

def productExceptSelf(self, nums: List[int]) -> List[int]:
    n = len(nums)
    prefix, suffix = [1], [1]
    result = []
    for i in range(n-1):
        prefix.append(prefix[-1] * nums[i])
        suffix.append(suffix[-1] * nums[n-1-i])
    for i in range(n):
        result.append(prefix[i] * suffix[n-i-1])
    return result

# Or we can allocate the memory first
def productExceptSelf(self, nums: List[int]) -> List[int]:
    result = [1] * len(nums)
    right, left = 1, 1
    for i in range(len(nums)):
        result[i] *= left
        left *= nums[i]
    for i in range(len(nums)-1, -1, -1):
        result[i] *= right
        right *= nums[i]
    return result 

Linked List

Fast and Slow Pointers

It is also called Floyd’s tortoise and hare algorithm. We can use it to find the middle of a linked list, to detect if there is a cycle in a linked list and to find the entry point of the cycle.

Q1

Find the middle of a linked list. If there are two middle nodes, return the second middle node.

def middle_of_list(head):
    # odd and even case are both covered by this algorithm, when there are two middle nodes, the slow pointer will jump over the first middle node and stop at the second middle node.
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Q2

Given head, the head of a linked list, determine if the linked list has a cycle in it. The basic method is to use a set to store the visited nodes pointer hash, if we visit a node that is already in the set, then there is a cycle. But this method has O(n) space complexity. We can use fast and slow pointers to achieve O(1) space complexity.

The idea is that if there is a cycle, the fast pointer will eventually catch up with the slow pointer. If there is no cycle, the fast pointer will reach the end of the list.

Will they meet when there is a cycle? Yes, they will meet. The fast pointer moves twice as fast as the slow pointer, so it will eventually catch up with the slow pointer. And they can be proved by the mathematical induction. If they start att the same position $$ (1 + 2\times t) \mod n == (1 + t) \mod n $$ These two quation represent the position of the fast pointer and the slow pointer after t steps. When they meet, they will be at the same position, so we can solve this equation to find the value of t. t is the times of step and n is the length of the cycle. We can find the they will meet at the t is the multiple of n, which means they will meet at the same position after n steps.

def has_cycle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

Q3

Given head, the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

flowchart LR
    1((1:Head)) --> 2
    2 --> 3[3:entry point]
    3 --> 4
    4 --> 5((5:meet point))
    5 --> 6
    6 --> 7
    7 --> 3

    1 -. p .-> 3
    3 -. n-k .-> 5
    5 -. k .-> 3

From head to entry point, we have p steps. The circle length is n. From entry point to meet point, we have k steps. So fro meet point to entry point again, we have n-k steps. When they meet, the fast pointer has moved 2(p+k) steps, and the slow pointer has moved p+k steps. So when faster pointer and slow pointer meet we have: $$ 2(p+n-k) = p + n - k + n*m $$ Where m is the times of cycle. we ahve $$ p - k = n(m-1) $$

if m is 1, we have p = k, which means the entry point is the meet point.

so we can then put another pointer at the head of the list, and move it and the slow pointer one step at a time, they will meet at the entry point of the cycle.

def find_cycle_entry(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    if not fast or not fast.next:
        return None
    entry = head
    while entry != slow:
        entry = entry.next
        slow = slow.next
    return entry

Trie (Prefix Tree)

The complexity of searching word or inserting word are both O(1). This can be achieved by using a hash map. But for Prefix Tree, we can also search with prefix with O(1) time complexity.

This algorithm is very useful for autocomplete and spell checker. It can also be used to solve some problems like word search, word search II, etc.

Basic a trie is a tree of characters, each node represents a character and the path from the root to a node represents a word. We can use a hash map to store the children of each node. For English, each node will have at most 26 children.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        curr.word = True

    def search(self, word):
        curr = self.root
        for c in word:
            if c not in curr.children:
                return False
            curr = curr.children[c]
        return curr.word
    
    def startsWith(self, prefix):
        curr = self.root
        for c in prefix:
            if c not in curr.children:
                return False
            curr = curr.children[c]
        return True