As I am waiting for my work pass to be issued, I have some spare time to kill now. Therefore, I have been doing some Leetcode questions for fun and also encounter some interesting algo techniques such as Line Sweep Algorithm and Fenwick Tree. As I continue to solve them and encounter more interesting algos, I will update this page :)

Sliding Window

This technique is useful if you need to maintain a window (i.e. a contiguous sequence) with some conditions. Most questions that are related to substring, subarray, contiguous sequence of 1s usually can be solved using this technique (+ probably combination with other techniques such as 2 pointers).

Questions

1. Minimum Swaps to Group All 1’s Together II

Union Find Disjoint Set (UFDS)

UFDS is a data structure that models disjoint set. This data structure is very useful to solve questions that requires/enquires some connectivity. Usually, you need to model the problem as graph first before using UFDS to solve it.

Following is the implementation of UFDS with path-compression (there are more optimizations such as union by rank but this should be enough for most leetcode questions).

class UFDS:
    def __init__(self, n: int):
        self.parents = [i for i in range(n)]

    def find(self, i: int) -> int:
        if self.parents[i] != i:
            self.parents[i] = self.find(self.parents[i])

        return self.parents[i]

    def union(self, i: int, j: int) -> None:
        self.parents[self.find(i)] = self.find(j)

Questions

1. Check if the Rectangle Corner Is Reachable

String Matching

String matching by itself is not a technique, but a category of questions. However, in string matching questions, there are several algorithms and data structures that are very useful.

Trie (Prefix Tree)

Trie is very efficient in performing certain operations over large amount of strings dictionary. Some important queries are prefix matching, word search, and autocomplete. Following is simple implementation of Trie on Python

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


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        current_node = self.root
        for char in word:
            if char not in current_node.children:
                current_node.children[char] = TrieNode()
            current_node = current_node.children[char]
        current_node.is_word = True

    # For additional functionalities such as word search and prefix matching, you need to traverse the trie similar to the insert routine above 

Questions

1. Minimum Number of Valid Strings to Form Target I

Knuth-Morris-Pratt (KMP) string-searching algorithm

Traditionally, this algorithm is used to find occurrences of a “pattern” string of length M within a “text” string of length N. But, it can be modified to return a list of integers representing the longest prefix matching length in the pattern at index i. For example, if the pattern is “AAA” and the text is “ABBAAA” then it can return [1, 0, 0, 1, 2, 3] whereas the conventional KMP will just return [5] This algorithm can run in O(N + M) whereas naive string matching runs in O(N * M)

Useful resource: KMP Algorithm

Following is the implementation of modified KMP to return length of prefix matching

def kmp(pattern, text): 
    k = 0
    lps = [0] # longest prefix suffix aux array
    for i in range(1, len(pattern)): 
        while k and pattern[k] != pattern[i]: 
            k = lps[k - 1] 
        if pattern[i] == pattern[k]: 
            k += 1
        lps.append(k)

    k = 0
    prefix_matching = []
    for i, ch in enumerate(text): 
        while k and (k == len(pattern) or pattern[k] != ch): 
            k = lps[k - 1]
            
        if pattern[k] == ch: 
            k += 1
            
        # conventionally, if k == len(pattern), add them to the "matched" array
        prefix_matching.append(k)
        
    return prefix_matching

Questions

1. Minimum Number of Valid Strings to Form Target II

Interesting Questions and Methods

Printing a Singly Linked List in Reverse Order with Space Complexity < O(N)

I encounter this question during an interview and I thought it’s pretty unique. On the surface, it looks really trivial until you are asked to solve it with space complexity $< O(N)$. This question does not rely on any programming language features.

The idea is similar to sqrt decomposition. Suppose the length of the LL is $N$. If we divide the LL into $K$ parts, the space complexity to print the entire LL in reverse order is $N/K + K$

1. $N/K$ to print the LL using stack or recursion
2. $K$ to save the head pointers to each sublist

The big brain part is, note that $N/K + K$ is a convex function where $K > 0$. To find the optimal $K$, do $d(N/K + K)/dK = 0$ and solving this equation will give $K = \sqrt{N}$. Therefore, the total space complexity now is $N/\sqrt{N} + \sqrt{N} = 2 * \sqrt{N} = O(\sqrt{N})$ !! Really amazing right!!

Find the Largest Palindrome Divisible by K

This question comes up in LC weekly contest 411, and I thought it’s fascinating. My first instinct to solve this problem is to employ divisibility rule and try to pattern for each $k$. However, upon reading the hints, they mentioned that we can use string dp.

Let’s define $dp(i, mod)$ as whether starting from digit $i$ (and hence also digit $n - i - 1$ by definition of palindrome) with some remainder $mod$ is able to form palindrome number that is divisible by $k$. The interesting trick that I found from other people here, to get the biggest palindrome, we check the number recursively by iterating the number in strictly decreasing order. The core of the solution code can be seen below :)

...
choice = [None] * n


@cache
def dp(i, mod):
    if i == half_length:
        if mod == 0:
            return True
        return False

    digit_pos = set([i, n - 1 - i])
    for d in range(9, -1, -1):
        cur_mod = 0
        for pos in digit_pos:
            choice[pos] = d
            cur_mod += pos_mod[d][pos]

        if dp(i + 1, (cur_mod + mod) % k):
            return True

    return False


...

Fascinating!! To combine dp technique with some external state!!

Advanced Algorithms

I personally never encounter these algorithms in any software engineering interviews. But I thought it’s quite interesting, so I will publish it here too :)

Finding Articulation Point

Tarjan’s algo to find articulation points (a node where if it’s deleted from the graph $G$, will increase the connected components in $G$).

Questions

1. Minimum Number of Days to Disconnect Island

Reflection

To be honest, I used to be afraid to face technical interviews that involve leetcode questions. I used to believe that my algo is not as strong as the others. But most of the time, I just give up too easily and do not want to think. Whenever I encounter really hard questions, I just look at the editorial or answer key. I regret it and that’s why now I am determined to really practise my algos, while it is true that most of these algos won’t be useful at work, I believe that practising algo allows me think really systematically and to be a problem solver.