How to Solve Any Graph Problem
The trick is in recognizing it as a graph problem
One of the most common challenges in coding interviews isn't just solving the problem—it's recognizing what kind of problem you're dealing with in the first place. Graph problems, in particular, can be tricky because they often disguise themselves under different guises. The key to cracking these questions lies in identifying that the problem can be modeled as a graph, even if it doesn't explicitly mention graphs.
Common Signs That a Problem Is a Graph Problem
Recognizing a graph problem often hinges on spotting certain patterns or keywords in the problem statement. Here are some indicators to help you identify when a problem is fundamentally a graph problem.
1. Grid and Matrix-Based Connectivity
Problems involving grids or matrices often can be modeled as graphs, even if they don't explicitly mention graphs.
Cells or elements are the nodes of the graph.
Adjacent cells (e.g., neighboring cells in a grid) are connected by edges.
Keywords: "Grid," "matrix," "2D array," "cells," "adjacent," "neighboring positions," "directions (up/down/left/right)."
Example:
"Given a 2D grid of '1's (land) and '0's (water), find the number of islands."
In this example, you can model each land cell as a node, and edges exist between horizontally or vertically adjacent land cells.
2. Dependency and Ordering
Problems that involve dependencies between entities can often be represented as graphs, particularly directed graphs.
Keywords: "Depends on," "prerequisite," "order," "sequence," "schedule," "build order."
Example: "Determine if it's possible to finish all courses given their prerequisites."
Here, courses are nodes, and prerequisites are directed edges from one course to another.
3. Directed Relationships and Social Networks
Problems involving relationships between entities, such as trust, friendship, following, or influence, can often be modeled using graphs. These relationships can be directed or undirected, depending on the nature of the connection.
Keywords: "Trusts," "follows," "influences," "friends," "relationships," "connections," "recommendations."
Example: "In a group of people, person A trusts person B. Find the person who is trusted by everyone but trusts no one."
4. State Spaces and Transformations
Many problems involve moving through a series of states or configurations, even if they don't explicitly mention graphs. In these cases:
States are the nodes of the graph.
Valid moves or transformations are the edges connecting the nodes.
Keywords: "State," "move," "step," "transition," "transform," "convert," "traverse," "explore," "reachable," "solve a puzzle."
Examples:
"You can unlock a lock by turning wheels. Find the minimum number of turns to open the lock."
"Find the minimum number of moves to solve a puzzle from a starting state to a goal state."
In these examples, each unique state of the system (e.g., a specific configuration of a lock or puzzle) represents a node, and possible moves or transformations between states are edges.
5. Explicit Graph Terminology
This is the most straightforward sign. If the problem directly mentions elements like nodes, edges, vertices, or explicitly refers to a graph, then it's clear you're dealing with a graph problem.
Keywords: "Graph," "node," "edge," "vertex," "connected," "path," "cycle," "neighbor," "network," "route."
Example: "Find the shortest path between two nodes in a graph."
How to Approach Graph Problems
Once you've identified a problem as a graph problem, the next step is to decide how to represent the graph and which algorithm to apply.
1. Representing the Graph
Adjacency List
What It Is: A collection of lists or arrays where each list represents a node and contains the nodes it's connected to.
When to Use: Suitable for sparse graphs where most nodes are not connected to every other node.
Why It's Common: Efficient in terms of space and allows for easy iteration over a node's neighbors.
Adjacency Matrix
What It Is: A 2D array where rows and columns represent nodes, and each cell
[i][j]indicates the presence (and possibly weight) of an edge between nodesiandj.When to Use: Useful for dense graphs where many nodes are interconnected or when you need to check for the existence of an edge quickly.
Trade-Off: Can be memory-intensive for large graphs.
No Explicit Data Structure Needed
In some problems, you don't need to build an explicit graph data structure because the connections are inherent or can be generated on the fly.
Examples:
Grids and Mazes: Use the grid itself for traversal; neighboring positions are determined by moving up, down, left, or right.
State Transitions: Define a function to generate neighboring states based on valid moves or transformations.
Key Point: Choose the representation that best fits the problem's requirements and constraints.
2. Choosing Between DFS and BFS
In interviews, almost all graph problems can be effectively solved using DFS or BFS. More complex algorithms like Dijkstra's or Ford–Fulkerson are rarely required due to time constraints and their complexity. Interviews typically don't allow time to implement and debug complex algorithms.
Depth-First Search (DFS)
Use When:
You need to explore all possible paths (e.g., to find all connected components, detect cycles).
The problem involves exhaustive search or backtracking.
Characteristics:
Goes as deep as possible along each branch before backtracking.
Can be implemented recursively or with a stack.
Common Interview Problems:
Finding connected components.
Detecting cycles in graphs.
Solving puzzles where all configurations need to be explored.
Breadth-First Search (BFS)
Use When:
You need the shortest path or minimum number of steps.
The problem involves levels or distances from a starting point.
Characteristics:
Explores all neighbors at the current depth before moving to the next level.
Uses a queue to keep track of nodes to visit next.
Common Interview Problems:
Finding the shortest path in unweighted graphs.
Solving puzzles where the minimal number of moves is required.
Traversing levels in a tree or graph.
Examples and Walkthroughs
Let's look at some common interview problems and how to recognize and solve them.
Example 1: Number of Islands
Leetcode 200
Problem Statement:
"Given a 2D grid of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically."
Recognition Clues:
Grid structure.
Adjacency between cells.
Need to group connected land cells.
Approach:
Modeling the Problem:
Each cell in the grid is a node.
Edges exist between horizontally or vertically adjacent land cells ('1's).
Algorithm Choice:
Use DFS or BFS to explore connected land cells.
No need to build an explicit graph; use the grid itself for traversal.
Solution Outline:
Initialize a counter for islands.
Iterate through each cell in the grid.
When a land cell ('1') is found and not visited:
Increment the island counter.
Perform DFS/BFS from this cell to mark all connected land cells as visited.
Continue until all cells are processed.
Example 2: Course Schedule
Leetcode 207
Problem Statement:
"There are numCourses you have to take, labeled from 0 to numCourses - 1. Some courses have prerequisites. Given the total number of courses and a list of prerequisite pairs, is it possible to finish all courses?"
Recognition Clues:
Dependencies between courses (prerequisites).
Need to determine if an ordering is possible without conflicts.
Potential cycles indicating impossible schedules.
Approach:
Modeling the Problem:
Represent courses as nodes.
Directed edges represent prerequisites (from prerequisite course to dependent course).
Graph Representation:
Use an adjacency list to represent the graph efficiently.
Algorithm Choice:
Use DFS with cycle detection.
Alternatively, use BFS with Kahn's algorithm for topological sorting.
Solution Outline:
Build the adjacency list for the graph.
Use DFS to detect cycles:
Keep track of visited nodes and recursion stack.
If a node is revisited while in the recursion stack, a cycle exists.
If a cycle is detected, return
False; otherwise, returnTrue.
Example 3: Word Ladder
Leetcode 127
Problem Statement:
"Given two words (beginWord and endWord), and a dictionary's word list, find the length of the shortest transformation sequence from beginWord to endWord, such that only one letter can be changed at a time and each transformed word must exist in the word list."
Recognition Clues:
Transformation steps between words.
One-letter differences imply connections.
Seeking the shortest sequence (path).
Approach:
Modeling the Problem:
Each word is a node.
Edges exist between words that differ by one letter.
Graph Representation:
While an explicit graph could be built, it's more efficient to generate neighbors on the fly.
Algorithm Choice:
Use BFS to find the shortest path from
beginWordtoendWord.
Solution Outline:
Use BFS starting from
beginWord.At each step, generate all valid transformations (words in the word list differing by one letter).
Keep track of visited words to prevent cycles.
Return the length of the path when
endWordis reached.
Practice Problems
Problem 1: Open the Lock
Leetcode 752
"You have a lock with 4 circular wheels, each wheel has 10 digits from '0' to '9'. Each wheel can be turned forward or backward by one digit, forming a new combination. The lock initially starts at '0000'. You are given a list of deadends, meaning combinations that will cause the lock to stop working if entered. Given a target combination, return the minimum total number of turns required to open the lock, or -1 if it is impossible."
Hint: Consider each combination as a state, and the action of turning a wheel as moving to an adjacent state. Use BFS to find the shortest path from '0000' to the target, while avoiding deadends.
Problem 2: Sliding Puzzle
Leetcode 773
"You're given a 2x3 board of numbers ranging from 0 to 5, where 0 represents the empty space. You can swap the empty space with any of its adjacent numbers (up, down, left, right). The goal is to move the numbers until the board is in the solved state [[1,2,3],[4,5,0]]. Return the minimum number of moves required to reach the solved state, or -1 if it is impossible."
Hint: Treat each board configuration as a state in a graph, and possible moves as edges between states. Use BFS to find the minimum number of moves to reach the solved state.
Problem 3: The Maze
Leetcode 490
"There is a ball in a maze with empty spaces and walls. The ball can go in any of the four directions (up, down, left, right) until it hits a wall. Given the maze, the ball's start position, and the destination, determine whether the ball could stop at the destination."
Hint: Model the maze as a graph where each position the ball can stop at is a node, and edges represent the ball rolling from one stop position to another. Use DFS or BFS to explore all reachable positions from the start.
Tips for Recognizing Graph Problems
Identify Entities and Connections:
Entities as Nodes: Items, states, or positions that can be represented as nodes.
Connections as Edges: Relationships, moves, or transformations that link nodes.
Look for Movement or Transformation:
If the problem involves moving from one state to another through valid moves, it's likely a graph traversal.
Understand the Problem's Structure:
Grid or Matrix: Cells are nodes; adjacent cells are connected.
Dependencies: Items depending on others can be modeled with directed edges.
State Transitions: Different configurations or states connected by allowed operations.
Consider Implicit Graphs:
Even if the problem doesn't mention graphs, ask yourself if you can model it as one.
Focus on Common Graph Scenarios:
Traversal, Connectivity, Shortest Path, Cycle Detection.
Final Thoughts
Recognizing that a problem is fundamentally a graph problem is a crucial skill in coding interviews. Once you make that connection, the path to the solution becomes much clearer. Remember:
Most interview graph problems can be solved with DFS or BFS.
You don't always need to build an explicit graph data structure.
Understanding how to represent the graph efficiently is key.
By practicing identifying these patterns and familiarizing yourself with fundamental graph algorithms, you'll be better prepared to tackle these problems confidently.
Feel free to share your thoughts or any questions you have about recognizing graph problems.
Stay curious, and happy coding!
Nurbo Kusmagul
Need Help with Coding Interviews?
Are you struggling with coding problems or feeling unprepared for your upcoming interviews? You're not alone, and I'm here to help.
With years of experience as a coding interview coach, I offer personalized one-on-one sessions to:
Master problem-solving skills for coding and system design interviews
Boost your confidence for the big day
Develop effective strategies to level up your tech career
Ready to elevate your coding interview skills? Book a personalized 1:1 coaching session with me today!
Still have questions? Let's chat! You can book a free 30-minute consultation to discuss how I can help you achieve your goals.
Feel free to email me at nurbo.kusmagul@(google’s email service) or connect with me on LinkedIn.
Looking forward to helping you succeed!