Bridges and Articulation Points

Bridges and Articulation Points are important in Graph Theory because in real-world situations, they often hint weak points, bottlenecks or vulnerabilities in the graph. Therefore, it is important to be able to quickly find and detect where and when they occur.

Bridge

A Bridge (or cut-edge) in graph theory is any edge in a graph whose removal increases the number of connected components.

Lines with the red color are bridges because if you remove any of them, the graph is divided into two components.

Articulation Point

An Articulation Point (or cut-vertex) is any node in a graph whose removal increases the number of connected components.

Nodes marked with orange color are articulation points because if you remove any of them, graph is devided into two components.

Tarjan’s Algorithm

Tarjan’s Algorithm provides a very effective way to find these bridges and articulation points in linear time. We can explain this algorithm in 3 steps:

Step 1

Start at any node and do a Depth First Search (DFS) traversal, labeling nodes with an increasing id value as you go.

Step 2

Keep track the id of each node and the smallest low link value.

What is Low Link?

Low Link Value of a node is defined as the smallest id reachable from that node when doing a Depth First Search (DFS), including itself.

Initially, all low link values can be initialized to the each node id.

If we inspect node 1 and node 2, we will notice that there exist a path going from node 1 and node 2 to node 0.

So, we should update both node 1 and node 2 low link values to 0.

However, node 3, node 4 and node 5 are already at their optimal low link value because there are no other node they can reach with a smaller id.

For node 6, node 7 and node 8, there is a path from node 6, node 7 and node 8 to node 5.

So, we should update node 6, node 7 and node 8 low link values to 5.

Step 3

During the Depth First Search (DFS), bridges will be found where the id of node your edge is coming from is less than the low link value of the node your edge is going to.

Problem: Critical Connections in a Network

Input: n = 4, connections = [[0, 1], [1, 2], [2, 0], [1, 3]]
Output: [[1, 3]]
Explanation: [[3, 1]] is also accepted.

Solution with using Tarjan’s Algorithm

from collections import defaultdict
from typing import List


class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        def make_graph(connections):
            graph = defaultdict(list)
            for edge in connections:
                a, b = edge
                graph[a].append(b)
                graph[b].append(a)
            return graph

        graph = make_graph(connections)

        id, node, prev_node = 0, 0, -1  # at first there is no prev_node. we set it to -1
        ids = [0 for _ in range(n)]  # tracks ids of nodes
        low_links = [0 for _ in range(n)]  # tracks low link value (default value is the index)
        visited = [False for _ in range(n)]  # tracks DFS visit status

        bridges = []
        self.dfs(node, prev_node, bridges, graph, id, visited, ids, low_links)

        return bridges

    def dfs(self, node, prev_node, bridges, graph, id, visited, ids, low_links):
        visited[node] = True
        low_links[node] = id
        ids[node] = id
        id += 1

        for next_node in graph[node]:
            if next_node == prev_node:
                continue
            if not visited[next_node]:
                self.dfs(next_node, node, bridges, graph, id, visited, ids, low_links)
                low_links[node] = min(low_links[node], low_links[next_node])  # on callback, generates low link values
                if ids[node] < low_links[next_node]:  # found the bridge!
                    bridges.append([node, next_node])
            else:
                # tried to visit an already visited node, which may have a lower id than the current low link value
                low_links[node] = min(low_links[node], ids[next_node])

Time Complexity: O(E + V) –> One pass, linear time solution

Space Complexity: O(N)

References

1. Wikipedia, Robert Tarjan
2. Wikipedia, Tarjan’s strongly connected components algorithm
3. YouTube, William Fiset - Bridges and Articulation points - Graph Theory

Previous posts were about Sliding Window, Two Pointers, Fast & Slow Pointers, Merge Intervals, Cyclic Sort, In-place Reversal of a Linked List, Breadth First Search (BFS), Depth First Search (DFS), Two Heaps, Subsets, Modified Binary Search, Top K Numbers, K-way Merge, 0/1 Knapsack, Topological Sort, Bitwise XOR, Staircase and Palindromes patterns and today, we will introduce Longest Common Substring / Subsequence pattern which is very useful to solve Dynamic Programming problems involving longest / shortest common strings, substrings, subsequences etc.

If you need to refresh your knowledge of Dynamic Programming, you may want to check it before diving into more advanced problems.

Problem: Longest Common Subsequence

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Brute Force Solution

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not).

As a brute force solution, we can try all subsequences of text1 and text2 to find the longest one.

