Home DSA Patterns
Post
Cancel

DSA Patterns

Posted Sep 17, 2022
By Sanfy.In
9 min read

With a good amount of practice of known questions, some very hard unknown DSA questions can be solved. There are well known patterns of questions and most of the questions that are asked in interviews fall into one or the other. If we do enough practice, we can easily identify the pattern and derive a solution. In this article, we will try to introduce the common patterns for solving DSA problems.

Maths for coding

Sieve of Eratosthenes - to find the Prime Numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// Declare a boolean array and mark all element as prime
bool[] primes = new bool[n + 1];
primes[0] = primes[1] = false;
for (int i=2; i<primes.Length; i++) {
	primes[i] = true;
}

// Loop through a portion of the array (up to the square root of MAX). If
// it's a prime, ensure all multiples of it are set to false, as they
// clearly cannot be prime.
for (int i=2; i<Math.Sqrt(n)+1; i++) {
	if (primes[i-1]) {
		for (int j=(int) Math.Pow(i,2); j<=n; j+=i) {
			primes[j - 1] = false;
		}
	}
}

Find GCD

1
2
3
4
5
6

def gcd(a,b):
	if b==0:
		return a
	return gcd(b, a%b)


1
2
3
4
5
6
7
8
9
10
11

int gcd(int a, int b)
{
	if(b == 0)
	{
		return a;
	}

	return gcd(b, a%b);
}

Fast Power

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18


int Pow(int a,int b)
{
	int res = 1;

	while( b > 0) {
		if((b & 1) != 0)
		{
			res = res * a;
		}

		a = a * a;
		b = b >> 1;
	}
	return res;
}

Catalan Numbers

  1. Program to write Catalan Numbers
1
2
3
4
5
6
7
8

dp[0] = 1
dp[1] = 1

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

Variations:

  1. Number of Binary Search Trees.
  2. Count of Valleys and Mountains
  3. Count of Brackets
  4. Dyk Words
  5. Maze path above diagonal
  6. Circle and Chords
  7. Number of ways of Triangulation
  8. Minimum score of Triangulation

0-1 Knapsack

1
2
3
4
5
6
7
8

def knapsack(wt: List[int], val: List[int], int W, int n)->int:
	if n == 0 or W == 0:
		return 0
	if wt[n-1] <= W:
		return max(val[n-1] + knapsack(wt,val, W - wt[n-1],n-1),knapsack(wt,val, W, n-1))
	else:
		return knapsack(wt,val, W, n-1)
  1. Subset Sum
  2. Equal Sum Partition
  3. Count of Subset Sum
  4. Minimum Subset sum difference
  5. Target Sum
  6. Number of subset with given difference

Unbounded Knapsack

1
2
3
4
5
6
7
8
9

def knapsack(wt: List[int], val: List[int], int W, int n)->int:
	if n == 0 or W == 0:
		return 0
	if wt[n-1] <= W:
		return max(val[n-1] + knapsack(wt,val, W - wt[n-1],n),knapsack(wt,val, W, n-1))
	else:
		return knapsack(wt,val, W, n-1)
  1. Rod cutting
  2. Coin Change
  3. Coin Change 2
  4. Maximum Ribbon Cut

Fibonacci

1
2
3
4
5
6
7
8

def fibo(n: int)-> int:
	dp[0] = 0
	dp[1] = 0
	for i in range(2,n+1):
		dp[i] = dp[i-1] + dp[i-2]
	return dp[n]
  1. Fibonacci number
  2. Climb Stair
  3. Climb Stairs With Variable Jump
  4. Climb Stairs with Minimum Moves
  5. Minimum cost in Maze Path
  6. Goldmine

LCS - Longest Common Subsequence

1
2
3
4
5
6
7

def lcs(x: str, y: str, n: int, m: int)->int:
	if n == 0 or m == 0:
		return 0
	if x[n] == y[m]:
		return 1 + lcs(x, y, n-1, m-1)
	else:
		return max(lcs(x, y, n-1, m),lcs(x, y, n, m-1))
  1. Longest Common Subsequence
  2. Largest Common Substring
  3. Print LCS
  4. Shortest common Super sequence
  5. Print SCS
  6. Minimum number of insertion or deletion to convert string a to b
  7. Length of largest subsequence of a which is a substring in b
  8. Subsequence pattern matching
  9. Count how many times a appears as subsequence in b
  10. Largest Palindromic Subsequence
  11. Largest Palindromic Substring
  12. Count of Palindromic Substring
  13. Minimum number of deletions in a string to make it a Palindrome
  14. Minimum number of insertions in a string to make it a Palindrome
  15. Largest Repeating Subsequence

LIS

  1. LIS
  2. Print all LIS
  3. Maximum sum increasing subsequence
  4. Longest Bitonic Subsequence
  5. Maximum Non-Overlapping Bridges
  6. Russian Doll Envelopes
  7. Perfect Squares
  8. Highway Billboard problem

Kadanes’s Algorithm

  1. Maximum Sum Subarray
  2. Maximum consecutive 1

Matrix Chain Multiplication

1
2
3
4
5
6
7
8
9

def solve(arr: str/List, i: int, j: int)->int:
	if i > j:
		return 0
	for k in range(i,j):
		temp = solve(arr, i,k) + solve(arr, k+1,j)
	ans = cal(temp, ans)
	return ans
  1. MCM
  2. Printing MCM
  3. Evaluate Expression to true / Boolean Parenthesisations
  4. Min/ Max value of an Expression
  5. Palindromic Partitioning
  6. Scramble String
  7. Egg Dropping Problem

DP on Trees

1
2
3
4
5
6
7
8
9
10

