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.
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.
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 provides a very effective way to find these bridges and articulation points in linear time. We can explain this algorithm in 3 steps:
Start at any node and do a Depth First Search (DFS) traversal, labeling nodes with an increasing id
value as you go.
Keep track the id
of each node and the smallest low link value.
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.
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.
LeetCode 1192 - Critical Connections in a Network [hard]
There are n
servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b]
represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.
A critical connection is a connection that, if removed, will make some server unable to reach some other server.
Return all critical connections in the network in any order.
Example 1:
Input: n = 4, connections = [[0, 1], [1, 2], [2, 0], [1, 3]]
Output: [[1, 3]]
Explanation: [[3, 1]] is also accepted.
Constraints:
n
<= 10^{5}n-1
<= connections.length
<= 10^{5}connections[i][0] != connections[i][1]
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)
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.
LeetCode 1143 - Longest Common Subsequence [medium]
Given two strings text1
and text2
, return the length of their longest common subsequence.
A common subsequence of two strings is a subsequence that is common to both strings. If there is no common subsequence, return 0.
Example 1:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
Example 2:
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.
Example 3:
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
Constraints:
text1.length
<= 1000text2.length
<= 1000A 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.
text1[i]
matches text2[j]
, we can recursively match the others.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.
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)
Lets create our two dimensional array in a bottom-up fashion.
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.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)
Longest Common Substring / Subsequence pattern is very useful to solve Dynamic Programming problems involving longest / shortest common strings, substrings, subsequences etc.
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.
LeetCode 516 - Longest Palindromic Subsequence [medium]
Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "bbbab"
Output: 4
One possible longest palindromic subsequence is "bbbb".
Example 2:
Input: "cbbd"
Output: 2
One possible longest palindromic subsequence is "bb".
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.^{1}
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 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.
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^{2}) because memoization array, memo[len(s)][len(s)]
. We will not have more than N*N subsequences.
Space Complexity: O(N^{2} + N) == O(N^{2}) because we used N^{2} for memoization array and N for recursive stack.
We can build our two-dimensional memoization array in a bottom-up fashion, adding one element at a time.
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
.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^{2})
Space Complexity: O(N^{2}) where N is the input sequence.
Palindromes pattern is very useful to solve Dynamic Programming problems involving palindromes and palindromic strings, substrings, subsequences etc.
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.
LeetCode 70 - Climbing Stairs [easy]
You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note:
Given n will be a positive integer.
Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
--> 1 step + 1 step
--> 2 steps
Example 2:
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
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.
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.
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.
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)
Staircase pattern is very useful to solve Dynamic Programming problems involving minimum/maximum steps, jumps, stairs, fibonacci numbers etc. to reach a target.
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:
LeetCode 136 - Single Number [easy]
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2, 2, 1]
Output: 1
Example 2:
Input: [4, 1, 2, 1, 2]
Output: 4
Recall the following two properties of XOR:
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)
LeetCode 260 - Single Number III [medium]
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
Example:
Input: [1, 2, 1, 3, 2, 5]
Output: [3, 5]
Note:
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
andnum2
, 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)
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.
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.
LeetCode 207 - Course Schedule [medium]
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0, 1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
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.
Example 2:
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.
Note:
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.
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:
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.
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.
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.
LeetCode 416 - Partition Equal Subset Sum [medium]
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
Each of the array element will not exceed 100. The array size will not exceed 200.
Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
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.
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)
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:
s
from the subset excluding this number: dp[i-1][s]
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)
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.
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.
LeetCode 23 - Merge k Sorted Lists [hard]
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
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.
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)
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.
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.
LeetCode 215 - Kth Largest Element in an Array [medium]
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3, 2, 1, 5, 6, 4] and k = 2
Output: 5
Example 2:
Input: [3, 2, 3, 1, 2, 4, 5, 5, 6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.
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:
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)
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.
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.
LeetCode 704 - Binary Search [easy]
Given a sorted (in ascending order) integer array nums
of n elements and a target
value, write a function to search target
in nums
. If target
exists, then return its index, otherwise return -1.
Example 1:
Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:
Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
Note:
nums
are unique.range [1, 10000]
.nums
will be in the range [-9999, 9999]
.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)
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.