Algorithm Patterns ���

Complete Reference
Two Pointers, Sweep Line, Greedy, Sliding Window, DFS/BFS,
Recursion

Two Pointers — Complete Guide

1. What is it?
2. Why is it used?
3. Where is it used?
4. How to identify a Two Pointers problem (pattern triggers)
5. Can you tell from constraints alone?
6. Intuition / Rationale
7. Time & Space Complexity (generic)
8. Types of Two Pointers (with templates)
9. Comparison of the patterns
10. Quick decision checklist (use this in an interview)
Sweep Line — Complete Guide
1. What is it?
2. Why is it used?
3. Where is it used?
4. How to identify a Sweep Line problem (pattern triggers)
5. Can you tell from constraints alone?
6. Intuition / Rationale
7. Time & Space Complexity (generic)
8. Types of Sweep Line (with Java templates)
9. Comparison of the patterns

1
 10. Quick decision checklist (use this in an interview)
11. Comparison with Two Pointers
Greedy Algorithms — Complete Guide
1. What is it?
2. Why is it used?
3. Where is it used?
4. How to identify a Greedy problem (pattern triggers)
5. Can you tell from constraints alone?
6. Intuition / Rationale
7. Time & Space Complexity (generic)
8. Types of Greedy (with Java templates)
9. Comparison of the patterns
10. Quick decision checklist (use this in an interview)
11. Comparison with Two Pointers and Sweep Line
Sliding Window — Complete Guide
1. What is it?
2. Why is it used?
3. Where is it used?
4. How to identify a Sliding Window problem (pattern triggers)
5. Can you tell from constraints alone?
6. Intuition / Rationale
7. Time & Space Complexity (generic)
8. Types of Sliding Window (with Java templates)
9. Comparison of the patterns
10. Quick decision checklist (use this in an interview)
11. Comparison with Two Pointers, Sweep Line, and Greedy
DFS & BFS — Complete Guide
1. What is it?
2. Why is it used?
3. Where is it used?
4. How to identify a DFS vs BFS problem (pattern triggers)
5. Can you tell from constraints alone?
6. Intuition / Rationale
7. Time & Space Complexity (generic)
8. Types of DFS & BFS (with Java templates)

2
 9. Comparison of the patterns
10. Quick decision checklist (use this in an interview)
11. Comparison with Two Pointers, Sliding Window, Sweep Line, and Greedy
Recursion — Complete Guide
1. What is it?
2. Why is it used?
3. Where is it used?
4. How to identify a Recursion problem (pattern triggers)
5. Can you tell from constraints alone?
6. Intuition / Rationale
7. Time & Space Complexity (generic)
8. Types of Recursion (with Java templates)
9. Comparison of the patterns
10. Quick decision checklist (use this in an interview)
11. Comparison with DFS/BFS and the other patterns

3
Two Pointers — Complete Guide

1. What is it?

Two Pointers is a technique where you use two index variables (pointers) to traverse
a data structure (usually an array, string, or linked list) instead of nested loops, to
reduce time complexity from O(n²) to O(n) or O(n log n).

The pointers can move: - Toward each other (from both ends, converging) - In the
same direction (fast/slow, or a sliding window) - From different starting points
(merging two structures)

2. Why is it used?

• Avoids brute-force nested loops (O(n²) → O(n))

• Constant extra space — no hash maps needed in most cases
• Naturally exploits sorted order or monotonic property in data
• Elegant for problems involving pairs, subarrays, or in-place modification

3. Where is it used?

• Sorted array pair/triplet sum problems

• Removing duplicates / elements in-place
• Palindrome checking
• Merging sorted arrays/lists
• Sliding window (subarray/substring) problems
• Container/trapping water problems
• Linked list cycle detection (Floyd’s — fast/slow pointers)
• Partitioning (Dutch National Flag, quicksort partition)

4. How to identify a Two Pointers problem (pattern

triggers)

Ask these questions within the first 2 minutes:

4
Signal in the problem statement What it suggests
“sorted array” / “sorted linked list” Converging or same-direction pointers
“pair/triplet that sums to X” Opposite-direction pointers
“in-place”, “O(1) space” Fast/slow same-direction pointers
“subarray/substring with property (sum, distinct
Sliding window (variable two pointers)
chars, at most K…)”
“remove duplicates”, “move zeroes” Slow/fast write-read pointers
“palindrome” Converging pointers from ends
“merge two sorted…” Two pointers, one per structure
“cycle in linked list”, “middle of linked list” Fast/slow (Floyd’s)
“container”, “trapping rain water”, “max area” Converging pointers, greedy shrink
Asks for O(n) or O(n log n) but brute force is
Strong hint to look for two pointers
O(n²) or O(n³)

Paraphrase test: If the problem can be rephrased as “find two indices i, j such that
some condition holds” or “find the longest/shortest contiguous range where condition
holds” — it’s very likely two pointers.

5. Can you tell from constraints alone?

Yes, constraints are a strong secondary signal: - n up to 10^5 – 10^6 with expected
O(n) or O(n log n) → nested loops are out, two pointers/sliding window is a prime
candidate. - Array is stated or can be sorted without breaking the answer (order doesn’t
matter, e.g., “does a pair exist”) → sort + converging pointers. - If order matters and
you can’t sort (e.g., original indices needed) → use a hashmap instead, not two
pointers. - “At most/exactly/at least K distinct” with large n → sliding window (variant of
two pointers).

6. Intuition / Rationale

Nested loops recheck combinations blindly. Two pointers work because of a monotonic
invariant: moving one pointer only ever helps in one direction, so you never need to
re-examine a discarded state.

Example: in sorted array pair-sum, if arr[left] + arr[right] > target , decreasing

right is the only useful move — increasing left while keeping right fixed only
makes the sum bigger or same relative issue. This monotonicity is what lets you drop
one loop entirely — each pointer moves at most n times total, giving O(n).

7. Time & Space Complexity (generic)

• Time: O(n) or O(n log n) if sorting is required first

• Space: O(1) extra (excluding input/output), since only index variables are used

5
8. Types of Two Pointers (with templates)

Type A — Opposite Direction (Converging)

Used for: sorted array pair sum, palindrome check, container with most water, trapping
rain water, reverse array in place.

public boolean twoSumSorted(int[] arr, int target) {

int left = 0, right = [Link] - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
return true; // or record indices/pair
} else if (sum < target) {
left++; // need a bigger sum
} else {
right--; // need a smaller sum
}
}
return false;
}

Type B — Same Direction (Fast/Slow, in-place read-write)

Used for: remove duplicates, move zeroes, partition array.

public int removeDuplicates(int[] arr) {

if ([Link] == 0) return 0;
int slow = 0; // last position of "clean" section
for (int fast = 1; fast < [Link]; fast++) {
if (arr[fast] != arr[slow]) {
slow++;
arr[slow] = arr[fast];
}
}
return slow + 1; // new length
}

Type C — Sliding Window (Variable-size, same direction)

Used for: longest/shortest subarray or substring satisfying a condition.

6
 public int longestSubarrayWithSumAtMostK(int[] arr, int k) {
int left = 0, sum = 0, maxLen = 0;
for (int right = 0; right < [Link]; right++) {
sum += arr[right];
while (sum > k) { // shrink window while invalid
sum -= arr[left];
left++;
}
maxLen = [Link](maxLen, right - left + 1);
}
return maxLen;
}