• if the characters text1[i] matches text2[j], we can recursively match the others.
• if the characters text1[i] and text2[j] does not match, we will make two recursive calls by skipping one character from each string.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        return self.longestCommonSubsequence_recursive(text1, text2, 0, 0)

    def longestCommonSubsequence_recursive(self, text1, text2, i, j):
        if i == len(text1) or j == len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1 + self.longestCommonSubsequence_recursive(text1, text2, i + 1, j + 1)

        return max(self.longestCommonSubsequence_recursive(text1, text2, i + 1, j),
                   self.longestCommonSubsequence_recursive(text1, text2, i, j + 1))

Time Complexity: O(2^N+M) where N and M are the lengths of two input strings.

Space Complexity: O(N + M) which is used to store the recursion stack.

Top-down Dynamic Programming with Memoization

We can use a two-dimensional array to store the already solved subproblems.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = [[-1 for _ in range(len(text2))] for _ in range(len(text1))]
        return self.longestCommonSubsequence_recursive(memo, text1, text2, 0, 0)

    def longestCommonSubsequence_recursive(self, memo, text1, text2, i, j):
        if i == len(text1) or j == len(text2):
            return 0
        if memo[i][j] == -1:
            if text1[i] == text2[j]:
                memo[i][j] = 1 + self.longestCommonSubsequence_recursive(memo, text1, text2, i + 1, j + 1)
            else:
                memo[i][j] = max(self.longestCommonSubsequence_recursive(memo, text1, text2, i + 1, j),
                                 self.longestCommonSubsequence_recursive(memo, text1, text2, i, j + 1))
        return memo[i][j]

Time Complexity: O(N * M) where N and M are the lengths of two input strings.

Space Complexity: O(N * M)

Bottom-up Dynamic Programming with Tabulation

Lets create our two dimensional array in a bottom-up fashion.

• if the characters text1[i] matches text2[j], the length of the common subsequence would be one plus the length of the common subsequence until the i-1 and j-1 indexes.
• if the characters text1[i] and text2[j] does not match, we take the longest sequence by skipping one character either from i^th string or j^th character from respective strings.

Our overall algorithm is;

if text1[i] == text2[j]:
    memo[i][j] = 1 + memo[i - 1][j - 1]
else:
    memo[i][j] = max(memo[i - 1][j], memo[i][j - 1])

