All DSA Techniques
Every technique on the site, organized by topic and pattern. Each one links to a detail page with Java code, complexity analysis, and tips — many with step-by-step visualizations.
Array
When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.
Kadane's / Subarray
String
Think of strings as arrays of characters. Frequency maps solve most comparison problems. For substring search, know KMP or rolling hash to beat O(n·m).
Hashing / Frequency Map
Sliding Window on String
Palindrome Patterns
Pattern Matching
Hash Map
If brute force is O(n²) because of a nested search, a hash map usually drops it to O(n). The tradeoff is O(n) extra space.
Complement / Two Sum
Frequency Count
Hash Map Design
HashMap & HashSet API
Stack
Monotonic stacks are the power tool here. If you need 'next greater/smaller element' or 'span' queries, a monotonic stack gives O(n) instead of O(n²).
Parentheses / Matching
Expression Evaluation
Queue / Deque
BFS = queue. If you need shortest path in an unweighted graph or level-order traversal, reach for a queue. Monotonic deques solve sliding window extremes in O(n).
Monotonic Deque
Queue Design
Linked List
Most linked list problems are about pointer manipulation. Draw it out! Fast & slow pointers detect cycles and find midpoints. In-place reversal is the other core technique.
Fast & Slow Pointers
In-Place Reversal
Merge & Sort
Design Problems
Trees
Tree problems are almost always DFS (recursion) or BFS (level-order). The pattern: solve for children, combine results, return up. BST's sorted property lets you prune half the tree.
Traversal
Path Problems
BST Patterns
Construction & Serialization
Recursion
Every recursive solution has: base case, recursive case, and combining step. For backtracking, add: make choice → recurse → undo choice. Prune early to avoid TLE.
Heap
Need the K largest? Use a min-heap of size K — anything larger than the min gets in. For median, split into two heaps: max-heap for lower half, min-heap for upper half.
Top K Elements
Reorganize / Schedule
Graphs
Start with: is it directed or undirected? Weighted or unweighted? Then pick the right tool: BFS for shortest unweighted path, Dijkstra for weighted, topological sort for DAG ordering, union-find for components.
Topological Sort
Shortest Path
Minimum Spanning Tree
Union Find (DSU)
Dynamic Programming
The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.
LIS Pattern
Bitmask DP
Stock / State Machine
Greedy
Greedy is NOT 'try the obvious thing'. It works only when local optimality guarantees global optimality. Sort first (by end time, deadline, ratio), then pick greedily. If greedy fails, try DP.
Interval Scheduling
Jump Game
Task Scheduling
Classic Greedy
Matrix
For traversal: use direction arrays dx=[0,0,1,-1], dy=[1,-1,0,0]. For sorted matrix search, start from top-right corner. For grid DP, fill row by row — current cell depends on top and left.
Traversal Patterns
Matrix Search
Matrix DP & BFS
Bit Manipulation
Key tricks: n & (n−1) clears lowest set bit (power-of-2 check). XOR of all elements cancels pairs. Bit masks can represent subsets for DP. These are often O(1) space solutions.
Trie
Use a trie when you need prefix-based operations that hash maps can't do efficiently — like 'find all words starting with X' or 'find word matching pattern with wildcards'.
Sorting
Sorting unlocks binary search, two-pointer, and greedy. Always ask: can I sort first? Custom comparators solve tricky ordering problems. Know QuickSelect for O(n) expected Kth element.
Comparison Sorts
Linear-Time Sorts
Sorting Tricks
Range Structures
If you only need prefix queries with point updates, use a BIT (simpler). If you need arbitrary range queries + range updates, use a segment tree with lazy propagation. Sparse table is O(1) query but static.