DAY 27 Navigating Graphs: From Islands to Regions

Hello Everyone!

Day 2 of Week 6 was dedicated to Graph Problems, and each challenge felt like unraveling a real-world mystery. Graph problems require a systematic approach, whether it’s exploring connected components or managing regions. Today’s tasks tested my traversal skills and my ability to treat grids as graphs, making the experience both challenging and rewarding.

---

How the Day Played Out

1. Number of Islands (Medium Difficulty)

   • Task: Count the number of islands in a grid where 1 represents land and 0 represents water.
   • The Strategy:
     • Treated the grid as a graph and applied Depth First Search (DFS) to explore all connected components of land.
     • Modified the grid directly to mark visited cells, which eliminated the need for additional memory.
   • The Fun Part:
     • Watching islands “disappear” as I marked cells during DFS felt like uncovering hidden treasures one step at a time. It was visually satisfying to see the grid transform.

2. Surrounded Regions (Medium Difficulty)

   • Task: Flip all Os surrounded by Xs to X, leaving only border-connected Os unchanged.
   • The Strategy:
     • Used Breadth First Search (BFS) from the border Os to mark them as non-flippable by temporarily changing their value.
     • In a second pass, flipped the remaining Os to X while restoring the border-connected ones.
   • The Fun Part:
     • The two-phase process of marking and flipping felt satisfying. It was like organizing a chaotic grid into a controlled structure.

---

What Made Today Special

1. Viewing Grids as Graphs:

   • Both problems treated grids as graphs, which provided a fresh perspective compared to the usual adjacency lists or matrices. This approach required visualizing connections between cells.

2. Efficient State Management:

   • Modifying the grid directly to mark visited cells improved efficiency and reduced space complexity, demonstrating the value of in-place solutions.

3. Real-World Analogies:

   • Number of Islands mirrored mapping out continents, while Surrounded Regions felt like managing territories on a map. These real-world parallels made the problems more engaging and relatable.

---

Key Takeaways

• DFS vs. BFS:

  • DFS is excellent for exploring connected components deeply, as seen in Number of Islands, while BFS excels in scenarios like Surrounded Regions, requiring layer-by-layer exploration.

• Grid Manipulation Simplifies Logic:

  • Marking visited cells directly in the grid is an efficient way to manage state without extra memory overhead.

• Two-Phase Solutions Work Wonders:

  • For problems like Surrounded Regions, separating the marking and flipping phases kept the solution modular and easy to debug.

---

Reflections

Both problems today were highly engaging. Number of Islands reinforced my understanding of DFS and connected component exploration, while Surrounded Regions required more strategic thinking to handle border-connected regions. Together, they showcased the versatility of graph traversal techniques and how grids can be tackled as graphs.

---

What’s Next?

Tomorrow, I’ll continue with Graph Problems, including Clone Graph, Evaluate Division, and another graph-based challenge. These will test my graph manipulation skills and push me further into logical reasoning and problem-solving.

Thank you for following along on this journey! Let’s keep exploring and solving these exciting challenges together.

Best regards,

Somuya