def solve(root: Node)-> int:
	if root is None:
		return 0
	l = solve(root.left)
	r = solve(root.right)
	temp = calc(l,r)
	ans = max/min(temp, ans)
	res = max/min(res,ans)
	return res
  1. Diameter of a Binary tree
  2. Maximum Path sum from any node to any
  3. Maximum Path sum from Leaf to leaf
  4. Diameter of N-array Tree

DP on Grid

Count Pattern

1
2
3
4
5
6
7
8
9
10
11

def solve(n):
	dp1 = [ 0 for i in range(n+1)]
	dp2 = [ 0 for i in range(n+1)]
	dp1[1] = 1
	dp2[1] = 1
	for i in range(2, n+1):
		dp2[i] = dp2[i-1] + dp1[i-1]
	dp1[i] = dp2[i-1]
	return dp1[n] + dp2[n]
  1. Count Binary String
  2. Arrange Building
  3. Decode Ways
  4. Count Subsequences of form ABC* Subsequences
  5. Maximum Sum Non Adjacent Elements
  6. Paint House 3 color
  7. Paint House many color
  8. Paint Fences
  9. Tiling with Dominos
  10. Tiling with M*1 Tiles
  11. Friends pairing f(n) = f(n-1) + (n-1)f(n-2)
  12. Partition into Subsets f(n,k) = k*f(n-1,k) + f(n-1,k-1)

Buy Sell Shares

  1. Best Time to Buy and Sell Stocks - one transaction
1
2
3
4
5
6
7
8
9
10
11
12

lsf = IntMax
op = 0
pist = 0

for p in range(len(prices)):
	if prices[p] < lsf:
		lsf = pist
		pist = prices[p] - lsf

	op = max(op, pist)
  1. Best Time to Buy and Sell Stocks - infinite transaction
1
2
3
4
5
6
7
8
9
10
11
12
13

bp = 0
sp = 0
ans = 0

for p in range(1, len(prices)):
	if prices[p] < sp:
		ans += prices[sp] - prices[bp]
		bp = p
		sp = p
	else:
		sp += 1
  1. Best Time to Buy and Sell Stocks - with transaction fees
1
2
3
4
5
6
7
8

bsp = prices[0]
ssp = 0

for p in range(1, len(prices)):
	tempbsp = min((prices[p] - ssp), bsp)
	ssp = max((prices[p] - bsp - f), ssp)
	bsp = tempbsp
  1. Best Time to Buy and Sell Stocks - infinite transaction with cool down
1
2
3
4
5
6
7
8
9
10
11
12
13
14

bsp = prices[0]
ssp = 0
csp = 0

for p in range(1, len(prices)):
	nbsp = min((prices[p] - csp), bsp)
	nssp = max((prices[p] - bsp), ssp)
	ncsp = max(ssp , csp)
	bsp = nbsp
	sso = nssp
	csp = ncsp

  1. Best Time to Buy and Sell Stocks - two transaction

  2. Best Time to Buy and Sell Stocks - k transaction

Others

  1. Largest Square Sub Matrix
1
2
3
4
5
6
7

for i in range(n-1, -1,-1):
	for j in range(m-1, -1, -1):
		if i == n-1 or j == m-1 or M[i][j] == 0:
			A[i][j] = M[i][j]
			continue
		A[i][j] = 1 + min(A[i][j-1], A[i-1][j], A[i-1][j-1]))

Greedy Algorithm

Local optimal solution

  1. N meetings in one room
  2. Maximum meetings in one room
  3. Shop in Candy store
  4. Check if it is possible to survive on Island
  5. Reverse words in a given string
  6. Chocolate Distribution Problem
  7. Minimum cost of ropes
  8. Huffman Coding
  9. Fractional Knapsack

  10. Job Sequencing Problem

  11. Maximum performance of a team - LC1383

Sliding Windows

  1. Maximum Sum Subarray of size K

  2. First Negative Number in every Window of Size K

  3. Count Unique Characters of All Substrings of a Given String

    • contribution of a Character = leftWindowCount * rightWindowCount
    • Create dict<char, List> to hold index of each character
    • ABCAACD - len(str) = 6
    • A -> -1,0,3,4,7
    • left = I[i] - I(i-1)
    • right = I[i+1] - I[i]
  4. Maximum Sum Circular Subarray
  • find max_sum, min_sum, total_sum
  • if total sum = min_sum, return max sum
  • else return max(max_sum, total_sum - min_sum)

Stack

  1. Remove K digits Build lowest number
  • remove first peak
  • Use stack, remove if the top of stack is greater than the current element and keep decrementing k
  • if stack is empty and current element is 0, skip to next element.
  • If k = 0, insert rest of the element in the stack.
  • remove element from stack and create the string
  • T O(N), S O(N)

Graph

1
2
3
4
5

class Edge:
	def **init**(self):
	self.src
	self.nbr
	self.wt

Bit Manipulation

0 MSB - covert as it is 1 MSB - 2’s complement 4bit signed - -8 to 7 4bit unsigned - 0 to 16

decimal to binary +ve - fit in bits -ve - Covert to binary without sign - Fit in bits - 2’s complement

on - or off - and toggle - xor check - and

  1. Allocate Minimum Number Of Pages
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

nums = [10, 20, 30, 40]

if m > len(nums):
	return -1

start = Max(nums)
end = Sum(nums)

res = -1

while start <= end:
	mid = start + (end - start)/2
	if isValid(nums,mid,m) == true:
		res = mid
		end = mid - 1
	else:
		start = mid + 1

def isValid(nums, max, m):
	tempM = 1
	sum = 0
	for n in nums:
		sum += n
		if sum > max:
			tempM++
		if(tempM > m):
			return false
			sum = n
	return true
algorithm
This post is licensed under CC BY 4.0 by the author.
Contents