Type D — Fast/Slow Pointers (Cycle detection — Floyd’s)

Used for: linked list cycle detection, finding the middle/duplicate.

public boolean hasCycle(ListNode head) {

ListNode slow = head, fast = head;
while (fast != null && [Link] != null) {
slow = [Link];
fast = [Link];
if (slow == fast) return true;
}
return false;
}

Type E — Merge Pointers (Two separate structures)

Used for: merge two sorted arrays/lists, intersection of sorted arrays.

public int[] mergeSorted(int[] a, int[] b) {

int i = 0, j = 0, k = 0;
int[] result = new int[[Link] + [Link]];
while (i < [Link] && j < [Link]) {
result[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];
}
while (i < [Link]) result[k++] = a[i++];
while (j < [Link]) result[k++] = b[j++];
return result;
}

7
9. Comparison of the patterns

Typical trigger
Type Pointer movement Complexity
words
“sorted”, “pair sum”,
A. Opposite/ left++ or right– based
“palindrome”, O(n)
Converging on comparison
“container”
both move forward, “remove”, “in-place”,
B. Fast/Slow (in-place) O(n)
different speeds/roles “move zeroes”
“subarray”,
right always advances,
C. Sliding Window “substring”, “at most/ O(n)
left conditionally
exactly K”
fast moves 2x speed “cycle”, “linked list”,
D. Floyd’s Cycle O(n)
of slow “middle node”
independent pointers “merge”, “two sorted
E. Merge O(n+m)
on two structures arrays”

Key distinguishing question: Are there two separate collections (→ Merge), one
collection with a fixed-size shrink (→ Converging), one collection with a growable/
shrinkable range (→ Sliding Window), or a “rewrite in place” (→ Fast/Slow)?

10. Quick decision checklist (use this in an interview)

1. Is data sorted or sortable without losing needed info? → Converging

2. Am I looking for a contiguous range satisfying a condition? → Sliding Window
3. Am I overwriting an array in place / removing elements? → Fast/Slow read-write
4. Am I merging or comparing two separate sorted structures? → Merge pointers
5. Is it a linked list with cycle/middle-finding needs? → Floyd’s fast/slow

If none of these fit and elements need to be looked up regardless of order/position, it’s
probably a hashmap problem instead, not two pointers. -e

8
Sweep Line — Complete Guide

1. What is it?

Sweep line is a technique where you imagine a vertical (or horizontal) line sweeping
across a set of events sorted by position (usually time, x-coordinate, or a numeric
range boundary), processing events in order and maintaining some running state (a
count, a running sum, an active set) as the line passes each event.

It converts a 2D or interval-overlap problem into a 1D ordered event-processing

problem.

2. Why is it used?

• Turns O(n²) pairwise interval/segment comparisons into O(n log n) sorted

processing
• Naturally handles “how many things are active at time X” without re-scanning
• Works well when the only thing that matters is order of events, not their exact
geometry
• Combines cleanly with a heap, ordered map (TreeMap), or difference array to track
“currently active” state

3. Where is it used?

• Interval scheduling / meeting rooms (min rooms needed, can attend all meetings)
• Merge intervals, insert interval
• Skyline problem (building silhouette)
• Maximum overlapping intervals / max concurrent events
• Calendar booking (detect double-booking, k-booking)
• Car pooling / trip overlap capacity problems
• Computational geometry: closest pair of points, segment intersection, rectangle
area/union
• Range update problems solvable via difference arrays

9
4. How to identify a Sweep Line problem (pattern
triggers)

Signal in the problem statement What it suggests

“intervals”, “meetings”, “events with start/end” Classic sweep line candidate
“maximum number of overlapping…” / “min
Event counting sweep
resources/rooms needed”
“at any point in time”, “concurrently” Sweep with a running counter
“skyline”, “silhouette”, “union of rectangles” Sweep + ordered structure (heap/TreeMap)
“book a meeting without conflict”, “k-th booking
Sweep with a count threshold
allowed”
Strong signal — sort by start (and sometimes
Multiple [start, end] pairs given
end)
“on a number line”, “range queries applied to
Difference array / sweep over deltas
array”

Paraphrase test: If the problem can be rephrased as “process a bunch of start/end

markers in order and track how many are open at once” — it’s sweep line.

5. Can you tell from constraints alone?

Yes: - Large n (up to 105–106) with intervals/points given → sorting-based O(n log n)
sweep is expected, since brute-force pairwise (O(n²)) is too slow. - If the problem only
asks for a count/aggregate at each moment (not exact geometric shapes) → simple
counter sweep suffices, no heap needed. - If it asks for the actual shape/skyline or
“which interval is active” → you need an ordered structure (heap or TreeMap) alongside
the sweep, not just a counter. - If updates apply to ranges of an array and you only
need the final array → difference array + prefix sum (a sweep variant) beats doing per-
index updates.

6. Intuition / Rationale

A sweeping line works because overlap/interval problems have a hidden 1D structure:

you don’t actually care about the shapes, you care about the sequence of moments
where the state changes — a start “opens” something, an end “closes” it. Between two
consecutive events, nothing changes, so you never need to examine the interior of an
interval — only its boundaries.

This is the same monotonicity idea as two pointers: once you sort events, you process
each boundary exactly once, and the running state (count, sum, or active set) is
updated incrementally rather than recomputed from scratch.

7. Time & Space Complexity (generic)

• Time: O(n log n) — dominated by sorting events (or the heap operations if used)

10
 • Space: O(n) for the event list / heap / active-interval structure

8. Types of Sweep Line (with Java templates)

Type A — Counting Sweep (max concurrent events)

Used for: meeting rooms II, max overlapping intervals, car pooling capacity check.

public int minMeetingRooms(int[][] intervals) {

int n = [Link];
int[] starts = new int[n];
int[] ends = new int[n];
for (int i = 0; i < n; i++) {
starts[i] = intervals[i][0];
ends[i] = intervals[i][1];
}
[Link](starts);
[Link](ends);

int rooms = 0, maxRooms = 0;

int s = 0, e = 0;
while (s < n) {
if (starts[s] < ends[e]) { // a meeting starts before another ends
rooms++;
s++;
} else { // a meeting ends, free a room
rooms--;
e++;
}
maxRooms = [Link](maxRooms, rooms);
}
return maxRooms;
}

Type B — Event List with +1/-1 Deltas

Used for: same problems as Type A, but generalizes better when you need to process by
exact timestamp order (ties handled explicitly — ends before starts at the same time, to
free a room before opening a new one).