and the solution is;

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = [[0 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]
        max_length = 0
        for i in range(1, len(text1) + 1):
            for j in range(1, len(text2) + 1):
                if text1[i - 1] == text2[j - 1]:
                    memo[i][j] = 1 + memo[i - 1][j - 1]
                else:
                    memo[i][j] = max(memo[i - 1][j], memo[i][j - 1])

                max_length = max(max_length, memo[i][j])
        return max_length

Time Complexity: O(N * M) where N and M are the lengths of two input strings.

Space Complexity: O(N * M)

How to identify?

Longest Common Substring / Subsequence pattern is very useful to solve Dynamic Programming problems involving longest / shortest common strings, substrings, subsequences etc.

Similar LeetCode Problems

• LeetCode 72 - Edit Distance [hard]
• LeetCode 97 - Interleaving String [hard]
• LeetCode 300 - Longest Increasing Subsequence [medium]
• LeetCode 1092 - Shortest Common Supersequence [hard]

Previous posts were about Sliding Window, Two Pointers, Fast & Slow Pointers, Merge Intervals, Cyclic Sort, In-place Reversal of a Linked List, Breadth First Search (BFS), Depth First Search (DFS), Two Heaps, Subsets, Modified Binary Search, Top K Numbers, K-way Merge, 0/1 Knapsack, Topological Sort, Bitwise XOR and Staircase patterns and today, we will introduce Palindromes pattern which is very useful to solve Dynamic Programming problems involving palindromes and palindromic strings, substrings, subsequences etc.

If you need to refresh your knowledge of Dynamic Programming, you may want to check it before diving into more advanced problems.

Problem: Longest Palindromic Subsequence

Input: "bbbab"
Output: 4
One possible longest palindromic subsequence is "bbbb".

Input: "cbbd"
Output: 2
One possible longest palindromic subsequence is "bb".

Brute Force Solution

A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as madam, racecar, or the number 10801.

Sentence-length palindromes may be written when allowances are made for adjustments to capital letters, punctuation, and word dividers, such as “A man, a plan, a canal, Panama!”, “Was it a car or a cat I saw?” etc.¹

As a brute force solution, we can try all subsequences of the given sequence. Starting from the beginning and the end of the sequence;

• if the elements at the beginning and the end are the same, we can increment the counter by 2 and make a recursive call to remaining subsequences
• we will skip one element either from the beginning or from the end o make two recursive calls for the remaining subsequence

If the first option applies then it will give us the length of Longest Palindromic Substring (LPS).

Otherwise, the length of Longest Palindromic Substring (LPS) will be the maximum number returned by the two recursive calls from the second option.

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        return self.longestPalindromeSubseq_recursive(s, 0, len(s) - 1)

    def longestPalindromeSubseq_recursive(self, s, start, end):
        if start > end:
            return 0

        # every sequence with one element is a palindrome of length 1
        if start == end:
            return 1

        # case 1: elements at the beginning and the end are the same
        if s[start] == s[end]:
            return 2 + self.longestPalindromeSubseq_recursive(s, start + 1, end - 1)

        # case 2: skip one element either from the beginning or the end
        subseq1 = self.longestPalindromeSubseq_recursive(s, start + 1, end)
        subseq2 = self.longestPalindromeSubseq_recursive(s, start, end - 1)

        return max(subseq1, subseq2)

Time Complexity: O(2^N) because we are making 2 recursive calls in the same function.

Space Complexity: O(N) which is used to store the recursion stack.

Top-down Dynamic Programming with Memoization

start and end are two changing values of our recursive function in the Brute Force Solution. So, we can store the results of all subsequences in a two-dimensional array to memoize them.

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        memo = [[-1 for _ in range(len(s))] for _ in range(len(s))]
        return self.longestPalindromeSubseq_recursive(memo, s, 0, len(s) - 1)

    def longestPalindromeSubseq_recursive(self, memo, s, start, end):
        if start > end:
            return 0

        # every sequence with one element is a palindrome of length 1
        if start == end:
            return 1

        if memo[start][end] == -1:
            # case 1: elements at the beginning and the end are the same
            if s[start] == s[end]:
                memo[start][end] = 2 + self.longestPalindromeSubseq_recursive(memo, s, start + 1, end - 1)
            else:
                # case 2: skip one element either from the beginning or the end
                subseq1 = self.longestPalindromeSubseq_recursive(memo, s, start + 1, end)
                subseq2 = self.longestPalindromeSubseq_recursive(memo, s, start, end - 1)
                memo[start][end] = max(subseq1, subseq2)

        return memo[start][end]

Time Complexity: O(N²) because memoization array, memo[len(s)][len(s)]. We will not have more than N*N subsequences.

Space Complexity: O(N² + N) == O(N²) because we used N² for memoization array and N for recursive stack.

Bottom-up Dynamic Programming with Tabulation

We can build our two-dimensional memoization array in a bottom-up fashion, adding one element at a time.

• if the element at the start and the end is matching, the length of Longest Palindromic Substring (LPS) is 2 plus the length of LPS till start+1 and end-1.
• if the element at the start does not match the element at the end, we will take the max of LPS by either skipping the element at start or end

So the overall algorith will be;

if s[start] == s[end]:
    memo[start][end] = 2 + memo[start + 1][end - 1]
else:
    memo[start][end] = max(memo[start + 1][end], memo[start][end - 1])

and the solution;

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        memo = [[0 for _ in range(len(s))] for _ in range(len(s))]

        # every sequence with one element is a palindrome of length 1
        for i in range(len(s)):
            memo[i][i] = 1

        for start in range(len(s) - 1, -1, -1):
            for end in range(start + 1, len(s)):
                # case 1: elements at the beginning and the end are the same
                if s[start] == s[end]:
                    memo[start][end] = 2 + memo[start + 1][end - 1]
                else:  # case 2: skip one element either from the beginning or the end
                    memo[start][end] = max(memo[start + 1][end], memo[start][end - 1])

        return memo[0][len(s) - 1]

Time Complexity: O(N²)

Space Complexity: O(N²) where N is the input sequence.

How to identify?

Palindromes pattern is very useful to solve Dynamic Programming problems involving palindromes and palindromic strings, substrings, subsequences etc.

Similar LeetCode Problems

• LeetCode 5 - Longest Palindromic Substring [medium]
• LeetCode 131 - Palindrome Partitioning [medium]
• LeetCode 647 - Palindromic Substrings [medium]
• LeetCode 1216 - Valid Palindrome III [hard] [premium]

References

1. Wikipedia, Palindrome

Previous posts were about Sliding Window, Two Pointers, Fast & Slow Pointers, Merge Intervals, Cyclic Sort, In-place Reversal of a Linked List, Breadth First Search (BFS), Depth First Search (DFS), Two Heaps, Subsets, Modified Binary Search, Top K Numbers, K-way Merge, 0/1 Knapsack, Topological Sort and Bitwise XOR patterns and today, we will introduce Staircase pattern which is very useful to solve Dynamic Programming problems involving minimum/maximum steps, jumps, stairs, fibonacci numbers etc. to reach a target.

If you need to refresh your knowledge of Dynamic Programming, you may want to check the Fibonacci Number Problem before diving into more advanced problems.

Problem: Climbing Stairs

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
--> 1 step + 1 step
--> 2 steps

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
--> 1 step + 1 step + 1 step
--> 1 step + 2 steps
--> 2 steps + 1 step

Brute Force Solution

At every step, we have two options: either climb 1 step or 2 steps.

class Solution:
    def climbStairs(self, n: int) -> int:
        # we don't take any steps, so there is only 1 way
        if n == 0:
            return 0
        # we can take one step to reach the end, and this is the only way
        if n == 1:
            return 1
        # we can take one step twice or take two steps to reach the end
        if n == 2:
            return 2

        # if we take one step, we are left with "n - 1" steps
        take1step = self.climbStairs(n - 1)
        # if we take two steps, we are left with "n - 2" steps
        take2steps = self.climbStairs(n - 2)

        return take1step + take2steps

Time Complexity: O(2^N) because we are making 2 recursive calls in the same function.

Space Complexity: O(N) which is used to store the recursion stack.

But can we do better? To be able to understand this, lets visualize the recursion stack.

We can clearly see from colors that there are lots of overlapping sub-problems that we don’t need to calculate them again and again.

Top-down Dynamic Programming with Memoization

We can use an array to store already solved sub-problems.

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0 for x in range(n+1)]
        return self.climbStairs_recursive(dp, n)
    
    def climbStairs_recursive(self, dp, n):
        # we don't take any steps, so there is only 1 way
        if n == 0:
            return 0
        # we can take one step to reach the end, and this is the only way
        if n == 1:
            return 1
        # we can take one step twice or take two steps to reach the end
        if n == 2:
            return 2
        
        if dp[n] == 0:
            # if we take one step, we are left with "n - 1" steps
            take1step = self.climbStairs_recursive(dp, n - 1)
            # if we take two steps, we are left with "n - 2" steps
            take2steps = self.climbStairs_recursive(dp, n - 2)
            
            dp[n] = take1step + take2steps
            
        return dp[n]

