[Algorithm -] Patterns (LeetCode)

https://blog.algomaster.io/

https://blog.algomaster.io/p/15-leetcode-patterns

https://blog.algomaster.io/p/20-patterns-to-master-dynamic-programming

Prefix Sum patterns
문제 303 / 525 / 560

usage :
Query Sum of elements in a subArray.

const array = [1,2,3,4,5,6,7] 

Two pointers patterns
문제 167 / 15 / 11

O(n^2) -> O(n)

Sliding window
문제 643 / 3 / 76

Fast and Slow Pointers
문제 141 / 202 / 287

Linked List in-place Reversal **
문제 206 / 92 / 24

Monotonic Stack
문제 496 / 739 / 84

Top 'K' Elements
문제 215 / 347 / 373

"K" Largest (Min-Heap) / "K" Smallest (Max-Heap) / "K" Most Frequent

Overlapping Intervals (미팅룸 빈곳 시간 찾기 등등)
문제 56 / 57 / 435

Intervals or Ranges that may overlap

Mergin Inverval

[[1,3], [2,6], [8,10], [15,18]]

[[1,6], [8,10], [15,18]]

Interval Intersection

[[0,2], [5,10], [13,23], [24,25]] and [[1,5], [8,12], [15,24], [25,26]]

[[1,2], [5,5], [8,10], [15,23], [24,24], [25,25]]

Insert Interval

[[1,2], [3,5], [6,7], [8,10], [12,16]] and [4,8] 

[[1,2], [3,10], [12,16]]

Modified Binary Search
문제 33 / 153 / 240

1. Searching In a Nearly Sorted array
2. Searching In a Rotated Sorted array
3. Searching In a list with Unknown length
4. Searching In a List with Duplicates
5. Finding the first of last occurence of an element.
6. finding the sqaure root of a number
7. finding a peak element.

Binary Tree Traversal
문제 PreOrder 257 / InOrder 230 / PostOrder 124 / LevelOrder 107

1. To retrieve the values of binary search tree in sorted order, use inforder traversal
2. To create a copy of a tree(serialization), use preorder. traversal
3. when you want to process child nodes before the parent, use postorder traversal
4. when you need to explore all nodes at current level before next, use level order traversal

Depth-first Search (DFS) **
문제 133 / 113 / 210
1. Finding a path between two nodes
2. checking if a graph contains a cycle
3. finding a topological order in a directed acyclic graph(DAG)
4. counding number of connected components in a graph.

Breadth-first search (BFS)
문제 102 / 994 / 127
1.Finding the shortest path between two nodes
2. Printing all nodes of a tree level by level
3. finding all connected components in a graph

Matrix Traversal
문제 733 / 200 / 130

Backtracking
문제 46 / 78 / 51

Exploring all potential solution paths and backtracking the paths that do not lead to a valid solution.

Dynamic programming (DP)
patterns : Fibonacci Numbers , 0/1 knapsack, longest common subsequence(LCS), longest increasing subsequence(LIS), Subset sum, Matrix chain Multiplication,
문제 70 / 322 / 1143 / 300 / 416 / 312
DP문제

Solving optimization problems by breaking them down into smaller sub-problems and storing their solutions to avoid repetitive work.

con's : Overlapping subproblems / ooptimal substructure