LeetCode

• Lists
  • [1,2,3] is a list not an array
    • implemented as list of arrays
  • a[i:j] - excludes j
  • a[i:j] - slicing creates a new list
• Sorting
  • .sort() - sort in increasing order, mutates
  • sorted(ar, key=lambda x: (x['age'], x['weight']))
    • sorts in increasing order
    • doesn't mutate
    • can do multi-key sorting

• heap: min heap

  import heapq
  heapq.heapify(h) # modifies h
  heapq.heappush(h, el) # updates h
  el = heapq.heappop(h)
  print(h[0]) # peak heap min value
  

• shuffle:

  import random
  random.shuffle(arr)
  print(arr)
  

• char code: ord('a') = 97
• code char: chr(97) = 'a'

• stack:

  ar= [1,2,3]
  ar.append(4)
  ar.pop() # -> 4
  

• queue

  • deque (pronounced deck) is implemented as doubly linked list of arrays

    from collections import deque
    q = deque()
    q.append(1)
    q.append(2)
    q.appendleft(0)
    q.popleft() # -> 0
    q.popleft() # -> 1
    

  • FIFO queue of fixed size can be implemented as circular buffer (not provided in python stdlib)

• Counter

  from collections import Counter
  c = Counter('abcdeabcdabcaba') # => Counter({'a': 5, 'b': 4, 'c': 3, 'd': 2, 'e': 1})
  # c is a dict
  c.most_common(3)
  c.update('abcd') # Adds to the counts
  c.subtract('abcd') # Subtracts from the counts
  

• Bisect

  import bisect
  ar = [1, 2, 3, 3, 3, 4, 5]
  # Find bisection location
  bisect.bisect_left(ar, 3)  # => 2 (left most 3's position)
  bisect.bisect_right(ar, 3) # => 5 (right most 3's position + 1)
  
  # Insert preseving sorting
  ar = ['a', 'aa', 'aaa']
  bisect.insort_left(ar, 'bb', key=len)
  # => ['a', 'bb', 'aa', 'aaa']
  bisect.insort_right(ar, 'bb', key=len)
  # => ['a', 'bb', 'aa', 'bb', 'aaa']
  

[neetcode.io]

If there is only one connected component, DFS/BFS starting from a node visits all nodes.

• Number of times we have to start DFS is the answer
• Can be done in O(V+E) time and O(V+E) space

Alternatively, can be done by using Disjoint Set Union (DSU).

• Take each vertex as a set
• Then for each edge do union of the vertex sets
• Count the number of times union was done. Say \(k\)
• \(|V| - k\) is the answer

If there are no loops and the number of connected components is 1.

• Can be done in O(V + E) time and O(V+E) space
  • Since E = V - 1 in a valid tree, if we abort in time, we do this in O(V) always.
• Start DFS from say node 0, abort if a cycle is found
• In the end check if all nodes are visited

Given two string s1 and s2 find the longest common substring.

• Can be done in \(O(mn)\) using DP
• Think of the recursive function that gives longest substring starting at index i1, i2
• The general problem for \(k\) strings can be done in \(O(\Pi_{k} l_k)\) using DP.

This can be done in \(O(m+n)\) or in general \(O(\sum_k l_k)\) time using Suffix Tree. But this is an advanced datastructure that we don't need to worry about for coding interviews.

[neetcode.io]

Given a string s find the longest substring which is a palindrome.

Approach 1:

• Can be done in \(O(n^2)\) time complexity and \(O(1)\) space complexity
• Think of center of the palindrom and expand from there.
  • \(2n - 1\) centers
  • max expansion of \(n\) for any of them

Approach 2:

Can also be done in O(n) using Manacher's algorithm. You can skip this.

Approach 3:

• Can also be done in O(n²) time complexity and O(n²) space complexity using DP.
• Think of the bruteforce algorithm, and notice the is_palindrome function
  • It is called \(O(n^2)\) times and take \(O(n)\) time always, so a total \(O(n^3)\) time.
  • But if we write it recursively and then memoize we can do this in \(O(n^2)\) time total.

Variation:

• Find the number of palindromes in a string

[neetcode.io]

Given \(n\) coins of some denominations make change for an amount \(t\) using least amount of coins. You can use coin of each denomination any amount of time.

• Can be done in \(O(nt)\) time and \(O(t)\) space.

[neetcode.io]

Where subsequence is defined as sequence obtained by deleting some or none of the characters but with order maintained.

• Can be done using DP in \(O(mn)\) time and \(O(mn)\) space.

• Space can be optimized to \(O(min(m,n))\)

  Look at how the dp table is looked up in the bottom up loop. You can make do with prev row and current row of table. And if you optimize it further, you can do with current row and one entry from previous row.

[neetcode.io]

Given an array of integers nums, find the subarray with the largest sum and return the sum. A subarray is a contiguous non-empty sequence.

• Greedy approach can do this in \(O(n)\) time and \(O(1)\) space.

  Just accumulate the numbers until the sum becomes less than 0. If it is less than 0, reset from this position.

Also,

• Can be done in \(O(n^3)\) using bruteforce: There are \(O(n^2)\) subsequence, whose sum takes \(O(n)\) each.
• Sum computation can be reused by DP table, thus complexity reduced to \(O(n^2)\) time and \(O(n^2)\) space.

Also,

• A better bruteforce does this in \(O(n^2)\)

Also,

• We can do this recursively. Think of how to use two mutually recursive functions max_subarray_starting_at(i), max_subarray_starting_after(i).
• And its corresponding DP does this in \(O(n)\) time and \(O(n)\) space.