11
 public int minMeetingRoomsDelta(int[][] intervals) {
List<int[]> events = new ArrayList<>(); // {time, delta}
for (int[] iv : intervals) {
[Link](new int[]{iv[0], 1}); // start: +1 active
[Link](new int[]{iv[1], -1}); // end: -1 active
}
// Sort by time; if tie, process ends (-1) before starts (+1)
[Link]((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);

int active = 0, maxActive = 0;

for (int[] ev : events) {
active += ev[1];
maxActive = [Link](maxActive, active);
}
return maxActive;
}

Type C — Sweep with a Heap (track which interval ends soonest)

Used for: skyline problem, whether a new meeting fits in an existing room, k-booking.

public boolean canAttendAll(int[][] intervals) {

[Link](intervals, (a, b) -> a[0] - b[0]); // sort by start
PriorityQueue<Integer> endTimes = new PriorityQueue<>(); // min-heap of end times

for (int[] iv : intervals) {

if (![Link]() && [Link]() <= iv[0]) {
[Link](); // free up the room that already ended
}
[Link](iv[1]);
}
return [Link]() <= 1; // or compare against room capacity
}

Type D — Difference Array (range updates on a fixed-size array/

line)

Used for: “add value to all indices in [l, r]” applied many times, then read final array.

public int[] applyRangeUpdates(int n, int[][] updates) {

int[] diff = new int[n + 1];
for (int[] u : updates) {
int l = u[0], r = u[1], val = u[2];
diff[l] += val;
diff[r + 1] -= val; // cancels the effect after r
}
int[] result = new int[n];
int running = 0;
for (int i = 0; i < n; i++) {
running += diff[i];
result[i] = running;
}
return result;
}

12
Type E — Coordinate Compression + Sweep (large/sparse
coordinate ranges)

Used for: skyline, rectangle union area, when coordinates span huge ranges but there
are few distinct values.

public int maxOverlapCompressed(int[][] intervals) {

TreeMap<Integer, Integer> deltaMap = new TreeMap<>(); // sorted by coordinate
for (int[] iv : intervals) {
[Link](iv[0], 1, Integer::sum);
[Link](iv[1], -1, Integer::sum);
}
int active = 0, maxActive = 0;
for (int delta : [Link]()) { // TreeMap iterates in sorted key order
active += delta;
maxActive = [Link](maxActive, active);
}
return maxActive;
}

9. Comparison of the patterns

Typical trigger
Type Structure used Complexity
words
A. Counting (two two pointers on sorted “min rooms”, “max
O(n log n)
sorted arrays) starts/ends overlap”
B. Event list with sorted list of (time, same as A, but needs
O(n log n)
deltas ±1) tie-breaking control
“skyline”, “k-booking”,
C. Heap-based sweep min-heap of end times O(n log n)
“can attend”
“apply range update”,
plain array + prefix
D. Difference array fixed small coordinate O(n + q)
sum
range
E. Coordinate huge/sparse
compression + sorted map of deltas coordinate range, still O(n log n)
TreeMap need overlap count

Key distinguishing question: Do I just need a running count (→ Type A/B), do I need to
know which specific interval is “active” or ending soonest (→ Type C heap), am I
applying repeated range updates to array indices (→ Type D), or are coordinates too
large/sparse for a plain array (→ Type E)?

10. Quick decision checklist (use this in an interview)

1. Do I only need a max/min concurrent count? → Type A or B

2. Do I need to know which interval is ending soonest, or simulate limited resources?
→ Type C (heap)
3. Am I applying many range-add updates to indices of a bounded array? → Type D
(difference array)

13
 4. Are the coordinates huge or sparse (not a small bounded range)? → Type E
(coordinate compression)
5. Does the problem also require me to reconstruct the actual overlapping shape
(e.g. skyline outline), not just a count? → Type C, output changes on every heap-
top update, not just count changes

If ties at the same coordinate need special handling (e.g. does a meeting ending at 10
conflict with one starting at 10?), always decide this explicitly in your sort comparator
— it’s the most common sweep-line bug.

11. Comparison with Two Pointers

Two Pointers Sweep Line

One (conceptual) pointer
Two indices moving toward/ moving through sorted
Core idea
along a single sorted array events derived from multiple
intervals/points
Usually a running sum/
Running count, active set, or
State tracked comparison between two
heap of “currently open” items
values
Count of overlaps, min
Pair/triplet, boolean, or a single
Typical output resources, or reconstructed
optimal value
shape
Intervals, points, or ranges (2
Data shape Flat array
numbers per item)
Type A sweep is two pointers,
just over two separate sorted
When they overlap —
arrays (starts, ends) instead of
one array from both ends

Sweep line is often thought of as “two pointers generalized to events with a start and
an end,” which is why Type A above looks almost identical to a two-pointer template. -e

14
Greedy Algorithms — Complete
Guide

1. What is it?

Greedy is a technique where at each step you make the locally optimal choice —
the choice that looks best right now — without reconsidering it later, and trust that the
sequence of locally optimal choices leads to a globally optimal solution.

Unlike DP, greedy never backtracks or explores alternatives — one pass, one decision
per step, done.

2. Why is it used?

• Much simpler and faster than DP or brute force when it’s provably correct (often
O(n log n) vs O(n²) or exponential)
• No extra memory for memoization tables
• Easy to reason about and implement once you’ve identified the right “greedy
criterion” (what to sort by / what to pick first)

3. Where is it used?

• Interval scheduling (max non-overlapping intervals, min intervals to remove)

• Activity selection / meeting attendance
• Jump game (reachability, min jumps)
• Gas station / circular tour feasibility
• Huffman encoding, minimum spanning tree (Kruskal’s, Prim’s)
• Task scheduling with cooldowns
• Assigning cookies / candies to children (two-pointer + greedy combo)
• Stock buy/sell (single pass, track running min/max)
• Coin change (only when denominations are canonical, e.g. US coins — NOT in
general)
• Huffman-style priority queue problems (merge stones, connect ropes)

15
4. How to identify a Greedy problem (pattern triggers)

Signal in the problem statement What it suggests

“maximum/minimum number of…” with simple Possible greedy — check if local choice is
constraints provably safe
“non-overlapping intervals” Sort by end time, greedily pick earliest-ending
“minimum number of steps/jumps/removals” Greedy reachability or interval-removal
“assign X to Y to satisfy as many as possible” Sort both sides, two-pointer greedy matching
“at each step choose the best/cheapest/largest
Explicit greedy phrasing
available”
Problem has an exchange argument feel —
Strong greedy signal
swapping two choices never makes it worse
Optimal substructure but NO overlapping
subproblems (each choice fully determines the Greedy over DP
rest, no need to “remember” alternatives)

Paraphrase test: If you can rephrase the problem as “if I always pick the best option
available right now, will I never regret it later?” and you can convince yourself yes (via
an exchange argument or contradiction), it’s greedy.

5. Can you tell from constraints alone?

Yes, partially: - If expected complexity is O(n log n) and DP would need O(n²) or worse,
that’s a hint towards greedy + sort. - Greedy problems rarely need extra memory
beyond O(1) or O(n) for sorting — if the intended solution needs a DP table, it’s usually
not pure greedy. - Caution: constraints alone can mislead you — many problems look
greedy but are DP in disguise (e.g. general coin change, 0/1 knapsack). Constraints only
tell you complexity expectations, not correctness of the greedy approach — you must
verify the greedy choice is provably safe (exchange argument or matroid structure), not
just assume it works because it’s fast.

6. Intuition / Rationale

Greedy works when the problem has two properties: 1. Greedy choice property — a
locally optimal choice can always be extended to a globally optimal solution (proved via
an exchange argument: assume an optimal solution doesn’t make the greedy choice,
show you can swap it in without making things worse). 2. Optimal substructure —
after making the greedy choice, the remaining subproblem is the same type of problem,
just smaller.

The exchange argument is the core proof technique: take any optimal solution, show
that replacing its first decision with the greedy decision doesn’t hurt (or only helps), and
repeat inductively. If you can’t construct this argument, greedy is likely wrong for the
problem — check DP instead.

16
Classic pitfall: 0/1 knapsack looks greedy (pick items with best value/weight ratio) but
isn’t — a locally best item can block a better combination later, because items can’t be
split. Fractional knapsack (where cutting off arbitrary weight is allowed) IS greedy,
because you never lose potential from a partial choice.

7. Time & Space Complexity (generic)

• Time: O(n log n) if sorting is required first, O(n) if no sort needed (e.g. single-pass
running-min/max problems)
• Space: O(1) extra beyond input/output, or O(n) if a heap/priority queue is used

8. Types of Greedy (with Java templates)

Type A — Interval Scheduling (sort by end time)

Used for: max non-overlapping intervals, min removals to make non-overlapping,

activity selection.

public int eraseOverlapIntervals(int[][] intervals) {

if ([Link] == 0) return 0;
[Link](intervals, (a, b) -> a[1] - b[1]); // sort by END time

int count = 0;
int lastEnd = intervals[0][1];
for (int i = 1; i < [Link]; i++) {
if (intervals[i][0] < lastEnd) {
count++; // overlap -> remove this interval (greedy: keep the one ending earlier)
} else {
lastEnd = intervals[i][1];
}
}
return count;
}

Type B — Single-Pass Running Min/Max

Used for: best time to buy/sell stock, gas station feasibility.

public int maxProfit(int[] prices) {

int minPriceSoFar = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
minPriceSoFar = [Link](minPriceSoFar, price); // greedy: track cheapest buy point
maxProfit = [Link](maxProfit, price - minPriceSoFar);
}
return maxProfit;
}

