Welcome to Day 10 of your coding interview journey.

So far, you’ve built strong fundamentals:

• ✅ Arrays, HashMaps, Sliding Window
• ✅ Two Pointers, Intervals, Binary Search
• ✅ Trees & Binary Search Trees

Today, we step into a game-changing topic:

👉 Graphs

---

🧠 What is a Graph?

A Graph is a collection of:

• Nodes (vertices)
• Edges (connections between nodes)

Graphs can represent:

• Social networks
• Maps & navigation
• Networks & systems

---

🔑 Two Core Traversal Techniques

To solve graph problems, you must master:

1. DFS – Depth-First Search

• Go deep first, then backtrack
• Usually implemented with recursion

2. BFS – Breadth-First Search

• Explore level by level
• Uses a queue

---

🧩 Problem – Number of Islands

---

🧠 Problem

You are given a 2D grid of '1' (land) and '0' (water):

👉 Count how many islands exist.

An island is formed by connecting adjacent lands (horizontally or vertically).

---

✅ Example

grid = [
  ["1","1","0","0"],
  ["1","1","0","0"],
  ["0","0","1","0"],
  ["0","0","0","1"]
]

Output:

3

---

💡 Approach 1 – DFS (Recursive)

---

🧠 Key Idea

👉 Every time you find land ('1'):

• That’s a new island
• Use DFS to mark the entire island as visited

---

🛠️ Solution in Python (DFS)

def num_islands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if (
            r < 0 or c < 0 or
            r >= rows or c >= cols or
            grid[r][c] == "0"
        ):
            return

        grid[r][c] = "0"  # mark as visited

        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                dfs(r, c)

    return count

---

⚡ Complexity (DFS)

• Time: O(m * n)
• Space: O(m * n) (recursion stack)

---

💡 Approach 2 – BFS (Queue)

---

🧠 Key Idea

Same logic, but instead of recursion:

👉 Use a queue to explore neighbors level by level

---

🛠️ Solution in Python (BFS)

from collections import deque

def num_islands_bfs(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                queue = deque([(r, c)])

                while queue:
                    x, y = queue.popleft()

                    if (
                        x < 0 or y < 0 or
                        x >= rows or y >= cols or
                        grid[x][y] == "0"
                    ):
                        continue

                    grid[x][y] = "0"

                    queue.append((x + 1, y))
                    queue.append((x - 1, y))
                    queue.append((x, y + 1))
                    queue.append((x, y - 1))

    return count

---

🎯 DFS vs BFS

Feature	DFS	BFS
Strategy	Go deep	Level by level
Data structure	Recursion / Stack	Queue
Use case	Exploration	Shortest path

---

⚠️ Common Mistakes

• ❌ Not marking nodes as visited
• ❌ Going out of bounds
• ❌ Counting the same island multiple times
• ❌ Modifying input without intention

---

🧪 Practice Problems

To master graphs, try:

1. Clone Graph
2. Pacific Atlantic water flow
3. Course schedule
4. Rotten oranges
5. Word ladder

---

🎯 Key Takeaways

• Graph problems = traversal problems
• Master:
  • DFS (recursion mindset)
  • BFS (queue mindset)
• Think in terms of:
  • Nodes
  • Neighbors
  • Visited states

---

🚀 Your Challenge (Day 10)

Solve this:

Given a grid, find the size of the largest island.

---

📌 Final Thoughts

Graphs are one of the most important topics in coding interviews.

Once you master DFS and BFS, you unlock problems that many candidates struggle with.