Written by CS Students

In many interviews, you’ll often face problems that ask you to minimize the number of steps or the cost to reach a certain target. Most of these problems are actually graphs… just not explicitly given. One of the most important patterns behind them is the Implicit Graph.

In this post, we will cover:

• What this pattern is (with a simple board visualization)
• Key questions you should ask yourself
• Step by step implementation
• Time & Space Complexity
• A list of interview problems to practice

Explanation Board

• Implicit Graph Visualization

Key Questions (Q&A)

Why do we use BFS instead of DFS?
Because we want the minimum number of steps. BFS guarantees the shortest path.

Why do we use a visited set?
To avoid revisiting the same state and wasting time.

Why can we stop early?
Because the first time we reach the target is guaranteed to be optimal.

What defines a "state" in this problem?
The state is the current value (x).

Why do we skip already visited states?
Because any future visit will always have equal or greater cost.

What is the main idea behind this pattern?
Model the problem as a graph (states + operations) and apply BFS.

Implementation Using Python

from collections import deque

class Solution:
    def minimum(self , x : int) -> int:

        qu = deque()  
        qu.append((x , 0))  
        # (value , steps)
        # start from x with 0 steps

        visited = set()  
        visited.add(x)
        # to avoid revisiting the same state
        # this is essential in BFS

        while qu:

            value , steps = qu.popleft()
            # take the first element (FIFO)
            # this ensures level-by-level traversal (BFS)

            #! Early return
            if value == 0:
                return steps
            # once we reach the target
            # we return immediately (guaranteed minimum steps)

            #! Case 1 → divide by 3
            if value % 3 == 0 and value // 3 not in visited:
                qu.append((value // 3 , steps + 1))
                visited.add(value // 3)
                # generate a new state
                # increase steps
                # mark as visited to avoid duplicates

            #! Case 2 → divide by 2
            if value % 2 == 0 and value // 2 not in visited:
                qu.append((value // 2 , steps + 1))
                visited.add(value // 2)
                # same pattern:
                # generate → check → push

            #! Case 3 → subtract 1
            if value - 1 not in visited:
                qu.append((value - 1 , steps + 1))
                visited.add(value - 1)
                # always valid transition
                # guarantees progress toward 0

S = Solution()
print(S.minimum(6))

We treat each number as a state. From each state, we generate all possible transitions:

• divide by 3
• divide by 2
• subtract 1

We use BFS to guarantee the minimum number of steps, and a visited set to avoid revisiting states since the first visit is always optimal.

Complexity Analysis

Explanation

• The complexity depends on the number of reachable states, not just the input value.
• Each state is visited at most once due to the visited set.
• For every state, we generate a limited number of transitions.

In the worst case, the number of states can grow exponentially depending on the problem constraints.

Previous Interview Questions

Previous interviews questions you can find it here:
Implicit Graph Interviews

Think in states. Think in graphs.
HackerRank FCDS Always By Your Side 💚