17
Type C — Reachability / Jump Game (extend the frontier greedily)

Used for: jump game, minimum jumps to reach end.

public boolean canJump(int[] nums) {

int farthestReachable = 0;
for (int i = 0; i < [Link]; i++) {
if (i > farthestReachable) return false; // stuck, can't even reach index i
farthestReachable = [Link](farthestReachable, i +
nums[i]); // greedy: always extend as far as possible
}
return true;
}

Type D — Two-Sorted-Array Matching (greedy pairing)

Used for: assign cookies, boats to save people (pair smallest with largest under a limit).

public int findContentChildren(int[] g, int[] s) { // g = children's greed factors, s = cookie sizes

[Link](g);
[Link](s);
int child = 0, cookie = 0;
while (child < [Link] && cookie < [Link]) {
if (s[cookie] >= g[child]) {
child++; // this cookie satisfies this child, greedily move to next child
}
cookie++; // this cookie is used up either way
}
return child;
}

Type E — Heap-Based Greedy (always combine the two smallest/

best)

Used for: merge stones/ropes with minimum cost, Huffman-style problems.

public int connectRopes(int[] ropes) {

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int r : ropes) [Link](r);

int totalCost = 0;
while ([Link]() > 1) {
int first = [Link]();
int second = [Link]();
int cost = first + second;
totalCost += cost; // greedy: always merge the two cheapest ropes first
[Link](cost);
}
return totalCost;
}

18
9. Comparison of the patterns

Core greedy Typical trigger

Type Complexity
criterion words
“non-overlapping”,
sort by end, keep
A. Interval scheduling “max activities”, “min O(n log n)
earliest finisher
removals”
track best-so-far in “buy/sell”, “max
B. Running min/max O(n)
one pass profit”, “single pass”
extend farthest “can you reach”, “min
C. Reachability frontier O(n)
reachable index jumps”
D. Two-sorted-array pair smallest feasible “assign”, “satisfy as
O(n log n)
matching match many as possible”
“minimum cost to
always combine two
E. Heap-based merge combine/merge”, O(n log n)
cheapest/smallest
“Huffman”

Key distinguishing question: Am I choosing between overlapping ranges (→ A), tracking

a best value seen so far (→ B), extending how far I can go (→ C), matching two separate
sorted lists (→ D), or repeatedly combining the two cheapest items (→ E)?

10. Quick decision checklist (use this in an interview)

1. Can I sort the input by some criterion (end time, ratio, value) such that picking
greedily in that order is safe? → Type A/D
2. Am I just tracking a running best value while scanning once? → Type B
3. Is the question “how far can I get” or “is X reachable”? → Type C
4. Do I need to repeatedly combine the two best/cheapest available options? → Type
E (heap)
5. Can I construct an exchange argument — “if the optimal solution didn’t make
this choice, I could swap it in without making things worse”? If yes → greedy is
provably correct. If no, and especially if items are indivisible/discrete with
interacting constraints → suspect DP instead.

19
11. Comparison with Two Pointers and Sweep Line

Two Pointers Sweep Line Greedy

Two indices moving Make locally optimal
Process sorted events,
Core idea through one sorted choice at each step,
track running state
array never revisit
Monotonicity of the
Same monotonicity, Exchange argument /
Correctness proof invariant (one move
applied to event order optimal substructure
only ever helps)
Pair/triplet, boolean, Count of overlaps, min Optimal count/cost/
Typical output
optimal value resources, shape sequence of picks
Type D “two-sorted- Type A interval sweep
array matching” above and Type A greedy
Overlap with greedy is literally a two- interval scheduling are —
pointer template used nearly the same code,
greedily different framing

In practice, greedy and two pointers/sweep line often coexist in the same solution —
sorting the input is a greedy setup step, and the pointer/sweep mechanics are how you
execute the greedy choices efficiently. If you’re identifying a problem as “greedy,” it’s
worth also asking whether the actual mechanics resemble a two-pointer or sweep-line
implementation. -e

20
Sliding Window — Complete Guide

1. What is it?

Sliding window is a technique where you maintain a contiguous range [left, right]
over an array or string, expanding it (moving right ) and shrinking it (moving left )
based on some condition, instead of re-scanning every possible subarray/substring from
scratch.

It’s really a specialized case of the same-direction two-pointer pattern, applied

specifically to contiguous ranges rather than arbitrary index pairs.

2. Why is it used?

• Avoids re-computing a subarray’s sum/count/frequency from scratch for every

window (O(n²) or O(n³) brute force → O(n))
• The window’s state (sum, character counts, distinct count) is updated incrementally
as it slides — add what enters, remove what leaves
• Works because of monotonicity: as the window grows, the property you’re tracking
changes predictably, so you never need to re-examine discarded parts

3. Where is it used?

• Longest/shortest substring with a condition (no repeating characters, at most K

distinct, contains all characters of another string)
• Maximum/minimum sum subarray of size K, or with a sum constraint
• Longest subarray with at most K zeros/replacements (flip problems)
• Anagram / permutation detection in a string
• Minimum window substring (shortest window containing all of a target’s characters)
• Fixed-size window problems (moving average, max in sliding window of size K)
• Count subarrays satisfying an exact condition (often via “at most K” − “at most
K-1” trick)

21
4. How to identify a Sliding Window problem (pattern
triggers)

Signal in the problem statement What it suggests

Strong signal — sliding window operates only on
“subarray” / “substring” (contiguous!)
contiguous ranges
“longest/shortest … satisfying condition” Variable-size window
“of size K” / “window of size K” Fixed-size window
“at most K distinct”, “no more than K”, “at least
Variable window with a shrink condition
K”
“contains all characters of”, “anagram of”, Frequency-map window (often fixed size for
“permutation of” permutation, variable for min window)
“sum equals/at least/at most target” over a Sum-tracking window (only works cleanly with
subarray non-negative numbers)
Brute force would be O(n²) checking every
Sliding window collapses it to O(n)
subarray

Paraphrase test: If the problem can be rephrased as “find the longest/shortest/count