Also,

• We can do this recursively. Think of the recursive function

  max(arr[i], arr[i] + max_subarray_starting_at(i+1))
  

  This takes \(O(n)\) space and time. But if you think about how to write this as a loop, this take \(O(n)\) time and \(O(1)\) space.

[neetcode.io]

Find the contiguous subarray that has the maximum product in an array.

• Naive bruteforce is \(O(n^3)\): There are \(O(n^2)\) subsequence whose product take \(O(n)\) to compute
• Better bruteforce is \(O(n^2)\): Take a starting position, and keep moving the end, the product can be updated as you move.
• Bruteforce approach can't directly converted to DP or recursive solution.

But there is a hidden substructure that can be exploited. Think of the following function:

def max_product_ending_at_i(i):
    return max(arr[i], arr[i] * max_product_ending_at_i(i-1), arr[i] * min_product_ending_at(i-1))

def min_product_ending_at_i(i):
    return max(arr[i], arr[i] * max_product_ending_at_i(i-1), arr[i] * min_product_ending_at(i-1))

solution = max([max_product_ending_at_i(i) for i in range(len(arr))])

The above functions give you the correct answer because the product so far is either positive, negative or zero.

Now you can convert this code to

• a simple loop with \(O(n)\) time complexity and \(O(1)\) space complexity
• a DP table with \(O(n)\) time complexity and \(O(n)\) space complexity

Cracking the Coding Interview - 6th.pdf: Page 84

Example: Numbers are randomly generated and stored into an (expanding) array. How would you keep track of the median?

import heapq as h
import random

arr = list(range(201)) # example input that is processes one by one
random.shuffle(arr)

bigger_heap = [] # items >= median, min heap
smaller_heap = [] # items <= median, max heap

# Base case
if arr[0] > arr[1]:
    bigger_heap.append(arr[0])
    smaller_heap.append(-arr[1])
else:
    bigger_heap.append(arr[1])
    smaller_heap.append(-arr[0])

for i in range(2, len(arr)):
    el = arr[i]

    if el >= bigger_heap[0]:
        h.heappush(bigger_heap, el)
    else:
        h.heappush(smaller_heap, -el)

    if len(bigger_heap) > len(smaller_heap):
        h.heappush(smaller_heap, -h.heappop(bigger_heap))
    elif len(bigger_heap) < len(smaller_heap):
        h.heappush(bigger_heap, -h.heappop(smaller_heap))

if len(bigger_heap) > len(smaller_heap):
    median = bigger_heap[0]
elif len(bigger_heap) < len(smaller_heap):
    median = -smaller_heap[0]
else:
    median = (-smaller_heap[0], bigger_heap[0])

print(median)

None

Algorithms > Mininum Spanning Tree

• Kruskal's Algorithm \(O(E\log E)\)
  • Start with all nodes as separate tree
  • Sort the edges by their weights (increasing order) \(O(E \log E)\)

  • For each edge decide to keep it or not. If it connects two different tree, keep the edge and merge the trees. \(O(E \alpha(E)) \approx O(E)\)

    Requires Union-Find (aka Disjoint-Set Union (DSU)):

    1. Method to find parent node of a node: To check for tree equality.

       Use path compression during parent finding:

       def find_parent(node):
           if node == parent[node]:
               return node
           return parent[node] = find_parent(parent[node])
       

    2. A way to merge trees.

       Merge by rank during tree merging:

       def union(node1, node2):
           p1 = find_parent(node1), p2 = find_parent(node2)
           if rank[p1] == rank[p2]:
               parent[p1] = p2
               rank[p2]++
           elif rank[p1] > rank[p2]:
               parent[p2] = p1
           else:
               parent[p1] = p2
       

    Path compression and rank based merging leads amortized O(1) complexity for both operations. (actually it is inverse ackerman \(\alpha(E)\) function. which is very slow. practically constant. <= 5)

• Prim's Algorithm

  • Start with a single node as the tree
  • Among the edges joining the tree to nodes not on the tree, find the minimum weight edge
  • Add the edge to the tree

  To implement:

  • Create a priority queue (min heap) of unvisted vertices with values as minimum distance from the tree
  • Assign infinity weight to all vertices except one of them
  • Pick min vertex from queue, and mark it as visited \(O(V \log V)\)

  • For all edges of that vertex

    • if the connected vertex is not visited, update the weight of the vertex

    This takes \(O(E \log V)\) (But if fibonacci heap is used decrease key is \(O(1)\). So this step takes just \(O(E)\))

  • Loop.

  Complexity: \(O((V + E) \log V)\) for binary heap, \(O(V\log V + E)\) for fibonacci heap.

• Floyd's algorithm aka Tortoise and hare alogrithm
• Take a slow pointer that moves one step at a time, take another fast pointer that moves two steps at a time
• If there is no loop, the fast pointer reaches the end
• If there is loop, then they meet once again inside the loop.

Proof:

1. Lets say the slow pointer just reached the start \(s\) of the loop of length \(l\), and the fast pointer is somewhere inside the loop say at distance \(k\) from the start of loop.

2. After some steps \(p <= l\) they meet because

   slow pointer will be at position \(s + p\) and fast pointer would be at \(s + (k + 2p mod l)\) both of these would be equal when:

   \begin{align*} & p = 2p + k & (mod\ l) \\ & p = -k & (mod\ l) \\ & p = l - k \end{align*}