Time Complexity: O(N) because memoization array dp[n+1] stores the results of all sub-problems. We can conclude that we will not have more than n + 1 sub-problems.

Space Complexity: O(N) which is used to store the recursion stack.

Bottom-up Dynamic Programming with Tabulation

Let’s try to populate our dp[] array in a bottom-up fashion. As we see from the recursion stack visualization, each climbStairs(n) call is the sum of the two previous calls.

We can use this fact while populating our dp[] array.

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0 for x in range(n+1)]
        dp[0] = 1
        dp[1] = 1

        
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        
        return dp[n]

Time Complexity: O(N)

Space Complexity: O(N) which is used to store the recursion stack.

Memory Optimization

As we can see from the visualization of the recursive stack and other solutions, to be able to calculate the n, you need the value of last two combinations: n-1 and n-2.

These two values are enough and we don’t need to store all other past combinations.

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 0:
            return 0
        if n == 1:
            return 1
        if n == 2:
            return 2

        first = 1  # how many step possibilities there are with 1 stairs
        second = 2  # how many step possibilities there are with 2 stairs
        third = 0

        for _ in range(2, n):
            third = first + second
            first = second  # walk up first to second
            second = third  # walk up second to third
        return third

OR more shortly;

class Solution:
    def climbStairs(self, n: int) -> int:
        a = b = 1
        for _ in range(n):
            a, b = b, a + b
        return a

Time Complexity: O(N)

Space Complexity: O(1)

How to identify?

Staircase pattern is very useful to solve Dynamic Programming problems involving minimum/maximum steps, jumps, stairs, fibonacci numbers etc. to reach a target.

Similar LeetCode Problems

• LeetCode 62 - Unique Paths [medium]
• LeetCode 91 - Decode Ways [medium]
• LeetCode 509 - Fibonacci Number [easy]
• LeetCode 746 - Min Cost Climbing Stairs [easy]
• LeetCode 1155 - Number of Dice Rolls With Target Sum [medium]