of contiguous ranges where property P holds” — it’s sliding window. If “contiguous”
doesn’t apply (any subset, not just adjacent elements), it’s NOT sliding window — look
at subsets/DP/backtracking instead.

Important caveat: sliding window with a simple expand/shrink works cleanly when the
tracked quantity is monotonic as the window grows — e.g., sum of non-negative
numbers only increases as you add elements. If negative numbers are allowed, growing
the window doesn’t monotonically increase the sum, so plain sliding window breaks —
look at prefix sums + hashmap instead.

5. Can you tell from constraints alone?

Yes: - n up to 105–106 with an expected O(n) or O(n log n) solution, and the problem
mentions “subarray”/“substring” → sliding window is a prime candidate over brute
force. - If all values are non-negative (sums, counts, positive array elements) → sum/
count-based sliding window is safe. - If negative numbers are present and the problem
is about sum, sliding window alone won’t work — that’s usually prefix sum + hashmap
instead. - If the alphabet/character set is small and bounded (e.g., lowercase letters
only) → frequency-array window (size 26) instead of a hashmap, for O(1) per-character
updates.

22
6. Intuition / Rationale

The window is safe to slide because of a monotonic invariant, exactly like two
pointers: once the window’s property becomes invalid (e.g., sum too large, too many
distinct characters), shrinking from the left is the only useful move — you never need to
re-check a left boundary you’ve already advanced past, because any window starting
there was already accounted for as valid or invalid.

Each element is added to the window exactly once (when right passes it) and
removed exactly once (when left passes it), giving O(n) total work instead of O(n)
work repeated for O(n) different window start points.

7. Time & Space Complexity (generic)

• Time: O(n) — each pointer moves forward at most n times total

• Space: O(1) for simple sum tracking, O(k) or O(26)/O(128) for a frequency map/
array (k = distinct elements tracked)

8. Types of Sliding Window (with Java templates)

Type A — Fixed-Size Window

Used for: max sum subarray of size K, moving average, max/min in window of size K
(with a deque).

public int maxSumFixedWindow(int[] nums, int k) {

int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += nums[i]; // build initial window
int maxSum = windowSum;

for (int right = k; right < [Link]; right++) {

windowSum += nums[right] - nums[right - k]; // slide: add new, remove oldest
maxSum = [Link](maxSum, windowSum);
}
return maxSum;
}

Type B — Variable-Size Window (shrink while invalid)

Used for: longest subarray with sum ≤ K, longest substring with at most K distinct
characters.

23
 public int longestSubarrayAtMostK(int[] nums, int k) {
int left = 0, sum = 0, maxLen = 0;
for (int right = 0; right < [Link]; right++) {
sum += nums[right];
while (sum > k) { // shrink while window is invalid
sum -= nums[left];
left++;
}
maxLen = [Link](maxLen, right - left + 1); // window is valid here
}
return maxLen;
}

Type C — Variable-Size Window (expand while invalid, shrink while

valid — “shortest” variant)

Used for: minimum window substring, smallest subarray with sum ≥ target.

