Hello Everyone!
Today was all about Graphs—a topic that feels like unraveling a web of connections. Graph problems are captivating because they reflect real-world scenarios, whether it’s navigating grids, planning schedules, or finding the shortest path between two points. Solving these problems required patience, structured thinking, and a willingness to explore every possibility.
How the Day Played Out
-
Number of Islands (Medium Difficulty)
- Task: Count the number of distinct islands in a grid where
1represents land and0represents water. -
The Strategy:
- Applied Depth First Search (DFS) to explore all connected components of land, marking visited cells to prevent revisiting.
- Also experimented with Breadth First Search (BFS), which worked just as well for this problem.
-
The Fun Part:
- Transforming the grid by marking cells during exploration felt like mapping out uncharted territory—it was visually satisfying to see the progress.
- Task: Count the number of distinct islands in a grid where
-
Course Schedule (Medium Difficulty)
- Task: Determine if it’s possible to finish all courses given their prerequisites (a classic directed acyclic graph problem).
-
The Strategy:
- Used Kahn’s algorithm for topological sorting, tracking indegrees for each course to identify dependencies.
- Iteratively reduced indegrees and detected cycles if there were remaining nodes with unmet prerequisites.
-
The Fun Part:
- Visualizing the dependency graph and methodically reducing prerequisites felt like solving a complex scheduling puzzle.
-
Shortest Path in Binary Matrix (Medium Difficulty)
- Task: Find the shortest path from the top-left to the bottom-right in a binary matrix.
-
The Strategy:
- Used Breadth First Search (BFS) to explore the matrix layer by layer, keeping track of distances to each cell.
- Managed edge cases like blocked start or end points to ensure the solution was robust.
-
The Fun Part:
- Navigating the grid in all 8 possible directions added a layer of complexity, making it feel like solving a real-world maze.
What Made Today Unique
-
Visual Problem Solving:
- Graph problems are inherently visual. From traversing grids to managing directed graphs, each problem felt like tackling a real-world scenario, making the process engaging and immersive.
-
Choosing Between BFS and DFS:
- Deciding when to use BFS versus DFS added an element of strategy to solving these problems. Understanding the strengths of each approach was a valuable learning experience.
-
Real-World Applications:
- Each problem had a tangible, real-world equivalent—exploring islands, managing course schedules, or navigating a maze. It made solving them feel practical and rewarding.
Key Takeaways
-
Graphs Are Everywhere:
- Mastering basic traversal techniques like BFS and DFS opens up solutions to a wide variety of graph-based problems.
-
Indegree is Key in Directed Graphs:
- Problems like Course Schedule highlighted the importance of managing indegrees efficiently to find topological orders and detect cycles.
-
Expand Your Directions in Grids:
- Challenges like Shortest Path in Binary Matrix required exploring all possible paths, including diagonals, which added complexity and depth to the solution.
Reflections
The Number of Islands problem was a fantastic way to practice exploring connected components, while Course Schedule challenged me to think critically about dependencies and cycles in directed graphs. Shortest Path in Binary Matrix was particularly exciting—it felt like solving a labyrinth while racing against time to find the optimal route.
What’s Next?
On Monday, I’ll conclude the week with Linked List Problems, including Reverse Linked List, Merge Two Sorted Lists, and Reorder List. These challenges will test my skills in manipulating pointers and navigating linked nodes.
Thank you for joining me on this journey! Let’s keep exploring and growing together as we dive deeper into the world of competitive programming.
Best regards,
Somuya
Top comments (0)