Previous posts were about Sliding Window, Two Pointers, Fast & Slow Pointers, Merge Intervals, Cyclic Sort, In-place Reversal of a Linked List, Breadth First Search (BFS), Depth First Search (DFS), Two Heaps, Subsets, Modified Binary Search, Top K Numbers, K-way Merge, 0/1 Knapsack and Topological Sort patterns and today, we will introduce Bitwise XOR pattern which is very surprising to know the approaches that the XOR operator (^) enables us to solve certain problems.

If you are not familiar with binary computation and bit manipulation, I strongly recommend to read these two posts first:

1. Binary Computation and Bitwise Operators
2. Bit Manipulation Tricks

Problem: Single Number

Input: [2, 2, 1]
Output: 1

Input: [4, 1, 2, 1, 2]
Output: 4

Bitwise XOR Solution

Recall the following two properties of XOR:

1. It returns 0 if we take XOR of two same numbers.
2. It returns the same number if we XOR with 0.

So we can XOR all the numbers in the input; duplicate numbers will zero out each other and we will be left with the single number.

from typing import List


class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        num = 0
        for i in nums:
            num ^= i
        return num

Time Complexity: O(N) where N is the total number of elements in the input array.

Space Complexity: O(1)

Problem: Single Number III

Input:  [1, 2, 1, 3, 2, 5]
Output: [3, 5]

Bitwise XOR Solution

Let’s say num1 and num2 are the two single numbers. If we do XOR of all elements of the given array, we will be left with XOR of num1 and num2 as all other numbers will cancel each other because all of them appeared twice.

Since we now have XOR of num1 and num2, how can we find these two single numbers?

As we know that num1 and num2 are two different numbers, therefore, they should have at least one bit different between them!

If a bit in n1xn2 is 1, this means that num1 and num2 have different bits in that place. We can take any bit which is 1 in n1xn2 and partition all numbers in the given array into two groups based on that bit.

One group will have all those numbers with that bit set to 0 and the other with the bit set to 1. This will ensure that num1 will be in one group and num2 will be in the other.

We can take XOR of all numbers in each group separately to get num1 and num2, as all other numbers in each group will cancel each other.

from typing import List


class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:

        # XOR of all numbers in the given list
        n1xn2 = 0
        for num in nums:
            n1xn2 ^= num

        # rightmost bit which is 1
        rightmost_bit = 1
        while rightmost_bit & n1xn2 == 0:
            rightmost_bit = rightmost_bit << 1

        num1, num2 = 0, 0
        
        for num in nums:
            if num & rightmost_bit != 0:  # the bit is set
                num1 ^= num
            else:  # the bit is not set
                num2 ^= num

        return [num1, num2]

Time Complexity: O(N) where N is the total number of elements in the input array.

Space Complexity: O(1)

How to identify?

Knowing XOR properties well opens some surprising doors in your problem solving skills. To be able to identify XOR related problems are mostly coming from previous experiences. But if you need to eliminate the same numbers from an integer array, using Bit Manipulation Tricks is extremely helpful.

Similar LeetCode Problems

• LeetCode 137 - Single Number II [medium]

Previous posts were about Sliding Window, Two Pointers, Fast & Slow Pointers, Merge Intervals, Cyclic Sort, In-place Reversal of a Linked List, Breadth First Search (BFS), Depth First Search (DFS), Two Heaps, Subsets, Modified Binary Search, Top K Numbers, K-way Merge and 0/1 Knapsack patterns and today, we will introduce Topological Sort pattern which is very useful for finding a linear ordering of elements that have dependencies on each other.

Problem: Course Schedule

Input: 2, [[1, 0]] 
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Input: 2, [[1, 0], [0, 1]]
Output: false
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0, and to take course 0 
             you should also have finished course 1. So it is impossible.

Topological Sort Solution

The aim of topological sort is to provide a partial ordering among the vertices of the graph such that if there is an edge from U to V then U <= V, which means, U comes before V in the ordering.

1. Source: Any node that has no incoming edge and has only outgoing edges is called a source.
2. Sink: Any node that has only incoming edges and no outgoing edge is called a sink.
3. Topological ordering starts with one of the sources and ends at one of the sinks.
4. A topological ordering is possible only when the graph has no directed cycles, i.e. if the graph is a Directed Acyclic Graph (DAG). If the graph has a cycle, some vertices will have cyclic dependencies which makes it impossible to find a linear ordering among vertices.