public int minSubArrayLen(int target, int[] nums) {

int left = 0, sum = 0, minLen = Integer.MAX_VALUE;
for (int right = 0; right < [Link]; right++) {
sum += nums[right];
while (sum >= target) { // shrink while window is still valid, to find the minimum
minLen = [Link](minLen, right - left + 1);
sum -= nums[left];
left++;
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

Type D — Frequency Map Window (character/element matching)

Used for: minimum window substring, find all anagrams, permutation in string.

24
 public String minWindow(String s, String t) {
if ([Link]() || [Link]()) return "";
Map<Character, Integer> need = new HashMap<>();
for (char c : [Link]()) [Link](c, 1, Integer::sum);

Map<Character, Integer> window = new HashMap<>();

int have = 0, needCount = [Link]();
int left = 0, bestLen = Integer.MAX_VALUE, bestStart = 0;

for (int right = 0; right < [Link](); right++) {

char c = [Link](right);
[Link](c, 1, Integer::sum);
if ([Link](c) && [Link](c).intValue() == [Link](c).intValue()) {
have++; // this character's frequency requirement is now fully satisfied
}

while (have == needCount) { // window is valid, try to shrink from the left
if (right - left + 1 < bestLen) {
bestLen = right - left + 1;
bestStart = left;
}
char leftChar = [Link](left);
[Link](leftChar, [Link](leftChar) - 1);
if ([Link](leftChar) && [Link](leftChar) < [Link](leftChar)) {
have--; // shrinking broke the requirement for this character
}
left++;
}
}
return bestLen == Integer.MAX_VALUE ? "" : [Link](bestStart, bestStart + bestLen);
}

Type E — “At Most K” Subtraction Trick (count exact-K subarrays)

Used for: count subarrays with exactly K distinct elements, exactly K odd numbers, etc.

public int subarraysWithExactlyKDistinct(int[] nums, int k) {

return atMostKDistinct(nums, k) - atMostKDistinct(nums, k - 1);
}

private int atMostKDistinct(int[] nums, int k) {

if (k < 0) return 0;
Map<Integer, Integer> count = new HashMap<>();
int left = 0, result = 0;
for (int right = 0; right < [Link]; right++) {
[Link](nums[right], 1, Integer::sum);
while ([Link]() > k) {
int leftVal = nums[left];
[Link](leftVal, [Link](leftVal) - 1);
if ([Link](leftVal) == 0) [Link](leftVal);
left++;
}
result += right - left + 1; // every window ending at `right` with ≤k distinct counts
}
return result;
}

25
9. Comparison of the patterns

Typical trigger
Type Window behavior Complexity
words
slides one step at a “size K”, “moving
A. Fixed-size O(n)
time, constant width average”
B. Variable — longest expand right, shrink
“longest … at most K” O(n)
under a cap while invalid
C. Variable — shortest expand right, shrink “shortest/minimum …
O(n)
meeting a target while still valid at least”
tracks character/ “anagram”,
O(n) (O(26) or O(k) per
D. Frequency map element counts, not “permutation”,
step)
just a sum “contains all of t”
E. At-most-K two calls to Type B “exactly K distinct/
O(n)
subtraction variant odd/etc.”

Key distinguishing question: Is the window always the same width (→ A), am I
maximizing width under a constraint (→ B), minimizing width while meeting a threshold
(→ C), matching character frequencies (→ D), or counting subarrays with an EXACT
property (→ E, via the at-most trick)?

10. Quick decision checklist (use this in an interview)

1. Is the window a fixed size K? → Type A

2. Am I looking for the longest window that stays valid (sum ≤ K, ≤K distinct)? → Type
B (shrink while invalid)
3. Am I looking for the shortest window that becomes valid (sum ≥ target, contains all
of t)? → Type C (shrink while valid, to minimize)
4. Do I need to track per-character/per-element frequency rather than just a sum/
count? → Type D
5. Does the problem ask for an EXACT count/value rather than longest/shortest? →
Type E, compute atMost(k) - atMost(k-1)
6. Are negative numbers involved and the property is sum-based? → Not sliding
window — use prefix sum + hashmap instead

26
11. Comparison with Two Pointers, Sweep Line, and
Greedy

Two Pointers Sliding Window Sweep Line Greedy

Two indices over A contiguous
Process sorted
one array, often range [left, Locally optimal
Core idea events, track
converging from right] that choice each step
running state
ends expands/shrinks
Any two positions Always
(not necessarily contiguous — the Points/intervals N/A — a decision
Range shape
contiguous range itself is the sorted by position strategy
between them) answer
Length, count, or Count of
Pair/triplet, Optimal count/
Typical output substring/ overlaps, min
boolean cost/sequence
subarray itself resources
Sliding window IS
Fixed-size sweep- Greedy criterion
a two-pointer
window over often decides
pattern,
Relationship — event time is how the window
specialized to
conceptually should shrink/
contiguous
similar expand
ranges

The cleanest mental model: two pointers is the general family (opposite-direction,
same-direction, merge, fast/slow). Sliding window is specifically the “same-direction,
contiguous range” member of that family, applied whenever the answer must be a
contiguous piece of the array/string. If contiguity doesn’t matter, you’re back to general
two pointers or a different technique entirely. -e

27
DFS & BFS — Complete Guide

1. What is it?

DFS (Depth-First Search) and BFS (Breadth-First Search) are the two fundamental
traversal techniques for graphs and trees.

• DFS goes as deep as possible down one path before backtracking — implemented
via recursion or an explicit stack.
• BFS explores level by level, visiting all neighbors at the current distance before
going further — implemented via a queue.

Both visit every reachable node exactly once (with a visited set), but the order and the
guarantees differ, which is what determines which one you need.

2. Why is it used?

• Systematic way to explore all nodes/paths in a graph or tree without missing or

repeating any
• BFS gives the shortest path in an unweighted graph for free, because it
explores in increasing distance order
• DFS naturally expresses exhaustive exploration (all paths, all combinations,
backtracking) and structural properties (cycles, connectivity, topological order)
• Both run in O(V + E) — visiting every vertex and edge once — which is optimal for
graph traversal

3. Where is it used?

DFS: - Path existence / all paths between two nodes - Cycle detection (directed and
undirected graphs) - Topological sort - Connected components / islands (grid flood fill) -
Backtracking: permutations, combinations, subsets, N-Queens, Sudoku - Tree traversals
(preorder, inorder, postorder)

BFS: - Shortest path in unweighted graph / grid - Level-order tree traversal - Minimum
number of steps/moves (word ladder, sliding puzzle) - Multi-source spreading (rotting
oranges, walls and gates) - Bipartite graph checking (via 2-coloring while traversing
levels)

28
4. How to identify a DFS vs BFS problem (pattern
triggers)

Signal in the problem statement What it suggests

“shortest path”, “minimum steps/moves”, BFS — guarantees shortest path in unweighted
“fewest number of…” graphs
“all paths”, “does a path exist”, “explore every
DFS — exhaustive exploration
possibility”
“level order”, “print level by level”, “distance
BFS — processes nodes in distance order
from source”
“connected components”, “number of islands”, Either works — DFS is usually simpler to write
“flood fill” (recursion)
DFS — track recursion stack (directed) or
“cycle detection”
parent (undirected)
“topological order”, “course schedule”, “build DFS (postorder + reverse) or BFS (Kahn’s
order” algorithm)
“generate all subsets/permutations/ DFS (backtracking) — BFS doesn’t naturally
combinations” express choice-branching with undo
“nearest”, “closest”, “minimum time to reach all
BFS, often multi-source
nodes”
Neither plain DFS nor BFS — needs Dijkstra/
Weighted graph + “shortest path”
Bellman-Ford instead

Paraphrase test: If the problem asks “what is the minimum distance/steps” in an

unweighted setting — BFS. If it asks “does X exist”, “find all X”, or “can you reach”
without needing the shortest route — DFS.

5. Can you tell from constraints alone?

Yes, partially: - Grid/graph size up to 104–106 nodes/cells with expected O(V+E) → either
DFS or BFS traversal is intended; the choice between them comes from what’s being
asked (shortest vs exhaustive), not from constraints. - If recursion depth could exceed
~10^4 (deep/skewed trees, long chains), a recursive DFS risks stack overflow in
Java — prefer iterative DFS with an explicit stack, or use BFS instead. - If the problem
says “minimum” or “shortest” AND edges are unweighted (all cost 1) → BFS, not DFS,
even though DFS could technically find a path — it won’t guarantee the shortest one
without extra bookkeeping. - If weights are involved despite looking like a shortest-path
problem → neither DFS nor BFS is sufficient; that’s a Dijkstra/Bellman-Ford signal.

6. Intuition / Rationale

Why BFS finds the shortest path: BFS processes nodes in strict order of distance
from the source — it fully exhausts all nodes at distance d before touching any node at
distance d+1 . The first time you reach the target, it’s guaranteed to be via the shortest
possible number of edges, because no longer path could have reached it first.

29
Why DFS is natural for exhaustive search: DFS’s call stack IS the current path
being explored. This makes it trivial to backtrack (undo the last choice and try another)
— which is exactly what problems like permutations, N-Queens, and path-finding-with-
constraints need. BFS’s queue doesn’t preserve “the current path” in the same
accessible way, making backtracking awkward.

Why both need a visited set: without it, cyclic graphs cause infinite loops — you’d
keep re-visiting the same nodes forever. Trees don’t strictly need one (no cycles), but
graphs always do.

7. Time & Space Complexity (generic)

• Time: O(V + E) for both — every vertex visited once, every edge examined once
• Space:
◦ DFS: O(V) for the visited set + O(H) for the recursion/explicit stack, where H is
the max depth (worst case O(V) for a skewed graph)
◦ BFS: O(V) for the visited set + O(W) for the queue, where W is the max width of
a level (worst case O(V))

8. Types of DFS & BFS (with Java templates)

Type A — Recursive DFS (graph/tree traversal)

Used for: path existence, connected components, general traversal.

public void dfs(int node, Map<Integer, List<Integer>> graph, Set<Integer> visited) {

if ([Link](node)) return;
[Link](node);
// process(node) here

for (int neighbor : [Link](node, new ArrayList<>())) {

dfs(neighbor, graph, visited);
}
}

Type B — Iterative DFS (explicit stack, avoids recursion depth

limits)

Used for: same as Type A, but safe for very deep/large graphs.

30
 public void dfsIterative(int start, Map<Integer, List<Integer>> graph) {
Set<Integer> visited = new HashSet<>();
Deque<Integer> stack = new ArrayDeque<>();
[Link](start);

while (![Link]()) {
int node = [Link]();
if ([Link](node)) continue;
[Link](node);
// process(node) here

for (int neighbor : [Link](node, new ArrayList<>())) {

if () [Link](neighbor);
}
}
}

Type C — BFS (shortest path / level order)

Used for: shortest path in unweighted graph, level-order traversal, min steps.

public int bfsShortestPath(int start, int target, Map<Integer, List<Integer>> graph) {

Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
[Link](start);
[Link](start);
int steps = 0;

while (![Link]()) {
int size = [Link](); // process one full level at a time
for (int i = 0; i < size; i++) {
int node = [Link]();
if (node == target) return steps;

for (int neighbor : [Link](node, new ArrayList<>())) {

if () {
[Link](neighbor);
[Link](neighbor);
}
}
}
steps++; // moved to the next level/distance
}
return -1; // target not reachable
}

Type D — Grid DFS (flood fill / connected regions)

Used for: number of islands, flood fill, max area of island.

31
 public int numIslands(char[][] grid) {
int rows = [Link], cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
int count = 0;

for (int r = 0; r < rows; r++) {

for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1' && !visited[r][c]) {
dfsGrid(grid, visited, r, c);
count++; // found a new island, explore all of it
}
}
}
return count;
}

private void dfsGrid(char[][] grid, boolean[][] visited, int r, int c) {

if (r < 0 || r >= [Link] || c < 0 || c >= grid[0].length) return;
if (visited[r][c] || grid[r][c] == '0') return;
visited[r][c] = true;

dfsGrid(grid, visited, r + 1, c);

dfsGrid(grid, visited, r - 1, c);
dfsGrid(grid, visited, r, c + 1);
dfsGrid(grid, visited, r, c - 1);
}

Type E — Multi-Source BFS

Used for: rotting oranges, walls and gates, spreading from multiple starting points
simultaneously.

32
 public int multiSourceBFS(int[][] grid) {
int rows = [Link], cols = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
int freshCount = 0;

for (int r = 0; r < rows; r++) {

for (int c = 0; c < cols; c++) {
if (grid[r][c] == 2) [Link](new int[]{r, c}); // seed ALL sources at once
else if (grid[r][c] == 1) freshCount++;
}
}

int minutes = 0;
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
while (![Link]() && freshCount > 0) {
int size = [Link]();
for (int i = 0; i < size; i++) {
int[] cell = [Link]();
for (int[] d : dirs) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
grid[nr][nc] = 2;
freshCount--;
[Link](new int[]{nr, nc});
}
}
}
minutes++;
}
return freshCount == 0 ? minutes : -1; // -1 if some fresh cells unreachable
}

