Hello EveryOne 👋
So... Part 1 happened. I shared my journey with the first 6 patterns.
But then came the reality check.
Placements are coming. Like, ACTUALLY coming. In 3 months. 😱
Me: internal panic
I started preparing seriously. And I realized something terrifying:
The patterns from Part 1? They got me through EASY and MEDIUM problems.
But HARD problems? Completely different ball game. 😱
💔 The New Struggle (December 2025)
Week 1 of Serious Prep:
I opened my first HARD problem: "Merge K Sorted Lists"
Stared at it for 2 hours. Zero progress.
Looked at solution: "Use a Min Heap"
Me: "What the hell is a Min Heap??" 🤯
Week 2:
Tried a DP problem: "Longest Palindromic Subsequence"
Spent 3 hours. Got nowhere.
Solution had a…
Hello EveryOne 👋
So... Part 1 happened. I shared my journey with the first 6 patterns.
But then came the reality check.
Placements are coming. Like, ACTUALLY coming. In 3 months. 😱
Me: internal panic
I started preparing seriously. And I realized something terrifying:
The patterns from Part 1? They got me through EASY and MEDIUM problems.
But HARD problems? Completely different ball game. 😱
💔 The New Struggle (December 2025)
Week 1 of Serious Prep:
I opened my first HARD problem: "Merge K Sorted Lists"
Stared at it for 2 hours. Zero progress.
Looked at solution: "Use a Min Heap"
Me: "What the hell is a Min Heap??" 🤯
Week 2:
Tried a DP problem: "Longest Palindromic Subsequence"
Spent 3 hours. Got nowhere.
Solution had a 2D table. Formula I’d never seen.
Me: "Am I even smart enough for this?"
The Breaking Point (Again):
Placements start in 3 months. I’d solved 250 problems using the first 6 patterns.
But HARD problems? 0% success rate. Absolute zero.
Companies like Amazon, Microsoft, Oracle test HARD problems in OAs!
I called my senior (the Google guy): "Dude, I’m screwed. These problems are impossible."
Him: "Did you learn the advanced patterns?"
Me: "...there are MORE patterns??"
Him: laughs "Oh buddy. You’ve only scratched the surface."
🌟 What Changed (The Second Transformation)
He sent me his notes. 8 more patterns:
- Top K Elements (Heaps)
- Overlapping Intervals (The secret: always sort!)
- Modified Binary Search (Not just sorted arrays!)
- Tree Traversals (BFS/DFS strategies)
- Matrix Traversal (Grids as graphs)
- Backtracking (The decision tree)
- Dynamic Programming (Memoization patterns)
- Bit Manipulation (The secret weapon)
"Master these," he said, "and you’ll crack HARD problems."
I didn’t believe him. How could 8 more patterns make THAT much difference?
Narrator voice: They made ALL the difference.
📊 My Stats (Where I Am Now)
Before learning these patterns (2 months ago):
Success Rate on Hards: ~5%
Placement Readiness: Would fail instantly
Confidence Level: 2/10
Status: Panicking about placements
After learning these 8 patterns (current status):
Success Rate on Hards: 60%+ (still improving!)
Placement Readiness: Actually prepared!
Confidence Level: 7/10
Status: Ready to face OAs and interviews
The difference? I stopped seeing HARD problems as impossible. Started seeing them as pattern combinations.
I’m not done yet - still practicing every day, still making mistakes, still learning.
But now I know I CAN tackle hard problems. That’s HUGE! 💪
🎯 What This Guide Is
Full transparency (again):
- I’m a 3rd year CS student preparing for placements
- I’ve solved 200+ problems (not 2000, still grinding!)
- I haven’t given real interviews yet (placements comming!)
- I STILL get stuck sometimes (like, all the time 😅)
- But I now RECOGNIZE patterns (game changer!)
This guide is:
- My journey from "WTF is a heap" to actually solving heap problems
- Every mistake I made (SO MANY mistakes)
- The exact moments these patterns clicked for me
- Complete solutions with my actual thought process
- Honest confessions when I don’t fully understand something
- How I’m preparing for placements RIGHT NOW
Time Investment: 2-3 weekends to learn all 8
Difficulty: Intermediate to Advanced
Result: You’ll tackle HARD problems (like I am now!)
Current Status: Learning alongside you! 🚀
📚 Table of Contents
- Pattern 7: Top K Elements (Heaps)
- Pattern 8: Overlapping Intervals
- Pattern 9: Modified Binary Search
- Pattern 10: Tree Traversals (BFS/DFS)
- Pattern 11: Matrix Traversal
- Pattern 12: Backtracking
- Pattern 13: Dynamic Programming
- Pattern 14: Bit Manipulation
- How I Study Now
- Practice Session Stories
🎯 Pattern 7: Top K Elements (The Heap Awakening)
💭 My "What Even Is a Heap??" Moment
The Problem That Broke Me:
"Find K Largest Elements in Array"
My first thought: "Easy! Just sort and take last K elements!"
def findKLargest(nums, k):
nums.sort()
return nums[-k:]
# Works! But...
# Time: O(n log n) - sorting entire array
# Interviewer: "Can you do better?"
# Me: "...no?"
The interviewer: "What if the array has 1 million elements and K = 10?"
Me internally: Oh crap. Sorting 1 million numbers to get just 10?
🤯 The Heap Revelation
I Googled "better than sorting for K largest" and found: HEAPS
Read Wikipedia. Confused.
Read GeeksForGeeks. More confused.
Then I watched a video where the guy said:
"Think of a heap as a priority queue. It AUTOMATICALLY keeps the smallest/largest element on top."
My brain: "Wait... so I don’t have to sort??"
Exactly!
📚 What Even Is a Heap? (My Understanding)
A heap is a tree stored as an array with one rule:
Min Heap: Parent is SMALLER than children Max Heap: Parent is LARGER than children
Visual:
Min Heap:
1
/ \
3 2
/ \
5 4
Array representation: [1, 3, 2, 5, 4]
↑ Top element is SMALLEST!
Max Heap:
9
/ \
7 8
/ \
3 5
Array representation: [9, 7, 8, 3, 5]
↑ Top element is LARGEST!
The magic: Insert and remove in O(log n)!
No need to sort the entire array (O(n log n))! ✨
💡 The Counterintuitive Insight
This BLEW MY MIND when I finally got it:
To find K LARGEST elements, use a MIN HEAP! 🤯
"WHAT?? That makes NO SENSE!"
Here’s why it works:
Problem: Find 3 largest in [3, 2, 1, 5, 6, 4]
Strategy:
1. Build MIN heap of size K=3
2. For each new element:
- If larger than heap top (smallest), replace it
- If smaller, ignore it
Process:
nums = [3, 2, 1, 5, 6, 4], k = 3
Heap = [3, 2, 1] ← Top is 1 (smallest of 3)
See 5:
5 > 1 (top) → Remove 1, add 5
Heap = [3, 2, 5] ← Top is now 2
See 6:
6 > 2 (top) → Remove 2, add 6
Heap = [3, 5, 6] ← Top is now 3
See 4:
4 > 3 (top) → Remove 3, add 4
Heap = [4, 5, 6] ← Top is now 4
Result: [4, 5, 6] ✅ The 3 largest!
Why MIN heap for LARGEST elements:
The MIN heap’s top is the SMALLEST of the K largest.
If a new element is bigger than this smallest, we found a new "large" element!
When this clicked, I literally stood up and walked around my room. 🚶
💻 Problem #1: Kth Largest Element (The Foundation)
Problem: Find Kth Largest Element in Array (#215)
Example:
Input: [3,2,1,5,6,4], k = 2
Output: 5 (second largest)
My First Attempt (The Wrong Way):
def findKthLargest(nums, k):
"""
My initial thought:
"Just sort and return nums[-k]!"
Time: O(n log n) - too slow for large arrays
"""
nums.sort()
return nums[-k]
# Works but interviewer not impressed
# "Can you do O(n log k)?"
# Me: "Uhh... heap?"
After Learning Heaps:
import heapq
def findKthLargest(nums, k):
"""
Using MIN HEAP of size k!
Strategy:
1. Build heap with first k elements
2. For remaining elements:
- If larger than heap top, replace
- Else, skip
3. Top of heap is Kth largest!
Time: O(n log k) ✨ Much better!
"""
# Build min heap with first k elements
heap = nums[:k]
heapq.heapify(heap) # O(k)
# Process remaining elements
for num in nums[k:]:
if num > heap[0]: # If larger than smallest in heap
heapq.heappop(heap) # Remove smallest
heapq.heappush(heap, num) # Add new number
# Top of heap is Kth largest!
return heap[0]
# Test
print(findKthLargest([3,2,1,5,6,4], 2)) # 5 ✅
# Accepted!
# Interviewer: "Nice! That's optimal."
# Me: *internal celebration* 🎉
🤦 My Stupid Heap Mistakes
Mistake #1: Using MAX heap instead of MIN
# WRONG (my first attempt)
heap = [-x for x in nums[:k]] # Negating for max heap
heapq.heapify(heap)
# Processing new elements...
if num > -heap[0]: # This logic is ALL WRONG
# Confused myself trying to negate everything
# Spent 2 hours debugging
# LESSON: For K largest, just use MIN heap!
# Don't overthink it!
Mistake #2: Forgetting heapify()
# WRONG
heap = nums[:k] # Just a list, NOT a heap!
heapq.heappop(heap) # Doesn't maintain heap property!
# RIGHT ✅
heap = nums[:k]
heapq.heapify(heap) # Convert list to heap!
heapq.heappop(heap) # Now works correctly
💪 Problem #2: Top K Frequent Elements (The Combo Move)
Problem: Find K most frequent elements (#347)
This is where it got interesting!
Example:
Input: [1,1,1,2,2,3], k = 2
Output: [1,2] (1 appears 3 times, 2 appears 2 times)
My Thought Process:
"I need to count frequencies... HashMap! Then find top K... Heap! COMBO PATTERN! 🤯"
The Solution:
import heapq
from collections import Counter
def topKFrequent(nums, k):
"""
Combination of HashMap + Heap!
Strategy:
1. Count frequencies (HashMap)
2. Use Min Heap to find K most frequent
Time: O(n log k)
"""
# Step 1: Count frequencies
freq = Counter(nums)
# freq = {1: 3, 2: 2, 3: 1}
# Step 2: Use Min Heap of size k
# Store (frequency, number) tuples
heap = []
for num, count in freq.items():
heapq.heappush(heap, (count, num))
# Keep heap size = k
if len(heap) > k:
heapq.heappop(heap)
# Extract just the numbers
return [num for count, num in heap]
# Test
print(topKFrequent([1,1,1,2,2,3], 2)) # [1,2] ✅
# Accepted!
When this worked, I felt like a genius combining two patterns!
🎓 Problem #3: Merge K Sorted Lists (The Boss Fight)
Problem: Merge K sorted linked lists (#23)
This is the problem that started my heap journey!
Example:
Input: [[1,4,7], [2,5], [3,6,8]]
Output: [1,2,3,4,5,6,7,8]
My Initial Panic:
"How do I merge K lists??"
Thought about merging 2 at a time... but that’s slow!
Then I learned: Use a Min Heap with K elements (one from each list)!
The Solution (Took Me 2 Days to Understand):
import heapq
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeKLists(lists):
"""
K-way Merge using Min Heap!
Strategy:
1. Put first element of each list in heap
2. Pop smallest
3. Add that element's NEXT to heap
4. Repeat!
Time: O(N log K) where N = total elements
"""
# Min heap: (value, list_index, node)
heap = []
# Add first element of each list
for i, head in enumerate(lists):
if head:
heapq.heappush(heap, (head.val, i, head))
# Dummy node for result
dummy = ListNode(0)
current = dummy
while heap:
# Pop smallest
val, i, node = heapq.heappop(heap)
# Add to result
current.next = node
current = current.next
# If this list has more elements, add next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
# This problem is GENIUS
# I didn't fully understand it for DAYS
# But once it clicked... 🤯
😱 The Tuple Comparison Bug
I got this error and spent an HOUR debugging:
# ERROR: '<' not supported between ListNode instances
# What happened:
# When heap compares (val, i, node) tuples
# If two values are equal, it compares i (works)
# If i is also equal, it tries to compare nodes (CRASH!)
# FIX: Add index to break ties
heapq.heappush(heap, (head.val, i, head))
# ↑
# This index prevents node comparison!
Lesson learned: When using custom objects in heaps, include a tiebreaker!
🎯 Heap Pattern Summary
When to use Heaps:
- ✅ "K largest/smallest elements"
- ✅ "K most frequent"
- ✅ "Merge K sorted"
- ✅ "Kth" anything
Min Heap vs Max Heap:
- K LARGEST → Use MIN heap (keep smallest of large)
- K SMALLEST → Use MAX heap (keep largest of small)
Python Heap Commands:
import heapq
heap = []
heapq.heappush(heap, item) # Add
heapq.heappop(heap) # Remove smallest
heapq.heapify(list) # Convert list to heap
# For Max Heap, negate values:
heapq.heappush(heap, -item)
My mental checklist:
- Do I need top/bottom K elements?
- Can I process elements one by one?
- Do I need to keep track of "best so far"?
If yes → Heap!
🎯 Pattern 8: Overlapping Intervals (The Calendar Revelation)
📅 The Moment It Clicked
I was scheduling my classes for next semester. Had a list of time slots:
CS101: 9:00-10:30
MATH: 10:00-11:30
PHYSICS: 11:00-12:30
I thought: "Wait, CS and MATH overlap! Can’t take both."
Then it hit me: This is EXACTLY what interval problems are about! 🤯
💡 The Secret (So Simple It’s Genius)
Every interval problem has ONE trick:
SORT BY START TIME! 🎯
That’s it. That’s the secret.
Why this works:
Unsorted intervals:
[5,7], [1,3], [2,4], [6,8]
How do you even begin??
Sorted by start:
[1,3], [2,4], [5,7], [6,8]
NOW it's obvious:
[1,3] and [2,4] overlap!
[5,7] and [6,8] overlap!
After sorting, patterns jump out!
💻 Problem #1: Merge Intervals (The Classic)
Problem: Merge overlapping intervals (#56)
Example:
Input: [[1,3], [2,6], [8,10], [15,18]]
Output: [[1,6], [8,10], [15,18]]
(merged [1,3] and [2,6])
My First Attempt (Before Knowing The Secret):
def merge(intervals):
"""
What I tried initially:
"Check every pair for overlap"
O(n²) - way too slow!
"""
result = []
merged = [False] * len(intervals)
for i in range(len(intervals)):
if merged[i]:
continue
current = intervals[i]
for j in range(i+1, len(intervals)):
# Check overlap...
# This got MESSY fast
# Gave up after 2 hours
I couldn’t even finish the code. Too complicated.
After Learning "SORT FIRST":
def merge(intervals):
"""
The GENIUS move: Sort by start time!
Then just compare adjacent intervals!
Strategy:
1. Sort by start time
2. For each interval:
- If overlaps with previous, merge
- Else, it's separate
Time: O(n log n) for sorting
"""
if not intervals:
return []
# Step 1: SORT by start time!
intervals.sort(key=lambda x: x[0])
# Start with first interval
merged = [intervals[0]]
for current in intervals[1:]:
# Get last merged interval
prev = merged[-1]
# Check for overlap
if current[0] <= prev[1]:
# Overlap! Merge them
prev[1] = max(prev[1], current[1])
else:
# No overlap, add as separate
merged.append(current)
return merged
# Test
print(merge([[1,3],[2,6],[8,10],[15,18]]))
# Output: [[1,6],[8,10],[15,18]] ✅
# Accepted!
# Me: "THAT'S IT?? Just sort??"
# Senior: "Yep. Told you."
When I solved this in 10 minutes after struggling for DAYS... 🤯
🤔 How Overlapping Works
This confused me at first:
When do [a,b] and [c,d] overlap?
My confusion: "There are so many cases!"
[1,3] and [2,4] → overlap
[1,4] and [2,3] → overlap
[1,2] and [3,4] → NO overlap
How to check all??
The GENIUS insight:
After sorting by start time, just check:
current.start <= prev.end
That's IT!
Why? Because we KNOW current.start >= prev.start (sorted!)
So we only need to check if current.start <= prev.end!
One. Simple. Check. 🎯
💪 Problem #2: Meeting Rooms II (The Mind-Bender)
Problem: Minimum meeting rooms needed (#253)
Example:
Input: [[0,30], [5,10], [15,20]]
Output: 2 (at time 5-10, two meetings active)
This one BROKE me. I spent 3 days on this.
My Failed Attempts:
# Attempt 1: Track overlaps
# Got too complicated, gave up
# Attempt 2: Brute force checking
# O(n²), way too slow
# Attempt 3: Some weird sorting thing
# Couldn't even explain my own logic
Then I learned the trick: Use TWO arrays! 🤯
The Solution (That Finally Clicked):
def minMeetingRooms(intervals):
"""
The GENIUS trick: Separate starts and ends!
Think of it like people entering/leaving a building:
- Each start = person enters
- Each end = person leaves
- Track peak occupancy!
Strategy:
1. Sort starts and ends SEPARATELY
2. Use two pointers
3. Track max rooms needed
"""
if not intervals:
return 0
# Separate starts and ends
starts = sorted([i[0] for i in intervals])
ends = sorted([i[1] for i in intervals])
rooms = 0
max_rooms = 0
s = 0 # Start pointer
e = 0 # End pointer
while s < len(starts):
if starts[s] < ends[e]:
# Meeting starting before previous ended
# Need a new room!
rooms += 1
max_rooms = max(max_rooms, rooms)
s += 1
else:
# Meeting ended, room freed!
rooms -= 1
e += 1
return max_rooms
# Test
print(minMeetingRooms([[0,30],[5,10],[15,20]])) # 2 ✅
# When this worked, I literally YELLED
# Roommate: "You okay?"
# Me: "I UNDERSTAND INTERVALS!" 🎉
🎨 Visual Explanation (What Made It Click)
Meetings: [[0,30], [5,10], [15,20]]
Timeline visualization:
Time: 0 5 10 15 20 30
|---| |---| |---|
| | |
|--------| |
|-----------------|
Sort starts: [0, 5, 15]
Sort ends: [10, 20, 30]
Process:
s=0, e=0: starts[0]=0 < ends[0]=10
Meeting starts! rooms=1
s=1, e=0: starts[1]=5 < ends[0]=10
Another starts! rooms=2 ← Peak!
s=2, e=0: starts[2]=15 > ends[0]=10
One ended first! rooms=1
Answer: max_rooms = 2 ✅
Drawing this timeline changed EVERYTHING for me!
🎓 Problem #3: Insert Interval (The Tricky One)
Problem: Insert new interval and merge if needed (#57)
Example:
Input: [[1,3],[6,9]], new = [2,5]
Output: [[1,5],[6,9]]
The Solution:
def insert(intervals, newInterval):
"""
Three phases:
1. Add all intervals BEFORE new interval
2. Merge overlapping intervals
3. Add all intervals AFTER
"""
result = []
i = 0
n = len(intervals)
# Phase 1: Before new interval
while i < n and intervals[i][1] < newInterval[0]:
result.append(intervals[i])
i += 1
# Phase 2: Merge overlapping
while i < n and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
result.append(newInterval)
# Phase 3: After new interval
while i < n:
result.append(intervals[i])
i += 1
return result
# This took me FOREVER to understand
# The three-phase approach is GENIUS
🎯 Interval Pattern Summary
The Golden Rule: ALWAYS SORT BY START TIME FIRST!
Common Interval Problems:
- Merge intervals → Sort, then merge adjacent
- Meeting rooms → Separate starts/ends
- Insert interval → Three-phase approach
My mental model:
See "intervals" or "ranges" in problem
↓
Sort by start time
↓
Compare adjacent/use two pointers
↓
Profit! ✨
🎯 Pattern 9: Modified Binary Search (Not Just Sorted Arrays!)
💭 My Mind-Blowing Realization
I thought binary search was ONLY for sorted arrays.
# Classic binary search
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Then my senior told me something that BLEW MY MIND:
"Binary search works on ANY monotonic search space!"
Me: "What does that even mean??"
Him: "If you can split the problem into YES/NO and eliminate half, use binary search."
Me: 🤯
🌟 The Paradigm Shift
Binary search isn’t about sorted arrays.
It’s about ELIMINATING HALF of the search space!
Examples:
Finding square root?
→ Binary search on answer range [0, x]
Minimum capacity to ship packages?
→ Binary search on capacity range [max, sum]
First bad version?
→ Binary search on version numbers
NONE of these are sorted arrays!
But all use binary search!
When this clicked, I felt like I discovered a cheat code. 🎮
💻 Problem #1: Search in Rotated Sorted Array (The Twist)
Problem: Array was sorted, then rotated. Find target (#33)
Example:
Input: [4,5,6,7,0,1,2], target = 0
Output: 4
My First Reaction:
"The array is rotated! Binary search won’t work!"
WRONG. It DOES work! With a twist! 🤯
The Insight:
Rotated array: [4,5,6,7,0,1,2]
At ANY midpoint, ONE half is sorted!
Mid at index 3 (value 7):
Left half [4,5,6,7] → SORTED ✅
Right half [0,1,2] → NOT sorted
We can use the SORTED half to decide which way to go!
When I realized this, I literally said "OHHH" out loud.
The Solution:
def search(nums, target):
"""
Modified binary search for rotated array!
Key insight:
At any mid, ONE half is sorted
Use sorted half to decide direction
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# Check which half is sorted
if nums[left] <= nums[mid]:
# Left half is sorted
if nums[left] <= target < nums[mid]:
# Target in sorted left half
right = mid - 1
else:
# Target in unsorted right half
left = mid + 1
else:
# Right half is sorted
if nums[mid] < target <= nums[right]:
# Target in sorted right half
left = mid + 1
else:
# Target in unsorted left half
right = mid - 1
return -1
# Test
print(search([4,5,6,7,0,1,2], 0)) # 4 ✅
# Accepted!
This problem made me realize: Binary search is MORE powerful than I thought!
💪 Problem #2: Find Minimum in Rotated Array (The Variation)
Problem: Find minimum element (#153)
Example:
Input: [3,4,5,1,2]
Output: 1
The Trick:
def findMin(nums):
"""
The minimum is where the rotation happened!
Strategy:
- If nums[mid] > nums[right], min is in right half
- Else, min is in left half (or mid itself)
"""
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
# Minimum in right half
left = mid + 1
else:
# Minimum in left half (or mid)
right = mid
return nums[left]
# So simple once you see it!
🎯 Problem #3: Binary Search on Answer (The Game-Changer)
Problem: Minimum capacity to ship packages (#1011)
This is where binary search got REALLY interesting!
Example:
Weights: [1,2,3,4,5,6,7,8,9,10]
Days: 5
What's minimum capacity needed?
Answer: 15
(Day 1: 15, Day 2: 14, Day 3: 13, etc.)
My Mind Blown Moment:
"We’re not searching IN an array... we’re searching FOR an answer!"
The Insight:
We don't know the answer.
But we know it's between:
- Minimum: max(weights) = 10
- Maximum: sum(weights) = 55
Can we ship with capacity 20? → Check
Can we ship with capacity 15? → Check
Can we ship with capacity 10? → Check
This is MONOTONIC!
If we can ship with capacity X,
we can definitely ship with capacity X+1!
BINARY SEARCH ON THE ANSWER! 🤯
The Solution:
def shipWithinDays(weights, days):
"""
Binary search on ANSWER (capacity)!
Range: [max(weights), sum(weights)]
For each mid capacity, check:
Can we ship within days? (helper function)
"""
def canShip(capacity):
"""Check if we can ship with this capacity"""
day_count = 1
current_load = 0
for weight in weights:
if current_load + weight > capacity:
# Need new day
day_count += 1
current_load = weight
else:
current_load += weight
return day_count <= days
# Binary search on capacity
left = max(weights) # Minimum possible
right = sum(weights) # Maximum possible
while left < right:
mid = (left + right) // 2
if canShip(mid):
# Can ship with mid, try smaller
right = mid
else:
# Can't ship, need bigger capacity
left = mid + 1
return left
# Test
print(shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5)) # 15 ✅
# When I solved this, I felt like a GENIUS
# "I can binary search on ANYTHING monotonic!"
😱 The Off-By-One Nightmare
Binary search has SO MANY off-by-one bugs:
# These ALL behave differently:
# Version 1:
while left <= right: # Include equal
mid = (left + right) // 2
...
left = mid + 1
right = mid - 1
# Version 2:
while left < right: # Exclude equal
mid = (left + right) // 2
...
left = mid + 1
right = mid # No -1!
# Version 3:
while left < right:
mid = (left + right + 1) // 2 # Round up!
...
# I got confused SO MANY TIMES
# Which version to use when??
My Solution: I have a template for each type:
- Finding exact value → Version 1
- Finding minimum → Version 2
- Finding maximum → Version 3
Memorized these. Life became easier. 😅
🎯 Binary Search Pattern Summary
Binary search works when:
- ✅ Search space is monotonic (sorted)
- ✅ Can split into YES/NO
- ✅ Can eliminate half each time
Types of binary search:
- Classic: Search in sorted array
- Rotated: One half always sorted
- On Answer: Search for minimum/maximum value
My mental model:
See "minimum"/"maximum" + constraints
↓
Is there a range to search?
↓
Is it monotonic? (Can I eliminate half?)
↓
Binary search on answer!
🎯 Pattern 10: Tree Traversals (BFS vs DFS Clarity)
🌳 The "It’s Just a Tree" Moment
I used to think trees were scary. Complex. Difficult.
Then I realized: A tree is just a linked list... with branches! 🤯
That’s IT!
Linked list:
1 → 2 → 3 → 4
Tree:
1
/ \
2 3
/
4
Same concept. Just split!
This realization made trees SO MUCH EASIER.
🔍 BFS vs DFS (The Strategy Decision)
The Question: "When do I use BFS? When DFS?"
My confusion lasted WEEKS.
Then someone explained it like this:
BFS (Breadth-First) = Level by level
- Use a QUEUE
- Good for: Shortest path, level order, "nearest"
DFS (Depth-First) = Go deep first
- Use RECURSION (or stack)
- Good for: Search all paths, tree height, validate
Visual:
Tree:
1
/ \
2 3
/ \
4 5
BFS order: 1, 2, 3, 4, 5 (level by level)
DFS order: 1, 2, 4, 5, 3 (deep first)
💻 Problem #1: Level Order Traversal (BFS Classic)
Problem: Return level-by-level values (#102)
Example:
Input:
3
/ \
9 20
/ \
15 7
Output: [[3], [9,20], [15,7]]
The BFS Template:
from collections import deque
def levelOrder(root):
"""
BFS using Queue!
Process level by level
"""
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
level_size = len(queue) # Current level size
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
# Add children for next level
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
# Output: [[3], [9,20], [15,7]] ✅
Key insight: Process ENTIRE level before moving to next!
💪 Problem #2: Maximum Depth (DFS Classic)
Problem: Find tree height (#104)
The DFS Approach:
def maxDepth(root):
"""
DFS with recursion!
Height = 1 + max(left height, right height)
"""
if not root:
return 0
left_depth = maxDepth(root.left)
right_depth = maxDepth(root.right)
return 1 + max(left_depth, right_depth)
# So elegant!
# Recursion makes tree problems BEAUTIFUL
🎓 Problem #3: Validate BST (The Tricky One)
Problem: Check if tree is valid Binary Search Tree (#98)
My First WRONG Attempt:
def isValidBST(root):
"""
WRONG approach:
"Just check if left < root < right"
"""
if not root:
return True
if root.left and root.left.val >= root.val:
return False
if root.right and root.right.val <= root.val:
return False
return isValidBST(root.left) and isValidBST(root.right)
# This fails on:
# 5
# / \
# 1 6
# / \
# 3 7
#
# 3 < 6 but 3 < 5! INVALID!
# But my code says VALID! 😱
The problem: Need to track RANGE, not just parent!
The CORRECT Solution:
def isValidBST(root):
"""
Track valid RANGE for each node!
Root can be anything
Left subtree must be < root
Right subtree must be > root
"""
def validate(node, min_val, max_val):
if not node:
return True
# Check if node value in valid range
if node.val <= min_val or node.val >= max_val:
return False
# Check left (must be < node.val)
# Check right (must be > node.val)
return (validate(node.left, min_val, node.val) and
validate(node.right, node.val, max_val))
return validate(root, float('-inf'), float('inf'))
# NOW it works! ✅
This bug cost me 4 HOURS of debugging. 🤦
🎯 Tree Pattern Summary
BFS (Queue):
- Level order traversal
- Shortest path
- Zigzag level order
DFS (Recursion):
- Tree height/depth
- Path sum
- Validate tree
Common tree patterns:
# DFS Template
def dfs(root):
if not root:
return base_case
left = dfs(root.left)
right = dfs(root.right)
return combine(left, right)
# BFS Template
def bfs(root):
queue = deque([root])
while queue:
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
# Process node
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
🎯 [CONTINUES WITH PATTERNS 11-14...]
This is Part 2 getting built! Should I continue with:
- Pattern 11: Matrix Traversal
- Pattern 12: Backtracking
- Pattern 13: Dynamic Programming
- Pattern 14: Bit Manipulation
Each will be 400-600 lines with full narrative style!
Total will be 4,000+ lines when complete!
Continue? 🚀
🎯 Pattern 11: Matrix Traversal (Grids Are Graphs!)
🗺️ The Grid Awakening
The Realization That Changed Everything:
I was stuck on "Number of Islands" for 2 days.
Couldn’t figure out how to "connect" adjacent cells.
Then my senior said: "A grid is just a graph where each cell is connected to its neighbors."
Me: "...WHAT??"
Him: "Seriously. Treat it like a graph. Use DFS or BFS."
I tried it. IT WORKED. 🤯
💡 The Matrix = Graph Insight
Matrix:
1 1 0
1 0 0
0 1 1
Think of it as graph:
(0,0) ←→ (0,1)
↕
(1,0)
Each cell is a NODE
Adjacent cells are CONNECTED
DFS/BFS works PERFECTLY!
When this clicked, matrix problems became SO MUCH EASIER.
💻 Problem #1: Number of Islands (The Foundation)
Problem: Count islands in grid (#200)
Example:
Input:
1 1 0 0
1 0 0 1
0 0 1 1
Output: 3 (three separate islands)
My Solution (After the Realization):
def numIslands(grid):
"""
Treat grid as graph!
Use DFS to mark visited cells
Each DFS call explores one island
"""
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
# Base cases
if (r < 0 or r >= rows or
c < 0 or c >= cols or
grid[r][c] == '0'):
return
# Mark as visited
grid[r][c] = '0'
# Explore all 4 directions
dfs(r+1, c) # Down
dfs(r-1, c) # Up
dfs(r, c+1) # Right
dfs(r, c-1) # Left
# Check each cell
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c) # Explore entire island
return count
# Test
grid = [
["1","1","0","0"],
["1","0","0","1"],
["0","0","1","1"]
]
print(numIslands(grid)) # 3 ✅
# Accepted!
# Me: "IT'S JUST DFS!" 🎉
😱 The Boundary Check Hell
I kept getting IndexError and couldn’t figure out why:
# WRONG (my first attempt)
def dfs(r, c):
if grid[r][c] == '0': # CRASHES if out of bounds!
return
# Then check bounds? Too late!
# RIGHT ✅
def dfs(r, c):
# Check bounds FIRST!
if r < 0 or r >= rows or c < 0 or c >= cols:
return
# THEN check value
if grid[r][c] == '0':
return
Lesson learned: ALWAYS check boundaries before accessing array!
💪 Problem #2: Flood Fill (The Paint Bucket)
Problem: Change connected cells to new color (#733)
Example:
Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
The Solution:
def floodFill(image, sr, sc, color):
"""
Classic DFS flood fill!
Like paint bucket tool in Paint!
"""
original_color = image[sr][sc]
# Edge case: already that color
if original_color == color:
return image
rows, cols = len(image), len(image[0])
def dfs(r, c):
# Check bounds and color
if (r < 0 or r >= rows or
c < 0 or c >= cols or
image[r][c] != original_color):
return
# Change color
image[r][c] = color
# Spread to neighbors
dfs(r+1, c)
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)
dfs(sr, sc)
return image
# So simple once you see the pattern!
🎓 Problem #3: Spiral Matrix (The Boundary Dance)
Problem: Return elements in spiral order (#54)
This one is DIFFERENT. No DFS/BFS!
Example:
Input:
1 2 3
4 5 6
7 8 9
Output: [1,2,3,6,9,8,7,4,5]
My Approach (After MANY Failed Attempts):
def spiralOrder(matrix):
"""
Move in spiral: Right → Down → Left → Up
Shrink boundaries after each side
"""
result = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
# Move right along top row
for c in range(left, right + 1):
result.append(matrix[top][c])
top += 1
# Move down along right column
for r in range(top, bottom + 1):
result.append(matrix[r][right])
right -= 1
# Move left along bottom row (if exists)
if top <= bottom:
for c in range(right, left - 1, -1):
result.append(matrix[bottom][c])
bottom -= 1
# Move up along left column (if exists)
if left <= right:
for r in range(bottom, top - 1, -1):
result.append(matrix[r][left])
left += 1
return result
# This took me FOREVER to get right
# The boundary updates are TRICKY
I spent 5 HOURS debugging this. The boundary logic is HARD!
🎯 Matrix Pattern Summary
Matrix as Graph:
- Each cell = node
- Adjacent cells = edges
- Use DFS/BFS to traverse
Common patterns:
# DFS on grid
def dfs(r, c):
# Bounds check FIRST!
if r < 0 or r >= rows or c < 0 or c >= cols:
return
# Then other checks
if grid[r][c] == visited:
return
# Mark visited
grid[r][c] = visited
# Explore 4 directions
dfs(r+1, c)
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)
# BFS on grid
from collections import deque
queue = deque([(start_r, start_c)])
visited = set()
while queue:
r, c = queue.popleft()
for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and 0 <= nc < cols and
(nr, nc) not in visited):
visited.add((nr, nc))
queue.append((nr, nc))
🎯 Pattern 12: Backtracking (The Decision Tree)
🌳 The "Try Everything" Revelation
I was stuck on "Generate Parentheses" for A WEEK.
Couldn’t figure out how to generate all valid combinations.
Then I learned about backtracking:
"Try a choice. If it works, continue. If it fails, UNDO and try different choice."
Like exploring a maze: Try path → Dead end → Go back → Try different path
This is backtracking! 🤯
💡 The Backtracking Template
def backtrack(current_state, choices):
# Base case: found solution
if is_solution(current_state):
result.append(current_state.copy())
return
# Try each choice
for choice in choices:
# Make choice
current_state.add(choice)
# Explore further
backtrack(current_state, remaining_choices)
# UNDO choice (backtrack!)
current_state.remove(choice)
The key: Make choice → Explore → UNDO → Try next choice
💻 Problem #1: Permutations (The Introduction)
Problem: Generate all permutations (#46)
Example:
Input: [1,2,3]
Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
My Solution (After Understanding Backtracking):
def permute(nums):
"""
Backtracking to try all orderings!
Decision tree:
Start: []
Try 1: [1] → Try 2: [1,2] → Try 3: [1,2,3] ✓
↑ Backtrack
Try 3: [1,3] → Try 2: [1,3,2] ✓
↑ Backtrack
Try 2: [2] → ...
Try 3: [3] → ...
"""
result = []
def backtrack(current):
# Base case: used all numbers
if len(current) == len(nums):
result.append(current[:]) # Copy!
return
# Try each number
for num in nums:
if num in current:
continue # Already used
# Make choice
current.append(num)
# Explore
backtrack(current)
# UNDO (backtrack!)
current.pop()
backtrack([])
return result
# Test
print(permute([1,2,3]))
# [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]] ✅
# When this worked, I FINALLY understood backtracking!
🤦 The Copy vs Reference Bug
This bug cost me 3 HOURS:
# WRONG
if len(current) == len(nums):
result.append(current) # Reference!
# Later changes affect this!
# Result: [[3,2,1], [3,2,1], [3,2,1], ...]
# All same because we modified it! 😱
# RIGHT ✅
if len(current) == len(nums):
result.append(current[:]) # COPY!
# Or: result.append(list(current))
Lesson learned: ALWAYS copy when storing in backtracking!
💪 Problem #2: Subsets (The Power Set)
Problem: Generate all subsets (#78)
Example:
Input: [1,2,3]
Output: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]
The Solution:
def subsets(nums):
"""
Each number: Include it or DON'T include it
Decision tree:
[]
├─ Don't take 1: []
│ ├─ Don't take 2: []
│ └─ Take 2: [2]
└─ Take 1: [1]
├─ Don't take 2: [1]
└─ Take 2: [1,2]
...
"""
result = []
def backtrack(start, current):
# Every state is a valid subset!
result.append(current[:])
# Try adding each remaining number
for i in range(start, len(nums)):
# Include nums[i]
current.append(nums[i])
# Explore with this number
backtrack(i + 1, current)
# Backtrack
current.pop()
backtrack(0, [])
return result
# So elegant!
🎓 Problem #3: N-Queens (The Classic)
Problem: Place N queens on N×N board (#51)
This is THE classic backtracking problem!
Example:
Input: n = 4
Output: [
[".Q..",
"...Q",
"Q...",
"..Q."],
["..Q.",
"Q...",
"...Q",
".Q.."]
]
The Solution (Took Me 2 DAYS):
def solveNQueens(n):
"""
Place queens row by row
Check if position is safe
Backtrack if stuck
"""
result = []
board = [['.'] * n for _ in range(n)]
def isSafe(row, col):
# Check column
for r in range(row):
if board[r][col] == 'Q':
return False
# Check diagonal (top-left)
r, c = row - 1, col - 1
while r >= 0 and c >= 0:
if board[r][c] == 'Q':
return False
r -= 1
c -= 1
# Check diagonal (top-right)
r, c = row - 1, col + 1
while r >= 0 and c < n:
if board[r][c] == 'Q':
return False
r -= 1
c += 1
return True
def backtrack(row):
# Placed all queens!
if row == n:
result.append([''.join(r) for r in board])
return
# Try placing queen in each column
for col in range(n):
if isSafe(row, col):
# Place queen
board[row][col] = 'Q'
# Try next row
backtrack(row + 1)
# Remove queen (backtrack)
board[row][col] = '.'
backtrack(0)
return result
# This problem is GENIUS
# I felt like a chess master when I solved it! ♟️
🎯 Backtracking Pattern Summary
The pattern:
- Make a choice
- Explore that choice
- If it fails, UNDO
- Try next choice
When to use:
- "Generate all ___"
- "Find all combinations/permutations"
- Constraint satisfaction (N-Queens, Sudoku)
Template:
def backtrack(state):
if is_solution(state):
result.append(state.copy())
return
for choice in choices:
if is_valid(choice):
make_choice(choice)
backtrack(state)
undo_choice(choice) # KEY!
🎯 Pattern 13: Dynamic Programming (The Pattern That Almost Broke Me)
😭 The DP Nightmare
I’m just gonna be honest:
Dynamic Programming kicked my ass. HARD.
I spent 3 WEEKS trying to understand it. Failed miserably.
Watched 50+ videos. Read 20+ articles. Still confused.
I genuinely thought: "Maybe I’m just not smart enough for DP."
💔 The Breaking Point (Again, Again)
Week 1: Tried "Climbing Stairs"
- Looked at solution
- Saw
dp[i] = dp[i-1] + dp[i-2] - "Where did that come from??"
Week 2: Tried "House Robber"
- Solution had 2D table
- "What do these dimensions even MEAN??"
Week 3: Tried "Longest Common Subsequence"
- Solution looked like black magic
- Gave up. Actually gave up.
My senior found me staring blankly at my laptop:
Him: "Still stuck on DP?" Me: "I don’t get it. I’ll never get it." Him: "Wanna know the secret?"
🌟 The Secret That Changed EVERYTHING
He told me:
"DP is just recursion + memory."
That’s IT.
Step 1: Solve it recursively Step 2: Notice you’re solving same subproblems Step 3: Store the answers (memoization) Step 4: Convert to bottom-up (optional)
Me: "...that’s all?"
Him: "That’s all."
I tried it. HOLY CRAP IT WORKED. 🤯
💻 Problem #1: Fibonacci (The Aha Moment)
Let me show you EXACTLY how I learned DP:
Step 1: Naive Recursion
def fib(n):
"""
Naive recursive solution
SLOW! Recalculates same values!
"""
if n <= 1:
return n
return fib(n-1) + fib(n-2)
# fib(5) calculation:
# fib(5)
# fib(4)
# fib(3)
# fib(2) ← Calculated
# fib(1)
# fib(0)
# fib(1)
# fib(2) ← Calculated AGAIN! Wasteful!
# fib(3) ← Calculated AGAIN!
# Time: O(2^n) - TERRIBLE!
Step 2: Add Memoization
def fib(n, memo={}):
"""
Recursion + Memory = FAST!
"""
if n <= 1:
return n
# Check if already calculated
if n in memo:
return memo[n] # Return stored answer!
# Calculate and store
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]
# Now fib(2) is calculated ONCE, then reused!
# Time: O(n) ✨
Step 3: Bottom-Up DP
def fib(n):
"""
Build from bottom up
No recursion needed!
"""
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# Time: O(n)
# Space: O(n)
When I saw these three versions side-by-side, DP FINALLY clicked! 🎉
💡 The DP Process (My Actual Workflow)
Now when I see a DP problem:
1. Can I solve it recursively?
↓
2. What are the subproblems?
↓
3. Am I solving same subproblems multiple times?
↓
4. Add memoization!
↓
5. (Optional) Convert to bottom-up
This process WORKS!
💪 Problem #2: Climbing Stairs (The Classic)
Problem: How many ways to climb n stairs? (#70)
You can climb 1 or 2 steps at a time
My Process:
Step 1: Think Recursively
To reach step n:
- Came from step n-1 (1 step)
- OR came from step n-2 (2 steps)
So: ways(n) = ways(n-1) + ways(n-2)
Base cases:
ways(1) = 1
ways(2) = 2
Step 2: Code It
def climbStairs(n):
"""
Recursion + memo
"""
memo = {}
def climb(n):
if n <= 2:
return n
if n in memo:
return memo[n]
memo[n] = climb(n-1) + climb(n-2)
return memo[n]
return climb(n)
# Accepted! ✅
This was the first DP problem I solved on my own! 🎉
🎓 Problem #3: House Robber (The 2D Awakening)
Problem: Rob houses, can’t rob adjacent (#198)
Example:
Houses: [2,7,9,3,1]
Max: 12 (rob 2,9,1)
My Process:
For each house, two choices:
1. Rob it (can't rob previous)
2. Don't rob it (can rob previous)
dp[i] = max(
rob[i] + dp[i-2], # Rob this house
dp[i-1] # Don't rob this house
)
The Solution:
def rob(nums):
"""
DP: Choose to rob or not rob each house
"""
if not nums:
return 0
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(
nums[i] + dp[i-2], # Rob this house
dp[i-1] # Skip this house
)
return dp[-1]
# Test
print(rob([2,7,9,3,1])) # 12 ✅
# When this worked, I cried happy tears! 😭🎉
🌟 Problem #4: Longest Common Subsequence (The Boss)
Problem: Find longest subsequence common to both strings (#1143)
This is the CLASSIC 2D DP problem!
Example:
s1 = "abcde"
s2 = "ace"
Output: 3 ("ace")
The 2D Table:
"" a c e
"" 0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0 1 2 2
e 0 1 2 3
Answer: dp[5][3] = 3
The Solution (Took Me FOREVER to Understand):
def longestCommonSubsequence(text1, text2):
"""
2D DP table!
dp[i][j] = LCS of text1[0:i] and text2[0:j]
If text1[i] == text2[j]:
dp[i][j] = 1 + dp[i-1][j-1]
Else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
"""
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
# Characters match!
dp[i][j] = 1 + dp[i-1][j-1]
else:
# Take best of skipping either character
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
# Test
print(longestCommonSubsequence("abcde", "ace")) # 3 ✅
# Solving this felt like climbing Mount Everest! 🏔️
😱 My DP Mistakes (All Of Them)
Mistake #1: Trying to understand WITHOUT recursion first
I tried to understand the DP table directly
Couldn't figure out where formulas came from
Gave up multiple times
SOLUTION: Always start with recursion!
Mistake #2: Not drawing the table
Tried to visualize in my head
Got confused by dimensions
Made off-by-one errors everywhere
SOLUTION: ALWAYS draw the table on paper!
Mistake #3: Giving up too fast
"I'll never understand DP"
Stopped trying for weeks
Fell behind
SOLUTION: DP is HARD. It's NORMAL to struggle!
Keep trying. It WILL click eventually!
🎯 DP Pattern Summary
The Process:
- Find recursive solution
- Identify overlapping subproblems
- Add memoization (top-down)
- Convert to DP table (bottom-up)
Common DP patterns:
1. Fibonacci-style:
dp[i] = dp[i-1] + dp[i-2]
# Climbing Stairs, House Robber
2. 0/1 Knapsack:
dp[i][w] = max(
dp[i-1][w], # Don't take item
value[i] + dp[i-1][w-weight[i]] # Take item
)
3. String DP:
dp[i][j] = {
1 + dp[i-1][j-1] if s1[i] == s2[j]
max(dp[i-1][j], dp[i][j-1]) otherwise
}
# LCS, Edit Distance
My advice:
- Start with EASY DP problems (Fibonacci, Climbing Stairs)
- Draw EVERYTHING on paper
- Don’t give up! DP takes TIME to click!
- It’s okay to not understand it immediately!
🎯 Pattern 14: Bit Manipulation (The Secret Weapon)
🔢 The Binary Awakening
I thought bit manipulation was:
- Super advanced
- Only for competitive programmers
- Not worth learning for interviews
I was SO WRONG. 🤦
Bit manipulation is:
- Actually pretty simple (once you see it)
- Shows up in LOTS of interviews
- Makes you look like a wizard ✨
💡 The XOR Magic
The problem that introduced me to bit magic:
"Find the number that appears once while others appear twice"
Naive approach:
# Use HashSet
def singleNumber(nums):
seen = set()
for num in nums:
if num in seen:
seen.remove(num)
else:
seen.add(num)
return seen.pop()
# Works but uses O(n) space
Then I learned about XOR:
def singleNumber(nums):
"""
XOR magic!
Key properties:
- a ^ a = 0
- a ^ 0 = a
- XOR is commutative
So: [2,3,2,5,3]
= 2 ^ 3 ^ 2 ^ 5 ^ 3
= (2 ^ 2) ^ (3 ^ 3) ^ 5
= 0 ^ 0 ^ 5
= 5 ✨
"""
result = 0
for num in nums:
result ^= num
return result
# O(1) space! 🤯
When this worked, I felt like I discovered cheat codes! 🎮
💻 Problem #1: Number of 1 Bits (Hamming Weight)
Problem: Count number of 1s in binary (#191)
Example:
Input: 11 (binary: 1011)
Output: 3 (three 1s)
My Journey:
Attempt 1: Convert to string
def hammingWeight(n):
return bin(n).count('1')
# Works but feels like cheating 😅
Attempt 2: The Bit Trick
def hammingWeight(n):
"""
Brian Kernighan's Algorithm!
n & (n-1) removes rightmost 1 bit!
Example:
n = 1011
n-1 = 1010
n & (n-1) = 1010 (removed rightmost 1!)
Keep doing this until n = 0
"""
count = 0
while n:
n &= (n - 1) # Remove rightmost 1
count += 1
return count
# So elegant! ✨
💪 Problem #2: Power of Two
Problem: Check if number is power of 2 (#231)
The Bit Trick:
def isPowerOfTwo(n):
"""
Power of 2 has exactly ONE bit set!
4 = 0100
8 = 1000
16 = 10000
Trick: n & (n-1) removes the only 1 bit
Result should be 0!
"""
if n <= 0:
return False
return (n & (n - 1)) == 0
# One line! 🤯
# Test
print(isPowerOfTwo(16)) # True ✅
print(isPowerOfTwo(18)) # False ✅
🎓 Problem #3: Bit Masking (The Advanced Stuff)
Problem: Generate all subsets using bits (#78 variation)
The Insight:
For [1,2,3]:
Use 3 bits to represent include/exclude:
000 = []
001 = [3]
010 = [2]
011 = [2,3]
100 = [1]
101 = [1,3]
110 = [1,2]
111 = [1,2,3]
8 possibilities = 2^3 subsets!
The Code:
def subsets(nums):
"""
Use bitmask to generate all subsets!
For each number from 0 to 2^n - 1:
- Check each bit
- If bit is set, include that element
"""
n = len(nums)
result = []
for mask in range(2 ** n):
subset = []
for i in range(n):
# Check if ith bit is set
if mask & (1 << i):
subset.append(nums[i])
result.append(subset)
return result
# Test
print(subsets([1,2,3]))
# [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]] ✅
# Mind = Blown 🤯
🎯 Bit Manipulation Summary
Essential Bit Tricks:
# Check if ith bit is set
if n & (1 << i):
# Bit is set
# Set ith bit
n |= (1 << i)
# Clear ith bit
n &= ~(1 << i)
# Toggle ith bit
n ^= (1 << i)
# Remove rightmost 1 bit
n &= (n - 1)
# Check if power of 2
n > 0 and (n & (n-1)) == 0
When to use:
- "Single number" problems → XOR
- "Power of 2" → Bit counting
- "All subsets" → Bitmask
- "Count bits" → Brian Kernighan