Problems
Catalan Number
Problem Statement:
How many unique Binary Search Trees (BSTs) can be formed with n nodes?
Approach:
The number of unique BSTs with n nodes is given by the Catalan number \(C_n\). For each possible root node \(i\) (from 1 to \(n\)), the left subtree contains \(i-1\) nodes and the right subtree contains \(n-i\) nodes. For a tree to be BST its left and right subtree should be a BST. The total number of BSTs is the sum over all possible roots: \(C_n = \sum_{i=1}^n C_{i-1} \times C_{n-i}\)
fun catalanNumber(n: Int) {
val cn = IntArray(n + 1) { 0 }
cn[1] = 1
cn[2] = 2
for(i in 3 .. n) {
for(j in 1 .. i)
cn[i] += cn[j - 1] * cn[i - j]
}
return cn[n]
}
Maximum Sum Subarray (Kadane's Algorithm)
Problem Statement:
Given an array of integers, find the contiguous subarray with the maximum sum.
Approach:
Let \(M[i]\) be the maximum sum of a subarray ending at index \(i\). For each \(i\), \(M[i] = \max(M[i-1] + A[i], A[i], 0)\). The answer is the maximum value among all \(M[i]\).
fun maxSubArraySum(arr: List<Int>) {
var maxSum = arr.first()
var currSum = arr.first()
arr.drop(1).forEach {
currSum += it
if(currSum < 0) currSum = 0
if(maxSum < currSum) maxSum = currSum
}
return maxSum
}
Edge case: all elements are negative.
Tiling
Problem Statement: Given a 2x1 dominoes. Find number of ways to tile a 2 x n strip.
Approach: If we use it vertically, we need 1 unit length and if its placed horizontally we need 2 units length. So the problem breaks down to number of ways to get n using 1 & 2. Number of ways to get n be dp[n] = dp[n-1] + dp[n-2]
fun tiling(n: Int) {
val dp = IntArray(n + 1) { 0 }
dp[0] = 1
dp[1] = 1
for(i in 2 .. n) {
dp[i] = d[i - 1] + dp[i - 2]
}
return dp[n]
}
Longest increasing subsequence (LIS)
Problem Statement: Given a list of integers. Find the longest subsequence, in which the values are strictly increasing.
Approach:
The subproblem is finding LIS in A[0..i], then LIS of A[0..i+1] is max(dp[j] + 1), where j <= i and A[i+1] > A[j]
fun lis(arr: List<Int>) {
val dp = IntArray(arr.size + 1) { 0 }
dp[0] = 1
for(i in 1 until arr.size) {
dp[i] = 1
for(j in 1 until i) {
if (arr[i] > arr[j])
dp[i] = maxOf(dp[i], 1 + dp[j])
}
}
return dp.max()
}
Time complexity of this approach is \(O(n^2)\). Optimal solution is using a binary search that takes \(O(log ~n)\)
Longest Common Subsequence (LCS)
Problem Statement:
Given two strings, X (length m) and Y (length n), find the length of their longest common subsequence (LCS).
Approach:
Compare the first characters of X and Y. If they are equal, increment the LCS length and move to the next characters in both strings. Otherwise, recursively compute the LCS by either skipping the current character in X or Y, and take the maximum result. Formally, for indices i in X and j in Y:
- If X[i] == Y[j]: LCS(X[i+1:], Y[j+1:]) + 1
- Else: max(LCS(X[i+1:], Y[j:]), LCS(X[i:], Y[j+1:]))
Subproblem: Find LCS in the strings X[i...m] and Y[j...n]
fun lcs(s1: String, s2: String) {
val dp = MutableList(s1.size + 1) { IntArray(s2.size + 1) {0} }
for(i in s1.size - 1 downTo 0) {
for(j in s2.size -1 downTo 0) {
if(s1[i] == s2[j]) {
dp[i][j] = 1 + dp[i + 1][j + 1]
} else {
dp[i][j] = maxOf(dp[i + 1][j], dp[i][j + 1])
}
}
}
}
This can be further space optimized as in every \(i^{th}\) iteration we only need current and previous row of table dp.
fun lcsOptim(s1: String, s2: String) {
var prev = IntArray(s2.size + 1) { 0 }
for(i in s1.size - 1 downTo 0) {
var curr = IntArray(s2.size + 1) { 0 }
for(j in s2.size -1 downTo 0) {
if(s1[i] == s2[j]) {
curr[j] = 1 + prev[j + 1]
} else {
curr[j] = maxOf(prev[j], curr[j + 1])
}
}
prev = curr.also { curr = prev}
}
}
To retrieve the actual subsequence (not just its length), you must maintain the DP table and reconstruct the answer from it.
Matrix Chain Multiplication (Parenthesization)
Problem Statement:
Given a sequence of matrices, find the most efficient way to multiply these matrices together.
Approach:
The idea is if we chain matrices 0 to k and k+1 to n then total operations is ops to multiply 0 to k matrices + ops to multiply k+1 to n matrices + \(P_0 * P_K * P_n\). So we have \(O(n^2)\) subproblems, and they repeat.
Let \(M[i, j]\) represents the least number of multiplications to multiply \(A_i \cdots A_j\). Then \(M[i, j] = 0\), if i=j else \(M[i, j] = \min_k (M[i, k] + M[k+1, j] + P_{i-1}*P_k*P_j)\)
fun matrixChainOrder(P: List<Int>) {
val n = p.size - 1
val m = MutableList(n) { IntArray(n) { 0 } }
val s = MutableList(n) { IntArray(n) { 0 } }
for(l in 2 .. n) {
for(i in 1 .. n-l+1) {
val j = i + l - 1
m[i][j] = INT.MAX_VALUE
for(k in i .. j - 1) {
val splitCost = m[i][k] + m[k+1][j] + P[i-1] * P[k] * P[j]
if (splitCost < m[i][j]){
m[i][j] = splitCost
s[i][k] = k
}
}
}
}
}
Space can be optimized by storing only m[i][:] and m[:][j] into two 1D lists.
0-1 Knapsack
Problem Statement:
Approach:
If \(W_i\) is greater than C, we can't add. Otherwise, For each item, we have two options either include it or not. We choose the option that gives maximum value.
We break the problem into subproblems of solving max value we get for i items and j capacity, where i \(\in\) [0, n] and j \(\in\) [0, C]. If we use an item the subproblem becomes solving max value we get for i - 1 items to fill j - W_i capacity knapsack. \(dp[i, j] = max(dp[i - 1, j], dp[i - 1, j - W_{i}] + V_{i})\) For i+i th item we can simply use previous values.
fun knapsack(weights: List<Int>, values: List<Int>, C: Int) {
val dp = MutabeList(weights.size + 1) { IntArray (C + 1) {0} }
for(i in 1 .. weights.size) {
for(j in 1 .. C) {
if(weights[i - 1] > j)
dp[i][j] = dp[i - 1][w]
else
dp[i][j] = maxOf(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
}
}
return dp[weights.size - 1][C]
}
Integer Knapsack
Problem Statement: Given n items, each with a weight and a value, determine the number of each item to include in a knapsack so that the total weight is less than or equal to a given limit C and the total value is as large as possible. The items can be taken in integer quantities. Each item can be included any number of times.
Approach:
The approach is similar to 0/1 knapsack, the only difference is an item can be used multiple times. So once an item is used the subproblem is to solve max value using i items to fill j - w_i capacity knapsack, instead of solving i-1 items to fill j - w_i capacity knapsack.
fun integerKnapsack(weights: List<Int>, values: List<Int>, C: Int) {
val dp = MutabeList(weights.size + 1) { IntArray (C + 1) {0} }
for(i in 1 .. weights.size) {
for(j in 1 .. C) {
if(weights[i - 1] > j)
dp[i][j] = dp[i - 1][w]
else
dp[i][j] = maxOf(dp[i - 1][j], dp[i][j - weights[i - 1]] + values[i - 1])
}
}
return dp[weights.size - 1][C]
}
Coin Change Problem
Problem Statement: Given n types of denominations of values \(v_1 \lt v2 \lt \cdots \lt v_n\), where \(v_1\) = 1. Minimum number of coins required to make change for an amount of money C.
Approach:
Similar to integer knapsack weight is the coin value and value is 1, instead of maximizing the value we want to minimize it.
Subset Sum
Problem Statement:
Given a list of positive integers, A. Find we there exists a subset whose sum is T.
Approach:
Similar to 0/1 knapsack approach. But instead of finding max value we will check if T capacity can be filled.
fun subset(arr: List<Int>) {
val curr = BooleanArray(T + 1) { False }
val prev = BooleanArray(T + 1) { False }
prev[0] = True
for(i in 1 .. arr.size) {
for (j in 1 .. T) {
curr[j] = prev[j] // Not include in subset
if (arr[i] <= j && prev[j - arr[i]]) { // Can include in subset
curr[j] = True
}
}
curr = prev.also { prev = curr }
}
return curr[T]
}
Subsets Partition
Problem Statement: Given a list of n integers. If their sum is K, find the subset whose sum is equal to half of total sum
Approach: Same as Subset Sum
Box Stacking
Problem Statement: Given n rectangular 3D boxes. Find the max height we can get by stacking the boxes such that dimensions of 2-D base of lower box is strictly larger than base of higher box
Approach:
For each box we have to consider 3 orientations. If we have a box with dimensions a x b x c, then a x (b x c), b x (a x c), c x (a x b) are 3 ways in which each box can be stacked.
After we sort the boxes on base area, the problem can be considered as LIS.
Building Bridges
Problem Statement: Given 2 lists each with integers from 1 to n in random order. We want to draw lines from one list to another, we can only draw a line from integer i in list 1 to integer i in list 2. Find the max lines that can be drawn such that no 2 lines cross.
Approach:
This problem is same as LCS.
What if we are also given a list of pairs that tells a line can only be drawn between elements in the index in the pair?
Then the problem can be solved using LIS approach. Two lines (a1, b1) and (a2, b2) overlap if (a1 < a2 & b1 > b2) or (a1 > a2 & b1 < b2). Sort on the first element and find LIS in the second elements.
Boolean Parenthesization
Problem Statement: Given a boolean expression consisting of symbols 'true', 'false', 'and', 'or', 'xor'. Find number of ways to parenthesize the expression that will evaluate to true.
Approach:
Similar to the matrix chain problem. Let T[i,j] be the number of ways to parenthesize operands from i to j so they evaluate to true and F[i,j] be for false.
Optimal BST
Problem Statement: Given n sorted keys A[1..n] and their frequencies of number of times they are searched. Construct a BST to reduce the search time.
Approach:
We can select any element as root. Let r be root then the problem turns into finding Optimal BST for A[1 .. r-1] amd A[r+1 .. n].
The cost of searching a key = depth of the node * frequency.
Optimal BST is the BST with root r that gives minimal searching cost. Let dp[i, j] be min cost of BST for A[i .. j]. Then dp[i, j] = $\min_r(dp[i, r-1] + dp[r + 1, j] + sum(freq[i ..j])) $
fun optimalBST(arr: List<Int>, freq: List<Int>) {
val n = arr.sizr
val dp = MutableList(n) { IntArray(n) { Int.MAX_VALUE } }
val cummFreq = freq.runningFold(0) { sum, it -> sum + it }.drop(1)
for(l in 1 .. n) {
for(i in 0 .. n -l) {
val j = i + l - 1
val freqSum = cummFreq[j + 1] - cummFreq[i]
for(r in i .. j){
dp[i][j] = minOf(
dp[i][j],
if(r > i) dp[i][r - 1] else 0 // left subtree
if(j > r) dp[r + 1][j] else 0 // right subtree
)
}
dp[i][j] += freqSum
}
}
return dp[0][n - 1]
}
Edit Distance
Problem Statement: Given strings A and B. Minimum number of operations required to transform A into B. Operations that can be performed are insert a chat in A, delete a char in A, update a char in A.
Approach:
Let dp[i, j] be min ops to transform A[1..i] to B[1..j]. If A[i] == B[j] then dp[i, j] = dp[i - 1, j - 1], else dp[i, j] = 1 + min(dp[i - 1, j], dp[i, j - 1], dp[i - 1, j - 1]) which captures delete, insert and replace operations respectively.
fun editDistance(A: String, B: String) {
val m = A.length
val n = B.length
val dp = MutableList(m + 1) { IntArray (n + 1) { 0 } }
for(i in 0 .. m) dp[i][0] = i // insertions
for(i in 0 .. n) dp[0][i] = i // deletions
for(i in 1 .. m){
for(j in 1 .. n) {
if(A[i - 1] == B[j - 1])
dp[i][j] = dp[i - 1][j - 1]
else
dp[i][j] = 1 + minOf(
dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]
)
}
}
}
There are a few heuristic algorithms that can solve in less than \(O(n^2)\) but with less accuracy such as Myers' algorithm, A* Search + Trie
Floyd's Algorithm
Problem Statement: Given a weighted DAG. Find the shortest path between all nodes in the DAG. C[][] contains the weight of edges and C[i][j] = \(\infty\) if there is no edge between node i and node j.
Approach:
Let d[i, j] represent distance between node i and node j. d[i,j] = C[i, j] if edge exists else \(\infty\) and d[i, i] = 0.
For each node k d[i,j] = min(d[i,j], d[i,k] + d[k, j])
fun floydWarshall(graph: List<List<Int>>) {
val V = graph.size
val d = MutableList(V) { i -> IntArray(V) { j -> graph[i][j] } }
for(k in 0 until V){
for(i in 0 until V) {
for (j in 0 until V) {
if (d[i][k] < Int.MAX_VALUE && d[k][j] < Int.MAX_VALUE) {
d[i][j] = minOf(d[i][j], d[i][k] + d[k][j])
}
}
}
}
}
Optimal Game Strategy
Problem Statement: Given a row of n coins, where n is even. In a two-player game at each turn a coin from the start or end can be removed, and its value is added to player's score. Find the maximum amount the first player can win.
Approach:
Let V[i,j] be maximum value first player can get when only coins \(v_i \cdots v_j\) are left.
If the player picks \(v_i\) then the other player picks optimally from \(v_{i+1} \cdots v_j\) and leave the minimum value for us.
V[i,j] = \(\max(v_i + min(V[i + 1, j - 1], V[i + 2, j]) , v_j + min(V[i, j - 2], V[i + 1, j - 1]))\)
fun maxScore(coins: List<Int>) {
val n = coins.size
val dp = MutableList(n) { IntArray(n) { 0 } }
for(i in 0 until n-1) {
dp[i][i] = coins[i]
dp[i][i + 1] = max(coins[i], coins[i+1])
}
dp[n-1][n-1] = coins[n-1]
for(l in 2 until n) {
for(i in 0 until n - l) {
val j = i + l
dp[i][j] = maxOf(
coins[i] + minOf(dp[i + 1][j - 1] , dp[i + 2][j]),
coins[j] + minOf(dp[i + 1][j - 1] , dp[i][j - 2])
)
}
}
}
Longest Palindrome Subsequence
Problem Statement: Given a string A, find the longest subsequence of A which is a palindrome.
Approach:
Let the length of longest palindrome subsequence in substring S[i,j] be L[i,j]. If S[i] = S[j] then L[i,j] = 2 + L[i+1, j-1] else L[i,j] = max(L[i+1, j], L[i, j-1])
fun palindromeSubSeq(str: String) {
val dp = MutableList(str.size) { IntArray (str.size) {false} }
for(i in str.indices) dp[i][i] = 1
for(l in 2 .. str.size) {
for(i in 0 .. str.size -l){
val j = i + l -1
if(str[i] == str[j]){
dp[i][j] = 2 + dp[i + 1][j - 1]
} else {
dp[i][j] = maxOf(dp[i+1][j], dp[i][j-1])
}
}
}
return dp[0][str.size - 1]
}
Longest Palindrome Substring
Problem Statement: Given a string A, find the longest substring of A which is a palindrome.
Approach:
A substring S[i,j] is palindrome if S[i+1, j-1] is palindrome and S[i] = S[j].
So we can start with substrings of length 2 and keep increasing the length.
fun palindromeSubString(str: String) {
val dp = MutableList(str.size) { BooleanArray (str.size) {false} }
var maxLen = 1
for(i in str.indices) {
dp[i][i] = true
if (i < str.size - 1 && str[i] == str[i+1]) {
dp[i][i+1] = true
maxLen = 2
}
}
for(l in 3 .. str.size) {
for(i in 0 .. str.size - l) {
val j = i + l - 1
if(str[i] == str[j] && dp[i+1][j-1]) {
dp[i][j] = dp[i+1][j-1]
maxLen = maxOf(maxLen, l)
}
}
}
return maxLen
}
Can be space optimized to O(n).
We can also use the idea of 'Expand Around Center', which takes O(1) space.
Manacher’s Algorithm solves this in O(n) time.
Matrix max value path
Problem Statement: Given a 2D matrix grid of size m x n, move from the top-left cell to the bottom-right cell. You can only move right or down at any point. Find the maximum path sum.
Approach:
Break the problem into subproblem of a max value path to (i,j) from (0, 0), let the solution be S[i, j]. Then the max value path to (m,n) is max(S[i-1, j], S[i, j-1]) + M[m, n]
fun maxValuePath(mat: List<List<Int>>) {
val rows = mat.size
val cols = mat.first().size
val dp = MutableList(rows) { IntArray(cols) { 0 } }
for(i in 0 until rows) {
for(j in 0 until cols) {
dp[i][j] = mat[i][j] + maxOf(
if(i > 0) dp[i-1][j] else 0,
if(j > 0) dp[i][j-1] else 0
)
}
}
return dp[rows - 1][cols - 1]
}
Max Square Sub-Matrix
Problem Statement: Given a matrix with 1's and 0's. Find maximum size square submatrix with all 1s.
Approach:
Break the problem into subproblems of finding max size that ends at (i,j), let solution be L[i, j]. Then for any other coordinate (x,y) max size is given by 1 + min(L[x-1, y], L[x, y-1], l[x-1, y-1])
fun square1sSubMatrix(mat: List<List<Int>>) {
val rows = mat.size
val cols = mat.first().size
val dp = MutableList(rows) { IntArray(cols) { 0 } }
var maxSize = 0
for(i in 0 until rows) dp[i][0] = mat[i][0]
for(i in 0 until cols) dp[0][i] = mat[0][i]
for(i in 1 until rows) {
for (j in 1 until cols) {
if(mat[i][j] == 1) {
dp[i][j] = 1 + minOf(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
}
maxSize = maxOf(maxSize, dp[i][j])
}
}
}
Max Sub-Matrix
Problem Statement: Given a matrix with 1's and 0's. Find maximum size submatrix with all 1s.
Approach:
Find the cumulative sum of consecutive 1's column wise. For each row get the largest rectangle in histogram.
fun largestRectangleArea(heights: IntArray) {
val stack = ArrayDeque<Int>()
var maxArea = 0
val newHeights = heights + 0
for(i in newHeights.indices) {
while(stack.isNotEmpty() && newHeights[i] < newHeights[stack.last()]) {
val height = newHeights[stack.removeLast()]
val width = if(stack.isEmpty()) i else i - stack.last() - 1
maxArea = maxOf(maxArea, height * width)
}
stack.addLast(i)
}
return maxArea
}
fun max1sMatrix(mat: List<List<Int>>) {
val rows = mat.size
val cols = mat.first().size
val heights = IntArray(cols) { 0 }
var maxArea = 0
for (i in 0 until rows) {
for (j in 0 until cols) {
height[j] = if (matrix[i][j] == 0) 0 else heights[j] + 1
}
maxArea = maxOf(maxArea, largestRectangleArea(heights))
}
return maxArea
}
Maximum sum sub-matrix (2D Kadane)
Problem Statement: Given an n x n Matrix M. Find the submatrix with the largest sum.
Approach:
We can extend Kadane's algorithm to 2D. The idea is to reduce the 2D problem to 1D by fixing the left and right columns of a submatrix. For each pair of columns, compute the sum of elements for every row between those columns, then use Kadane's algorithm on this 1D array to find the maximum sum subarray (which corresponds to the best submatrix for those columns). Repeat for all pairs of columns and keep track of the maximum sum found.
fun maxSumSubmatrix(matrix: Array<IntArray>): Int {
val n = matrix.size
var maxSum = Int.MIN_VALUE
var maxLeft = 0
var maxRight = 0
var maxTop = 0
var maxBottom = 0
for (left in 0 until n) {
val temp = IntArray(n) { 0 }
for (right in left until n) {
for (i in 0 until n) {
temp[i] += matrix[i][right]
}
// Apply Kadane's algorithm on temp
var currSum = temp[0]
var currMax = temp[0]
var start = 0
var maxStart = 0
var maxEnd = 0
for (i in 1 until n) {
if (currSum < 0) {
currSum = temp[i]
start = i
} else currSum += temp[i]
if (currSum > maxSum) {
maxSum = currSum
maxStart = start
maxEnd = i
}
}
if (currMax > maxSum) {
maxSum = currMax
maxLeft = left
maxRight = right
maxTop = maxStart
maxBottom = maxEnd
}
}
}
return maxSum
}
Optimal jumps
Problem Statement: Given an array start from the first element and reach the end by jumping. The jump length can be at most the value at current position. Find minimum jumps required.
Approach:
Break it in to subproblems of min jumps required to reach from i to end, let the solution to this subproblem be J[i]. Then the min jumps from start to end will be \(\min_{k=0}^{A[0]} 1 + J[k]\). Return -1 if it can't be reached
fun minJumps(arr: List<Int>) {
val n = arr.size
val dp = IntArray(n) { -1 }
dp[n - 1] = 0
for(i in n - 2 downTo 0) {
for(j in i + 1 .. minOf(i + arr[i], n-1)) {
if(dp[j] != -1){
if (dp[i] == -1) dp[i] = 1 + dp[j]
else dp[i] = minOf(dp[i], 1 + dp[j])
}
}
}
return dp[0]
}
Can be solved in O(n) using greedy approach.