Type F — Backtracking DFS (explicit undo)

Used for: permutations, combinations, subsets, N-Queens.

33
 public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, new ArrayList<>(), new boolean[[Link]], result);
return result;
}

private void backtrack(int[] nums, List<Integer> current, boolean[] used, List<List<Integer>>

result) {
if ([Link]() == [Link]) {
[Link](new ArrayList<>(current)); // copy — current will keep mutating
return;
}
for (int i = 0; i < [Link]; i++) {
if (used[i]) continue;
used[i] = true;
[Link](nums[i]);

backtrack(nums, current, used, result); // explore

[Link]([Link]() - 1); // undo (the "back" in backtracking)

used[i] = false;
}
}

9. Comparison of the patterns

Typical trigger
Type Structure Complexity
words
“traverse”, “path
A. Recursive DFS call stack O(V+E)
exists”, “connected”
same as A, but very
B. Iterative DFS explicit Deque as stack O(V+E)
deep/large graphs
“shortest path”, “min
C. BFS Queue , level-by-level O(V+E)
steps”, “level order”
recursion over 2D “islands”, “flood fill”,
D. Grid DFS O(rows × cols)
array “connected region”
“simultaneously
queue seeded with
E. Multi-source BFS spread”, “min time to O(rows × cols)
multiple starts
reach all”
recursion + explicit “all permutations/
F. Backtracking DFS O(branching^depth)
undo step combinations/subsets”

Key distinguishing question: Do I need the shortest/minimum distance (→ C or E, BFS),

am I exploring a grid region (→ D), am I generating all valid arrangements with undo (→
F), or is it general reachability/structure (→ A/B, DFS)?

10. Quick decision checklist (use this in an interview)

1. Does the problem need shortest path / minimum steps in an unweighted graph? →
BFS (Type C)

34
 2. Are there multiple simultaneous starting points spreading outward? → Multi-
source BFS (Type E)
3. Do I need to generate all valid combinations/arrangements, with the ability to undo
a choice? → Backtracking DFS (Type F)
4. Is it a 2D grid asking about connected regions/islands? → Grid DFS (Type D) (BFS
works too, DFS is usually simpler to write)
5. Is the graph very deep or could cause a stack overflow with recursion? → Iterative
DFS (Type B)
6. Otherwise — general traversal, cycle detection, topological sort → Recursive DFS
(Type A)
7. Are edges weighted and you still need shortest path? → Neither — use Dijkstra
(non-negative weights) or Bellman-Ford (negative weights allowed)

11. Comparison with Two Pointers, Sliding Window,

Sweep Line, and Greedy

Two Pointers / Sliding

Window / Sweep Line / DFS / BFS
Greedy
Linear (array, sorted events, Graph/tree structure (nodes +
Data shape
intervals) edges, possibly a grid)
Pointer(s) advancing through a
Traversal following edges/
Core mechanism sequence with a monotonic
adjacency, with branching
invariant
None — a discarded position is DFS backtracking explicitly re-
Backtracking
never revisited visits/undoes choices
Grid BFS/DFS problems
sometimes combine with a
sweep-like “process by
When they meet —
distance/level” idea (Type E is
essentially a sweep line over
graph distance)

The core difference: earlier patterns (two pointers, sliding window, sweep line, greedy)
all operate on flat, ordered sequences where you never branch. DFS/BFS operate on
branching structures — there isn’t one path forward, there are potentially many, and
the choice of DFS vs BFS is about which order you explore those branches in. -e

35
Recursion — Complete Guide

1. What is it?

Recursion is when a function calls itself to solve smaller instances of the same
problem, until it reaches a base case simple enough to answer directly. The results of
the smaller calls are then combined to build the answer to the original problem.

Every recursive function needs exactly two parts: 1. Base case(s) — the condition(s)
where the function stops calling itself and returns directly. 2. Recursive case — where
the function calls itself on a smaller/simpler version of the input, and combines that
result into the current answer.

2. Why is it used?

• Naturally expresses problems that are self-similar — the solution to size n is built
from the solution to a smaller size
• Often dramatically simpler to read/write than the equivalent iterative version (tree
traversals, backtracking, divide and conquer)
• The call stack gives you “free” backtracking — undoing a choice is often just
returning from the call
• It’s the natural language for problems defined recursively in the first place (trees,
nested structures, mathematical recurrences)

3. Where is it used?

• Tree and graph traversal (DFS is inherently recursive)

• Divide and conquer (merge sort, quick sort, binary search)
• Backtracking (permutations, combinations, subsets, N-Queens, Sudoku)
• Dynamic programming (top-down / memoized recursion)
• Mathematical recurrences (factorial, Fibonacci, power, GCD)
• Nested/recursive data structures (nested lists, JSON parsing, file system traversal)
• String/array problems expressible as “solve for the rest after handling the first/last
element”

36
4. How to identify a Recursion problem (pattern triggers)

Signal in the problem statement What it suggests

“tree”, “nested”, data structure defined in
Recursion mirrors the data’s own definition
terms of itself
“all possible ways to…”, “generate all…” Recursion + backtracking
Problem naturally splits into “solve for smaller
Divide and conquer recursion
input, then combine”
“the answer for n depends on the answer for
Direct recursive recurrence
n-1 (or smaller)”
You can describe the solution as “do X, then
Strong recursion signal
recursively solve the rest”
Problem involves undo/backtrack after trying a
Recursion (backtracking specifically)
choice

Paraphrase test: If you can finish the sentence “the answer to a problem of size n is
[some combination of] the answer(s) to problem(s) of smaller size” — that’s a recursive
definition, and the code should mirror it directly.

5. Can you tell from constraints alone?

Yes, partially: - Small n (≤ ~20–25) with an expected exponential-looking solution (“all

subsets”, “all permutations”) → recursion/backtracking is expected; brute-force
enumeration is intentional at that size. - Large n (10^4+) with a naive recursive
recurrence and overlapping subproblems (e.g. Fibonacci) → plain recursion will time out;
you need memoization (top-down DP) or an iterative bottom-up version. - Very deep
recursion (chain-like structures, n up to 104–105) → risk of StackOverflowError in Java;
prefer converting to iteration or increasing stack size deliberately, don’t assume
recursion is safe just because it’s simple. - If overlapping subproblems exist (the same
sub-call happens many times with identical inputs) → recursion alone is exponential;
add memoization.