To find the topological sort of a graph we can traverse the graph in a Breadth First Search (BFS) way.

a. Initialization

We will store the graph in Adjacency Lists, which means each parent vertex will have a list containing all of its children. We will do this using a Hash Table where the key will be the parent vertex number and the value will be a List containing children vertices.

To find the sources, we will keep a Hash Table to count the in-degrees (count of incoming edges of each vertex). Any vertex with 0 in-degree will be a source.

b. Build the graph and find in-degrees of all vertices

We will build the graph from the input and populate the in-degrees Hash Table.

c. Find all sources

All vertices with 0 in-degrees will be our sources and we will store them in a Queue.

d. Sort

For each source:

• Add it to the sorted list.
• Get all of its children from the graph.
• Decrement the in-degree of each child by 1.
• If a child’s in-degree becomes 0, add it to the sources Queue.

Repeat these steps, until the source Queue is empty.

from collections import deque
from typing import List


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        sorted_list = []

        if numCourses <= 0:
            return False

        # a. Initialization
        graph = {i: [] for i in range(numCourses)}  # adjacency list graph
        in_degree = {i: 0 for i in range(numCourses)}  # count of incoming edges

        # b. Build the graph
        for prerequisite in prerequisites:
            parent, child = prerequisite[0], prerequisite[1]
            graph[parent].append(child)  # put the child into it's parent's list
            in_degree[child] += 1

        # c. Find all sources
        sources = deque()
        for key in in_degree:
            if in_degree[key] == 0:
                sources.append(key)

        # d. Sort
        while sources:
            vertex = sources.popleft()
            sorted_list.append(vertex)
            for child in graph[vertex]:  # get the node's children to decrement their in-degrees
                in_degree[child] -= 1
                if in_degree[child] == 0:
                    sources.append(child)

        # if sorted_list does not contain all the courses, there is a cyclic dependency between courses
        # scheduling is not possible if there is a cyclic dependency
        return len(sorted_list) == numCourses

Time Complexity: O(V + E) where V is the total number of courses and E is the total number of prerequisites.

Space Complexity: O(V + E) since we are storing all of the prerequisites for each course in an adjacency list.

How to identify?

Topological Sort pattern is very useful for finding a linear ordering of elements that have dependencies on each other.

Scheduling or grouping problems which have dependencies between items are good examples to the problems that can be solved with using this technique.

Similar LeetCode Problems

• LeetCode 210 - Course Schedule II [medium]
• LeetCode 269 - Alien Dictionary [hard] [premium]
• LeetCode 310 - Minimum Height Trees [medium]

Previous posts were about Sliding Window, Two Pointers, Fast & Slow Pointers, Merge Intervals, Cyclic Sort, In-place Reversal of a Linked List, Breadth First Search (BFS), Depth First Search (DFS), Two Heaps, Subsets, Modified Binary Search, Top K Numbers and K-way Merge patterns and today, we will introduce 0/1 Knapsack pattern which is very useful to solve the famous Knapsack problem by using Dynamic Programming techniques.

We are going to use top-down Memoisation or bottom-up Tabulation technique to solve the problems efficiently.

Problem: Partition Equal Subset Sum

Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Brute Force Solution

A basic brute-force solution could be to try all combinations of partitioning the given numbers into two sets to see if any pair of sets has an equal sum.

This essentially transforms our problem to: Find a subset of the given numbers that has a total sum of sum / 2.

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        
        if s % 2 != 0:
            return False
        
        return self.can_partition_recursive(nums, s/2, 0)
    
    def can_partition_recursive(self, nums, sum, current_index):
        if sum == 0:
            return True
        
        if len(nums) == 0 or current_index >= len(nums):
            return False
        
        if nums[current_index] <= sum:
            if (self.can_partition_recursive(nums, sum - nums[current_index], current_index + 1)):
                return True
        
        return self.can_partition_recursive(nums, sum, current_index + 1)

Time Complexity: O(2^N) where N represents the total number.

Space Complexity: O(N) which will be used to store recursion stack.

Top-down Dynamic Programming with Memoization

