DAY 27 Navigating Graphs: From Islands to Regions

Hello Everyone!

Day 2 of Week 6 was dedicated to Graph Problems, where each challenge felt like solving a real-world mystery. Graph problems require a structured approach, whether it’s exploring connected components or marking regions. Today’s tasks tested my traversal skills and my ability to manage grids as graphs.

How the Day Played Out

1. Number of Islands (Medium Difficulty)

   • 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 used Depth First Search (DFS) to explore connected components of land.
     • Marked cells as visited by modifying the grid directly, reducing the need for extra memory.
   • The Fun Part:
     • Watching islands “disappear” as I marked cells during DFS felt like uncovering hidden treasures one piece at a time.

2. Surrounded Regions (Medium Difficulty)

   • Flip all Os that are surrounded by Xs to X, leaving only border-connected Os intact.
   • The Strategy:
     • Used Breadth First Search (BFS) from the border Os, marking them as non-flippable.
     • Flipped the remaining unvisited Os to X in a second pass.
   • The Fun Part:
     • The two-phase process (marking and flipping) was satisfying—it felt like creating order from chaos.

What Made Today Special

1. Graph Traversal in Grids:

   • Both problems treated grids as graphs, which was a refreshing change from typical adjacency lists or matrices. Traversing them required visualizing connections effectively.

2. Efficient State Management:

   • Modifying the grid directly to mark visited cells (instead of using additional data structures) improved efficiency and reduced space complexity.

3. Real-World Analogies:

   • Number of Islands felt like mapping out continents, while Surrounded Regions mirrored controlling territories—it made the problems feel practical and engaging.

Key Takeaways

• DFS vs. BFS:

  • DFS is great for exploring connected components deeply, while BFS shines in scenarios requiring layer-by-layer exploration, like Surrounded Regions.

• Grid Manipulation is Key:

  • Modifying the grid in place for marking visited cells simplifies solutions and avoids unnecessary memory usage.

• Two-Phase Solutions Work Well:

  • For problems like Surrounded Regions, separating the marking and flipping phases keeps the logic clean and modular.

Reflections

Both problems today were fun and engaging. Number of Islands was straightforward but rewarding, as it strengthened my DFS implementation skills. Surrounded Regions was more nuanced, requiring careful handling of border-connected regions and strategic grid manipulation. Together, they emphasized the versatility of graph traversal techniques.

What’s Next?

Tomorrow, I’ll continue with Graph Problems, tackling Clone Graph, Evaluate Division, and another graph-based task. These will push me further into the realm of graph manipulation and logical reasoning.

Thanks for following along! Let’s continue solving, learning, and growing together.