6. Intuition / Rationale

Recursion works because of mathematical induction: if you can prove the base case
is correct, and prove that the recursive case is correct assuming smaller sub-calls are
correct, then by induction the function is correct for all valid inputs. You don’t need to
trace every call by hand — you only need to trust the recursive leap of faith once the
base case and the inductive step are both verified.

The “leap of faith”: when writing return solve(n-1) + something; , you should not
mentally unroll what solve(n-1) does internally — you should assume it’s already
correct (by the inductive hypothesis) and focus only on how to correctly build the
answer for n from that assumed-correct result. This is the single biggest mental shift
that makes recursion easy to write instead of confusing.

37
Why the call stack matters: each recursive call gets its own stack frame with its own
local variables. This is what makes backtracking trivial — when a call returns, its local
state (e.g. [Link](x) before the call, [Link](x) after) naturally “undoes”
as control returns to the caller, without needing to manually manage a global undo
stack.

7. Time & Space Complexity (generic)

• Time: depends entirely on the recurrence relation.

◦ One recursive call per level, shrinking input by a constant amount (e.g. n-1 ) →
O(n)
◦ Two recursive calls per level without memoization, each shrinking by 1
(e.g. naive Fibonacci) → O(2^n)
◦ One call, shrinking input by half (e.g. binary search) → O(log n)
◦ Two calls, each on half the input (e.g. merge sort) → O(n log n)
• Space: O(depth of recursion) for the call stack, regardless of how many total
calls are made — this is the most commonly mis-estimated part. Naive Fibonacci
makes O(2^n) calls but only ever has O(n) stack frames alive at once, so its space
complexity is O(n), not O(2^n).

8. Types of Recursion (with Java templates)

Type A — Linear Recursion (single recursive call)

Used for: factorial, sum of array, simple traversal of a linked structure.

public int factorial(int n) {

if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case: trust factorial(n-1) is correct
}

Type B — Divide and Conquer (multiple calls on disjoint sub-inputs)

Used for: merge sort, quick sort, binary search, tree height/depth.

public void mergeSort(int[] arr, int left, int right) {

if (left >= right) return; // base case: 0 or 1 elements, already sorted

int mid = left + (right - left) / 2;

mergeSort(arr, left, mid); // solve left half
mergeSort(arr, mid + 1, right); // solve right half
merge(arr, left, mid, right); // combine the two sorted halves
}

Type C — Tree Recursion (mirrors the tree’s own structure)

Used for: tree traversals, tree depth, validate BST, tree sum.

38
 public int maxDepth(TreeNode root) {
if (root == null) return 0; // base case: empty tree has depth 0

int leftDepth = maxDepth([Link]); // trust this is correct (leap of faith)

int rightDepth = maxDepth([Link]); // trust this is correct too
return 1 + [Link](leftDepth, rightDepth); // combine: this node + deeper subtree
}

Type D — Backtracking (explore, then undo)

Used for: permutations, combinations, subsets, N-Queens, word search.

public List<List<Integer>> subsets(int[] nums) {

List<List<Integer>> result = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), result);
return result;
}

private void backtrack(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {
[Link](new ArrayList<>(current)); // every state along the way is a valid subset

for (int i = start; i < [Link]; i++) {

[Link](nums[i]); // choose
backtrack(nums, i + 1, current, result); // explore
[Link]([Link]() - 1); // un-choose (backtrack)
}
}

Type E — Memoized Recursion (top-down DP)

Used for: Fibonacci, climbing stairs, any recursion with overlapping subproblems.

public long fib(int n, Map<Integer, Long> memo) {

if (n <= 1) return n; // base case
if ([Link](n)) return [Link](n); // avoid recomputing a solved subproblem

long result = fib(n - 1, memo) + fib(n - 2, memo);

[Link](n, result); // cache before returning
return result;
}

Type F — Mutual/Indirect Recursion (two functions call each other)

Used for: parsing recursive grammars, alternating state machines (less common in
interviews, but appears in parsers).

39
 public boolean isEven(int n) {
if (n == 0) return true;
return isOdd(n - 1);
}

public boolean isOdd(int n) {

if (n == 0) return false;
return isEven(n - 1);
}

9. Comparison of the patterns

Number of recursive Typical trigger

Type Complexity driver
calls words
1 call, shrinks by “compute for n based
A. Linear O(n) time, O(n) space
constant on n-1”
2+ calls on disjoint “sort”, “search”, split
B. Divide and conquer O(n log n) typical
sub-ranges problem in half
1 call per child (2 for “tree”, “depth”, O(n) time (n = node
C. Tree recursion
binary tree) “traverse” count), O(h) space
Variable — one call per “all permutations/ O(branching^depth),
D. Backtracking
choice, with undo combinations/subsets” often exponential
overlapping
Same shape as A/C but O(number of unique
E. Memoized subproblems, “number
cached subproblems)
of ways”
Alternates between grammar/parsing
F. Mutual depends on recurrence
two+ functions problems

Key distinguishing question: Does the problem split into independent sub-ranges (→ B),
mirror a tree’s own shape (→ C), require generating all choices with undo (→ D), have
overlapping subproblems recomputed many times (→ E, add memoization), or is it a
straightforward “smaller version of the same problem” (→ A)?

10. Quick decision checklist (use this in an interview)

1. Can I state the base case(s) first — the smallest input(s) I can answer without
recursing? Always start here.
2. Does my recursive case call the function on a strictly smaller input, guaranteeing
eventual termination? If not, infinite recursion.
3. Am I trusting the recursive call’s result (leap of faith) instead of trying to mentally
trace every nested call?
4. Do I need to undo a choice after exploring it (add to a list, then remove)? →
Backtracking (Type D)
5. Will the same sub-call happen with identical arguments more than once? → add a
memo map (Type E) before it becomes exponential
6. Is the recursion depth potentially very large (deep chains, large n)? → consider
converting to iteration to avoid StackOverflowError

40
 7. Does the problem split cleanly into independent halves that don’t need to “know”
about each other until combined? → Divide and conquer (Type B)

11. Comparison with DFS/BFS and the other patterns

Recursion (general) DFS Backtracking

A specific application
A specific application
The general of recursion with
Relationship of recursion to graph/
mechanism explicit choose/
tree traversal
explore/un-choose
A decision tree of
Any self-similar sub- Nodes/edges of a choices (not
What’s being explored
problem graph or tree necessarily a “real”
graph)
Rarely (just mark Always — that’s the
Undo needed? Only if backtracking
visited) defining feature

The cleanest mental model: recursion is the umbrella technique. DFS is recursion
specifically applied to graph/tree adjacency. Backtracking is recursion specifically
applied to a decision tree where you must undo a choice to try the next one. Divide and
conquer is recursion where sub-calls are on independent, non-overlapping pieces of
input that get merged afterward. Memoized recursion (top-down DP) is recursion plus a
cache, used when sub-calls overlap. Once you see recursion as the shared foundation,
DFS/backtracking/divide-and-conquer/DP all become “recursion + one extra rule,” not
separate things to memorize from scratch. -e

41