We can use memoization to overcome the overlapping sub-problems. Since we need to store the results for every subset and for every possible sum, therefore we will be using a two-dimensional array to store the results of the solved sub-problems.

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        
        if s % 2 != 0:
            return False
        
        # initialize two-dimensional dp array, -1 for default
        dp = [[-1 for x in range(int(s/2)+1)] for y in range(len(nums))]
        
        if self.can_partition_recursive(dp, nums, int(s / 2), 0) == 1:
            return True  # return True for 1
        else:
            return False  # return False for 0
        
    def can_partition_recursive(self, dp, nums, sum, current_index):
        if sum == 0:
            return 1
        
        if len(nums) == 0 or current_index >= len(nums):
            return 0
        
        if dp[current_index][sum] == -1:  # if we have not processed this sub-problem
                if nums[current_index] <= sum:
                    if self.can_partition_recursive(dp, nums, sum - nums[current_index], current_index + 1) == 1:
                        dp[current_index][sum] = 1
                        return 1

                # recursive call after excluding the number at the current_index
                dp[current_index][sum] = self.can_partition_recursive(dp, nums, sum, current_index + 1)

        return dp[current_index][sum]

Time Complexity: O(N * S) where N represents the total numbers and S is the total sum of all numbers.

Space Complexity: O(N * S)

Bottom-up Dynamic Programming with Tabulation

Let’s try to populate our dp[][] array from the above solution by working in a bottom-up fashion with using tabulation dynamic programming technique.

Essentially, we want to find if we can make all possible sum with every subset. This means, dp[i][s] will be True if we can make the sum s from the first i numbers.

For each number at index i and sum s, we have these two options:

1. Exclude the number. In this case, we will see if we can get s from the subset excluding this number: dp[i-1][s]
2. Include the number if its value is not more than s. In this case, we will see if we can find a subset to get the remaining sum: dp[i-1][s-num[i]]

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        
        if s % 2 != 0:
            return False
        
        s = int(s / 2)
        dp = [[False for x in range(s + 1)] for y in range(len(nums))]
        
        # populate s = 0 columns
        for i in range(0, len(nums)):
            dp[i][0] = True
            
        # form a subset only when the required sum is equal to its value
        for j in range(1, s + 1):
            dp[0][j] = nums[0] == j
        
        # process all subsets for all sums
        for i in range(1, len(nums)):
            for j in range(1, s + 1):
                # if we can get the sum 'j' without the number at index 'i'
                if dp[i - 1][j]:
                    dp[i][j] = dp[i - 1][j]
                    
                # else if we can find a subset to get the remaining sum
                elif j >= nums[i]:
                    dp[i][j] = dp[i - 1][j - nums[i]]
        
        # the bottom-right corner will have our answer
        return dp[len(nums) - 1][s]

Time Complexity: O(N * S) where N represents the total numbers and S is the total sum of all numbers.

Space Complexity: O(N * S)

How to identify?

0/1 Knapsack pattern is very useful to solve the famous Knapsack problem by using Dynamic Programming techniques.

Knapsack problem is all about optimization. For example, given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

We are using top-down Memoisation or bottom-up Tabulation technique to solve these problems efficiently.

Similar LeetCode Problems

• LeetCode 474 - Ones and Zeroes [medium]

Previous posts were about Sliding Window, Two Pointers, Fast & Slow Pointers, Merge Intervals, Cyclic Sort, In-place Reversal of a Linked List, Breadth First Search (BFS), Depth First Search (DFS), Two Heaps, Subsets, Modified Binary Search and Top K Numbers patterns and today, we will introduce K-way Merge pattern which is very useful to solve the problems whenever we are given K sorted arrays, we can use a Heap to efficiently perform a sorted traversal of all the elements of all arrays.

We can push the smallest (first) element of each sorted array in a Min Heap to get the overall minimum. While inserting elements to the Min Heap we keep track of which array the element came from.

We can also remove the top element from the heap to get the smallest element and push the next element from the same array, to which this smallest element belonged, to the heap. We can repeat this process to make a sorted traversal of all elements.

Problem: Merge K Sorted Lists

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

K-way Merge Solution

We need to find the smallest element of all the input lists. To do so, we have to compare only the smallest element of all the lists first. Once we have the smallest element, we can put it in the merged list.

Following a similar pattern, we can then find the next smallest element of all the lists to add it to the merged list.

1. We can push the smallest (first) element of each sorted array in a Min Heap to get the overall minimum.
2. After this, we can take out the smallest (top) element from the heap and add it to the merged list.
3. After removing the smallest element from the heap, we can insert the next element of the same list into the heap.
4. We can repeat steps 2 and 3 to populate the merged list in sorted order.

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class ListNodeExtension(ListNode):
    def __lt__(self, other):
        return self.val < other.val


