Purpose: Solves problems like finding the largest substring without repeating characters, maximum sum subarray of size K, and largest substring with K distinct characters
How it works: Uses two pointers, left and right, to define a "window" within an array or string. The right pointer expands the window, and when a condition (e.g., repeating character) is met, the left pointer shrinks the window
Top K Elements
Purpose: Used for problems like finding the K largest/smallest numbers in an array or K most frequent numbers. It also appears in some sliding window problems
How it works: Instead of sorting (which is O(n log n)), it uses a heap data structure to maintain the K largest elements seen so far. Elements are added to the heap, and if the heap size exceeds K, the minimum element is removed
Time Complexity: O(n log K)
Backtracking
Purpose: Explores all possible solutions step by step. When an invalid state is reached, it "backtracks" to explore other paths. Commonly implemented using recursion.
Example Problem: Combination Sum. Given a list of positive numbers and a target sum, find all unique combinations that add up to the target, allowing numbers to be picked more than once.
Applications: Word Ladder, Permutations, Sudoku Solver.
Dynamic Programming
Purpose: A more thoughtful approach to exploring solutions compared to backtracking. It breaks down a problem into smaller subproblems and builds solutions from the bottom up.
Example Problem: Combination Sum. The video explains how knowing solutions to smaller subproblems (e.g., combinations for target sum - 1, target sum - 2) can help build the solution for the main target sum.
Modified Binary Search
Binary Tree Traversal
Binary Tree DFS (Depth-First Search) & Binary Tree BFS (Breadth-First Search)
Purpose: Both are used for graph traversal and are very similar.
DFS: Starts from a vertex and explores as far as possible along each branch before backtracking. Implemented using a stack
BFS: Explores neighboring vertices first before moving to deeper unvisited vertices. Implemented using a queue.
Applications: BFS is used to find the shortest path between two vertices. Dijkstra's algorithm is a related algorithm for shortest path. Topological Sort is closely related to DFS and is essential for coding interviews
Subset Pattern
Fast & Slow Pointers
In-place Reversal
Monotonic Stack
Top âKâ Elements
Overlapping Intervals
Matrix Traversal
Coding / Problem Solving Tricks
If input array is sorted then:
Binary Search
Two Pointers
If asked for all permutations/subsets then:
Backtracking
If given a tree/graph then:
DFS
BFS
If given a linked list then:
Two Pointers
If recursion is banned then:
Stack
If must solve in-place then:
Swap corresponding values
Store one or more different values in the same pointer
If asked for maximum/minimum subarray/subset/options then:
