AlgoMonster - Templates

Question 1

What is the template for Backtracking (without pruning)

Answer 1

function dfs(start_index, path):
if is_leaf(start_index):
report(path)
return
for edge in get_edges(start_index):
path.add(edge)
dfs(start_index + 1, path)
path.pop()

Time complexity: O(N) , where N = number of nodes in the tree
Space complexity: O(log N) which is about the height of the tree.

Question 2

String Permutations.
Given a string, such as “abcd”, return an array of all permutations of that string.

Answer 2

Use the backtracking template with pruning. Need to pass 2 extra args. Used and res

class Solution:
def string_permutations(self, s: str) -> List[str]:
def dfs(start_index, path, used, res):
if start_index == len(s):
res.append(‘‘.join(path))
return

        for i, c in enumerate(s):
            # pruning
            if used[i]:
                continue
            # add letter to permutation and mark as used
            path.append(c)
            used[i] = True
            dfs(start_index + 1, path, used, res)
            path.pop()
            used[i] = False
    
    res = []
    letter_usage = [False] * len(s)
    dfs(0, [], letter_usage, res)
    return res

Question 3

Binary Search template ?

Answer 3

def binary_search(arr: List[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    while left <= right:  # <= because left and right could point to the same element, < would miss it
        mid = (left + right) // 2 # double slash for integer division in python 3, we don't have to worry about integer `left + right` overflow since python integers can be arbitrarily large
        # found target, return its index
        if arr[mid] == target:
            return mid
        # middle less than target, discard left half by making left search boundary `mid + 1`
        if arr[mid] < target:
            left = mid + 1
        # middle greater than target, discard right half by making right search boundary `mid - 1`
        else:
            right = mid - 1
    return -1 # if we get here we didn't hit above return so we didn't find target

Question 4

Find the first True in an array of booleans. Any False(s) will start at the beginning of array.

Answer 4

In the whilte loop, have “if” statement that checks for the condition you want. If condition is met, set the index variable and set “right” pointer to (mid-1)
~~~
def find_boundary(arr: List[bool]) -> int:
left, right = 0, len(arr) - 1
boundary_index = -1

while left <= right:
    mid = (left + right) // 2
    if arr[mid]:
        boundary_index = mid
        right = mid - 1
    else:
        left = mid + 1

return boundary_index ~~~

Question 5

Monotonic template

Answer 5

Define the “is_feasible” function. If condition is met, set the index = mid and set “right = (mid - 1)”.
~~~
def binary_search(arr: List[int], target: int) -> int:
left, right = 0, len(arr) - 1
first_true_index = -1
while left <= right:
mid = (left + right) // 2
if feasible(mid):
first_true_index = mid
right = mid - 1
else:
left = mid + 1

return first_true_index ~~~

Question 6

Backtracking 2 template and when does it apply?

Answer 6

This problem is good for aggregating results (bubbling up) such as:

Word Break
~~~
function dfs(start_index, […additional states]):
if is_leaf(start_index):
return 1
ans = initial_value
for edge in get_edges(start_index, […additional states]):
if additional states:
update([…additional states])
ans = aggregate(ans, dfs(start_index + len(edge), […additional states]))
if additional states:
revert([…additional states])
return ans

~~~

Question 7

Word Break problem - hint use backtracking 2 template

Answer 7

def word_break(target, words):
    def dfs(start_index):
        if start_index == len(target): # we have constructed the entire target target
            return True

        ans = False
        for word in words:
            if target[start_index:].startswith(word):
                ans = ans or dfs(start_index + len(word))

        return ans

    return dfs(0)

Question 8

Num ways to decode a message
We have a message consisting of digits 0-9 to decode. Letters are encoded to digits by their positions in the alphabet

Given a non-empty string of digits, how many ways are there to decode it?

Input: “18”
Output: 2
Explanation: “18” can be decoded as “AH” or “R”

Input: “123”
Output: 3
Explanation: “123” can be decoded as “ABC”, “LC”, “AW”

HINT: use memoization

Answer 8

def decode_ways(digits):
    memo = {}
    def dfs(start_index, memo):
        if start_index in memo:
            return memo[start_index]
        if start_index == len(digits):
            return 1

        ways = 0
        # can't decode string with leading 0
        if digits[start_index] == '0':
            return ways
        # decode one digit
        ways += dfs(start_index + 1, memo)
        # decode two digits
        if 10 <= int(digits[start_index: start_index + 2]) <= 26:
            ways += dfs(start_index + 2, memo)
        
        memo[start_index] = ways
        return ways

    return dfs(0, memo)

if \_\_name\_\_ == '\_\_main\_\_':
    digits = input()
    res = decode_ways(digits)
    print(res)

Question 9

DFS on Binary Tree template

Answer 9

def dfs(root, target):
    if root is None:
        return None
    if root.val == target:
        return root
    left = dfs(root.left, target)
    if left is not None:
        return left
    return dfs(root.right, target)

Question 10

Monotonic Stack

Answer 10

def mono_stack(insert_entries):
    stack = []
    for entry in insert_entries:
        while stack and stack[-1] <= entry:
            stack.pop()
            # Do something with the popped item here
        stack.append(entry)

Example: Sliding Window Max. Given a window of size K. Find the max value each time the window moves.
~~~
def sliding_window_maximum(nums: List[int], k: int) -> List[int]:
q = deque() # stores indices
res = []
for i, cur in enumerate(nums):
while q and nums[q[-1]] <= cur:
q.pop()
q.append(i)
# remove first element if it’s outside the window
if q[0] == i - k:
q.popleft()
# if window has k elements add to results (first k-1 windows have < k elements because we start from empty window and add 1 element each iteration)
if i >= k - 1:
res.append(nums[q[0]])

return res ~~~

Question 11

Sliding Window Fixed

Answer 11

def sliding_window_fixed(input, window_size):
    ans = window = input[0:window_size]
    for right in range(window_size, len(input)):
        left = right - window_size
        remove input[left] from window
        append input[right] to window
        ans = optimal(ans, window)
    return ans

Example usage: Max sum subset of window K

def subarray_sum_fixed(nums, k):
    window_sum = 0
    for i in range(k):
        window_sum += nums[i]
    largest = window_sum
    for right in range(k, len(nums)):
        left = right - k
        window_sum -= nums[left]
        window_sum += nums[right]
        largest = max(largest, window_sum)
    return largest

Question 12

Sliding Window Flex, Find Longest Subset

Answer 12

def sliding_window_flexible_longest(input):
    initialize window, ans
    left = 0
    for right in range(len(input)):
        append input[right] to window
        while invalid(window):        # update left until window is valid again
            remove input[left] from window
            left += 1
        ans = max(ans, window)        # window is guaranteed to be valid here
    return ans

Example:
Given input nums = [1, 6, 3, 1, 2, 4, 5] and target = 10, then the longest subarray that does not exceed 10 is [3, 1, 2, 4]

def subarray_sum_longest(nums, target):
    window_sum, length = 0, 0
    left = 0
    for right in range(len(nums)):
        window_sum += nums[right]
        while window_sum > target:
            window_sum -= nums[left]
            left += 1
        length = max(length, right-left+1)
    return length

if \_\_name\_\_ == '\_\_main\_\_':
    nums = [int(x) for x in input().split()]
    target = int(input())
    res = subarray_sum_longest(nums, target)
    print(res)

Answer 13

def sliding_window_flexible_shortest(input):
    initialize window, ans
    left = 0
    for right in range(len(input)):
        append input[right] to window
        while valid(window):
            ans = min(ans, window)      # window is guaranteed to be valid here
            remove input[left] from window
            left += 1
    return and

Example:
Given input nums = [1, 4, 1, 7, 3, 0, 2, 5] and target = 10,
Find the smallest window with the sum >= 10 is [7, 3] with length 2.
~~~
def subarray_sum_shortest(nums, target):
window_sum, length = 0, len(nums)
left = 0
for right in range(len(nums)):
window_sum += nums[right]
while window_sum >= target:
length = min(length, right-left+1)
window_sum -= nums[left]
left += 1
return length
~~~

Question 14

Topological Sort template

Answer 14

Topo Sort basically does the following:
Initialize a hashmap to store the in-degrees.
Go through the nodes, count the in-degree of each node.
Push the nodes with 0 in-degree into the queue.
Pop each node from the queue, subtract 1 from the in-degree of each of its neighbors (each node it points to).
If a node’s in-degree drops to 0, then push it into the queue.
repeat until the queue is empty. If any nodes remain unprocessed, then there must be a cycle.

def find_indegree(graph):
    indegree = { node: 0 for node in graph }  # dict
    for node in graph:
        for neighbor in graph[node]:
            indgree[neighbor] += 1
    return indegree

def topo_sort(graph):
    res = []
    q = deque()
    indegree = find_indegree(graph)
    for node in indegree:
        if indegree[node] == 0:
            q.append(node)
    while len(q) > 0:
        node = q.popleft()
        res.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                q.append(neighbor)
    return res if len(graph) == len(res) else None

def task_scheduling(tasks: List[str], requirements: List[List[str]]) -> List[str]:
    graph = {t: [] for t in tasks}
    for a, b in requirements:
        graph[a].append(b)
    return topo_sort(graph)

Question 15

Trie template

Answer 15

class Node:
    def \_\_init\_\_(self, value):
        self.value = value
        self.children = {}

    def insert(self, s, idx):
        # idx: index of the current character in s
        if idx != len(s):
            self.children.setdefault(s[idx], Node(s[idx]))
            self.children.get(s[idx]).insert(s, idx + 1)

Question 16

Auto complete using a Trie

Answer 16

The purpose of the frequency variable is to determine if the current node represents the end of a word.
~~~
class Trie:
def __init__(self):
self.children = {} # Dictionary to hold child nodes
self.freq = 0 # Frequency counter for words/prefixes

def insert(self, word):
    node = self
    for char in word:
        # If character is not a child, add it
        if char not in node.children:
            node.children[char] = Trie()
        node = node.children[char]
        node.freq += 1  # Increase frequency for this prefix

# Returns 0 if not in the trie, returns 1 or greater if in the trie.
def query(self, prefix):
node = self
for char in prefix:
# If prefix does not exist in trie, return 0
if char not in node.children:
return 0
node = node.children[char]
return node.freq # Return the frequency of this prefix
~~~

Question 17

Union Find

Answer 17

class UnionFind:
    def \_\_init\_\_(self):
        self.id = {}

    def find(self, x):
        y = self.id.get(x, x)
        if y != x:
            self.id[x] = y = self.find(y)
        return y

    def union(self, x, y):
        self.id[self.find(x)] = self.find(y)