QUICK_REFERENCE

Quick Reference Guide

Pattern Recognition Cheat Sheet

When you see these keywords → Think these patterns

Problem Keywords	Pattern	Example Problems
”sorted array”, “find pair/triplet”	Two Pointers	Two Sum II, 3Sum, Container With Water
”contiguous subarray”, “substring”	Sliding Window	Max Sum Subarray, Longest Substring
”sorted”, “find in log(n)“	Binary Search	Search Insert Position, Find Peak
”find in O(1)”, “frequency”, “pairs”	HashMap	Two Sum, Anagrams, Subarray Sum
”k most/least”, “top k”	Heap	Top K Elements, Kth Largest
”graph/tree traversal”	DFS/BFS	Island Count, Level Order
”overlapping problems”, “optimal choice”	DP	Climbing Stairs, Coin Change
”connected components”, “cycles”	Union Find	Number of Islands, Redundant Connection

Complexity Quick Reference

Pattern	Typical Time	Typical Space
Two Pointers	O(n)	O(1)
Sliding Window	O(n)	O(k)
Binary Search	O(log n)	O(1)
HashMap	O(n)	O(n)
Heap	O(n log k)	O(k)
DFS/BFS	O(V + E)	O(V)
DP	O(n²) to O(n)	O(n)

Java Version Quick Notes

Java 17 Features (Available)

• Sealed classes
• Pattern matching for instanceof
• Text blocks
• Records
• Switch expressions (enhanced)

Java 21+ Features (Mark with comment)

// Java 21+ - Pattern matching for switch
String result = switch (obj) {
    case Integer i when i > 0 -> "positive";
    case Integer i -> "non-positive";
    case String s -> s;
    default -> "unknown";
};
 
// Java 21+ - Record patterns
record Point(int x, int y) {}
if (obj instanceof Point(int x, int y)) {
    // Use x and y directly
}
 
// Java 21+ - Unnamed patterns
if (obj instanceof Point(int x, _)) {
    // Don't care about y
}
 
// Java 21+ - Virtual threads
Thread.startVirtualThread(() -> {
    // Lightweight thread for I/O-bound tasks
});

Common Pitfalls & Tips

Two Pointers

• ✅ Remember to sort if needed (check if sorting changes problem)
• ❌ Don’t forget to skip duplicates in 3Sum-style problems
• ✅ Choose right pointer direction: opposite or same direction

Sliding Window

• ✅ Expand until invalid, then shrink
• ❌ Don’t recalculate window from scratch each time
• ✅ Use array for small alphabets, HashMap for large

Binary Search

• ✅ Use left + (right - left) / 2 to avoid overflow
• ❌ Watch infinite loops in right boundary search (need +1)
• ✅ Verify monotonicity for “binary search on answer”

HashMap

• ✅ Use getOrDefault() for cleaner code
• ❌ Don’t modify keys after insertion
• ✅ Consider LinkedHashMap if order matters

General

• ✅ Always analyze space-time tradeoffs
• ❌ Don’t optimize prematurely (correct first, fast second)
• ✅ Test edge cases: empty, single element, duplicates

Interview Strategy

1. Clarify (2 min)

   • Input constraints (size, range, duplicates?)
   • Output format
   • Edge cases

2. Plan (5 min)

   • Identify pattern
   • Discuss brute force
   • Optimize (what’s bottleneck?)

3. Implement (20 min)

   • Start with helper functions
   • Handle edge cases
   • Use meaningful names

4. Test (5 min)

   • Walk through example
   • Edge cases
   • Complexity analysis

5. Optimize (3 min)

   • Discuss alternatives
   • Space-time tradeoffs

Compile & Run

# Compile single file
javac src/patterns/TwoPointers.java
 
# Run
java -cp src patterns.TwoPointers
 
# Compile all
javac src/patterns/*.java
 
# With Java 21 features (if using Java 21+)
javac --release 21 src/patterns/*.java
java -cp src patterns.PatternName

Next Steps

1. ✅ Review pattern in src/patterns/
2. ✅ Read practice session in practice-sessions/
3. ✅ Attempt problem without looking at solution
4. ✅ Compare your solution with provided approaches
5. ✅ Understand tradeoffs
6. ✅ Practice explaining complexity analysis