class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        ListNode.__lt__ = ListNodeExtension.__lt__
        min_heap = []
        for root in lists:
            if root is not None:
                heappush(min_heap, root)

        head = tail = ListNode(0)
        while min_heap:
            tail.next = heappop(min_heap)
            tail = tail.next
            if tail.next:
                heappush(min_heap, tail.next)

        return head.next

Time Complexity: O(N log K) where N is the total number of elements in all the K input arrays.

Space Complexity: O(K)

How to identify?

If the problem giving K sorted arrays and asks us to perform a sorted traversal of all the elements of all arrays, we need to think about K-way Merge pattern.

While solving the problems, we are going to use Heap data structure to keep track of all elements in K arrays.

Similar LeetCode Problems

• LeetCode 4 - Median of Two Sorted Arrays [hard]

Previous posts were about Sliding Window, Two Pointers, Fast & Slow Pointers, Merge Intervals, Cyclic Sort, In-place Reversal of a Linked List, Breadth First Search (BFS), Depth First Search (DFS), Two Heaps, Subsets and Modified Binary Search patterns and today, we will introduce Top K Numbers pattern which is very useful to solve the problems that asks us to find the top / smallest / frequent K elements among a given set.

We are going to use Heap data structure to keep track of K elements.

Problem: K-th Largest Element

Input: [3, 2, 1, 5, 6, 4] and k = 2
Output: 5

Input: [3, 2, 3, 1, 2, 4, 5, 5, 6] and k = 4
Output: 4

Top K Numbers Solution

The best data structure to keep track of top K elements is Heap.

If we iterate through the array one element at a time and keep kth largest element in a heap such that each time we find a larger number than the smallest number in the heap, we do two things:

1. Take out the smallest number from the heap
2. Insert the larger number into the heap

This will ensure that we always have top k largest numbers in the heap. We will use a min-heap for this;

from heapq import *


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        min_heap = []
        
        for i in range(k):
            heappush(min_heap, nums[i])
        
        for i in range(k, len(nums)):
            if nums[i] > min_heap[0]:
                heappop(min_heap)
                heappush(min_heap, nums[i])
            
        return min_heap[0]

Time Complexity: O(N log K).

Space Complexity: O(K)

How to identify?

If the problem asking us to find the top / smallest / frequent K elements among a given set, we need to think about Top K Numbers pattern.

While solving the problems, we are going to use Heap data structure to keep track of K elements.

Similar LeetCode Problems

• LeetCode 973 - K Closest Points to Origin [medium]

Previous posts were about Sliding Window, Two Pointers, Fast & Slow Pointers, Merge Intervals, Cyclic Sort, In-place Reversal of a Linked List, Breadth First Search (BFS), Depth First Search (DFS), Two Heaps and Subsets patterns and today, we will introduce Modified Binary Search pattern which is very useful to solve the problems whenever we are given a sorted Array or Linked List or Matrix, and we are asked to find a certain element.

This pattern describes an efficient way to handle all problems involving Binary Search.

Problem: Binary Search

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Binary Search Solution

1- Let’s assume that start is the first element and end is the last element in nums.

start = 0
end = len(nums) - 1

2- We need to find middle value, mid. An easy way to do it in Python is

mid = (start + end) // 2

For Java and C++, this equation will work for most cases, but when start or end is large, this equation will give us the wrong result due to integer overflow. To solve this problem, we will do our calculation a bit differently;

int mid = start + (end - start) / 2;

3- Next, we will see if the target value is equal to the number at mid value. If it is equal we return mid as the required index.

4- If target is not equal to number at index mid, there are two possibilities that we need to check:

• If target < nums[mid], then we can conclude that target will be smaller than all the numbers after index mid as the array is sorted in the ascending order. We can reduce our search to end = mid - 1.

• If target > nums[mid], then we can conclude that target will be greater than all numbers before index mid as the array is sorted in the ascending order. We can reduce our search to start = mid + 1.

from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        start, end = 0, len(nums) - 1
        while start <= end:
            mid = (start + end) // 2

            if target == nums[mid]:
                return mid

            if target < nums[mid]:
                end = mid - 1
            else:
                start = mid + 1
        return -1

Time Complexity: O(log N) where N is the total elements in the given array.

Space Complexity: O(1)

How to identify?

This approach is quite useful to solve the problems whenever we are given a sorted Array or Linked List or Matrix, and we are asked to find a certain element.

This pattern describes an efficient way to handle all problems involving Binary Search.

Similar LeetCode Problems

• LeetCode 744 - Find Smallest Letter Greater Than Target [easy]