Coding Patterns

P1 : Sliding Window
Template:

iterate
constraint/pattern/K/sum(S)
output

P2: Two Pointers

P3: Fast and Slow Pointers

P4: Merge Intervals

P13: Top 'K' elements

P10: Subsets

P5: Cyclic Sort

P9: Two Heaps

P6: In-place Reversal of a Linked List

P7: Tree - BFS

P11: Modified Binary Search

P8: Trees - DFS

Bit Manipulation

P14: K-way merge

P15: 0/1 Knapsack problem

click to edit

Graphs

P16.0: Topological Sort / BFS

Course Scheduling Order (medium)

Tasks Scheduling (medium)

click to edit

Topological Sort (medium)

click to edit

Course Scheduling (medium)

click to edit

Tasks Scheduling Order (medium)

click to edit

Alien Dictionary (Hard)

click to edit

PC1: Reconstructing a Sequence (Hard)

Time Complexity: O(V + E)
Space Complexity: O(V + E)

PC2: Minimum Height Tree (Hard)

Time Complexity: O(V + E)
Space Complexity: O(V + E)

All Tasks Scheduling

Backtracking

Time Complexity: O(V! E)
Space Complexity: O(V! E)

click to edit

P 16.1 DFS

Course Scheduling (P16.0)

Possible Bipartition

Number of connected components in an undirected graph

Minimum Height Tree (P16.0)

click to edit

Return from Recursive function

click to edit

Single Root to Leaf Path and tracing back

Deleting currentPath [-1]
Return output from main function not recursive function

All Paths for a Sum (medium)

Sum of Path Numbers (medium)

Binary Tree Path Sum (easy)

All root-to-leaf paths

Algorithm

Start DFS with the root of the tree.

If the current node is not a leaf node, do two things:

At every step, see if the current node being visited is a leaf node and if its value is equal to the given number ‘S’. If both these conditions are true, we have found the required root-to-leaf path, therefore return true.

If the current node is a leaf but its value is not equal to the given number ‘S’, return false.

2.2 Make two recursive calls for both the children of the current node with the new number calculated in the previous step.

2.1 Subtract the value of the current node from the given number to get a new sum => S = S - node.value

Time Complexity: O(N)
Space Complexity: O(N)

Time Complexity: O(N^2)
Space Complexity: O(V! * E)

Time Complexity: O(V! E)
Space Complexity: O(V! E)

Refer EIO Explanation

click to edit

Facts:
Total Root-to-leaf paths can't be more than Number of leaves

No. of leaves in Binary Tree:
(N+1)/2

Depth/height of Balanced Binary Tree:
O(log N)

Algorithm

G(U,V): U comes before V in the ordering.

Source : Vertices with no incoming edges {i:[] for i in range(nodes)}
Indegrees : Number of incoming edges {i:0 for i in range(nodes)}

Facts:

Topological Sort works on no cycles ie. works on Directed Acyclic graph (DAG)

Types
Arrays: [1,2,3,5,8],
Strings: [4,7,9,12]

Dynamic Sliding Window

click to edit

Standard Sliding Window

click to edit

String_Standard SW

5 step process

Array_Standard SW

Smallest Subarray with a given sum

Array

Longest substring with K distinct characters

Fruits into Basket
(Longest substring with at most 2 distinct characters)

Array

Maximum Sum Subarray of Size 'K'

PC1: Permutations in a String

Time Complexity: O(N)
Space Complexity: O(N)

Time Complexity: O(N)
Space Complexity: O(K)

Partial_Dynamic_SW

Longest substring with same letters after replacement

String

Time Complexity: O(N)
Space Complexity: O(K)/O(1) 26 lowercase letters

Longest substring with Ones after replacement

Array

Time Complexity: O(N)
Space Complexity: O(1) (no dict)

Average Subarray of Size 'K'

Time Complexity: O(N)
Space Complexity: O(N)

Time Complexity: O(N)
Space Complexity: O(1)

Time Complexity: O(N+K)
Space Complexity: O(K)

String Anagrams

Time Complexity: O(N+K)
Space Complexity: O(N+K)

Coding Patterns

Reverse

Mirror Image

Two Pinters

Recursion

Sort

Binary Search

Linked List

Two Pointers

Recursion

Smallest window containing substring

P12: Bitwise [XOR]

Blind 75

Sum of two integers

click to edit