LeetCode 913 - Cat and Mouse

LeetCode Problem 913

Difficulty: 🔴 Hard
Topics: Math, Dynamic Programming, Graph Theory, Topological Sort, Memoization, Game Theory

Solution

Problem Understanding

In this problem, we are given an undirected graph where two players, Mouse and Cat, move alternately across the graph according to specific rules. The graph is represented as an adjacency list, where graph[a] contains all nodes directly connected to node a.

The Mouse always starts at node 1, and the Cat always starts at node 2. The Mouse moves first. There is a special node, node 0, which represents a hole. If the Mouse reaches node 0, the Mouse immediately wins. If the Cat ever occupies the same node as the Mouse, the Cat immediately wins.

The Cat has one additional restriction: it cannot move into the hole at node 0.

The game can also end in a draw. A draw occurs when the exact same game state appears again. A game state consists of three pieces of information:

• The Mouse's position
• The Cat's position
• Whose turn it is

If all three repeat, the game is considered infinite, and the result is a draw.

The problem asks us to determine the outcome of the game assuming both players play optimally. We must return:

• 1 if the Mouse can force a win
• 2 if the Cat can force a win
• 0 if neither side can force a win and the game ends in a draw

The constraints are important. The graph contains at most 50 nodes, which means the total number of possible game states is manageable:

• Mouse positions: 50
• Cat positions: 50
• Turns: 2

This gives at most 50 × 50 × 2 = 5000 states.

That number is small enough that we can treat the problem as a state graph and perform graph-based dynamic programming or retrograde analysis.

Several edge cases are important:

• The Mouse may already be close to the hole and win immediately.
• The Cat may trap the Mouse quickly.
• Cycles in the graph may create infinite loops and therefore draws.
• Since the Cat cannot enter node 0, we must carefully exclude those transitions.
• Some states cannot be determined immediately and only become solvable after propagating information backward through the game graph.

A naive recursive simulation can easily revisit the same states repeatedly and may not terminate correctly without cycle detection.

Approaches

Brute Force Approach

A straightforward approach is to simulate all possible game paths recursively using minimax logic.

For each state (mouse, cat, turn):

• If the Mouse reaches node 0, return Mouse win.

• If Mouse and Cat occupy the same node, return Cat win.

• Otherwise:

• If it is the Mouse's turn, try every Mouse move.

• If it is the Cat's turn, try every Cat move except node 0.

The current player chooses the move that maximizes their outcome.

However, this approach runs into a major problem: cycles.

Because the graph may contain loops, the same game state can appear repeatedly. Without memoization and cycle tracking, recursion may never terminate. Even with memoization, handling draws correctly becomes extremely complicated because some states depend recursively on themselves.

The brute-force search effectively explores an exponentially large game tree.

Key Insight Behind the Optimal Solution

The critical observation is that this is a finite deterministic game with a limited number of states.

Instead of searching forward from the starting position, we can work backward from known outcomes.

This technique is called retrograde analysis, and it is commonly solved using topological propagation over game states.

We classify states into three categories:

• Mouse-winning
• Cat-winning
• Draw

We begin with states whose outcomes are already known:

• If Mouse is at node 0, Mouse wins.
• If Mouse and Cat are on the same node, Cat wins.

Then we propagate those results backward to predecessor states.

The key game theory rule is:

• If a player can move into a winning state for themselves, then the current state is winning for that player.
• If every possible move leads to a winning state for the opponent, then the current state is losing.

This transforms the problem into a graph propagation problem similar to topological sorting.

Because the number of states is bounded, this approach efficiently solves the entire game state space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores all possible game paths recursively
Optimal	O(n³)	O(n³)	Uses reverse BFS and game state propagation

Algorithm Walkthrough

State Definition

We represent each game state using:

• mouse position
• cat position
• turn

Where:

• turn = 0 means Mouse moves next
• turn = 1 means Cat moves next

We store:

• color[mouse][cat][turn]

• 0 = draw/unknown

• 1 = Mouse win

• 2 = Cat win

We also maintain:

• degree[mouse][cat][turn]

This represents how many legal moves remain from that state.

Step-by-Step Algorithm

1. Initialize all states as draws.

Initially, we do not know the outcome of most states. Every state starts as undecided. 2. Mark terminal winning states.

These states are immediately known:

• If mouse == 0, Mouse already reached the hole, so Mouse wins.
• If mouse == cat, Cat already caught the Mouse, so Cat wins.

These states are inserted into a queue for BFS propagation. 3. Compute outdegrees for every state.

For each state, count how many legal moves the current player has.

This is important because if all moves eventually lose, then the state itself becomes losing.

For Mouse turns:

• Degree equals number of Mouse neighbors.

For Cat turns:

• Degree equals number of Cat neighbors excluding node 0.

4. Process states using reverse BFS.

We repeatedly remove solved states from the queue.

Suppose state (m, c, t) is already known to be a Mouse win or Cat win.

We then examine all predecessor states that could move into (m, c, t). 5. Determine predecessor outcomes.

For each predecessor:

• If the predecessor player can move into a winning state for themselves, mark predecessor as winning immediately.
• Otherwise, decrement its degree.
• If degree becomes zero, every move leads to opponent victory, so mark predecessor as losing.

6. Continue until queue becomes empty.

Eventually all forced wins and losses propagate through the state graph.

Any remaining unresolved states are draws. 7. Return the starting state result.

The initial game state is:

• Mouse at 1
• Cat at 2
• Mouse turn

Return the computed result for this state.

Why it works

The algorithm works because every game state depends only on future states. By starting from terminal states and propagating backward, we guarantee that when a state is resolved, its outcome is logically correct.

A state becomes winning if the current player has at least one move to a losing state for the opponent. A state becomes losing if every possible move leads to opponent-winning states.

This exactly matches optimal game play.

Because the total number of states is finite, the BFS propagation eventually stabilizes.

Python Solution

from collections import deque
from typing import List

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        n = len(graph)

        DRAW = 0
        MOUSE = 1
        CAT = 2

        MOUSE_TURN = 0
        CAT_TURN = 1

        color = [[[DRAW] * 2 for _ in range(n)] for _ in range(n)]
        degree = [[[0] * 2 for _ in range(n)] for _ in range(n)]

        # Compute degrees
        for mouse in range(n):
            for cat in range(n):
                degree[mouse][cat][MOUSE_TURN] = len(graph[mouse])

                cat_moves = 0
                for nxt in graph[cat]:
                    if nxt != 0:
                        cat_moves += 1

                degree[mouse][cat][CAT_TURN] = cat_moves

        queue = deque()

        # Mouse reaches hole -> Mouse wins
        for cat in range(n):
            for turn in range(2):
                if color[0][cat][turn] == DRAW:
                    color[0][cat][turn] = MOUSE
                    queue.append((0, cat, turn, MOUSE))

        # Cat catches mouse -> Cat wins
        for node in range(1, n):
            for turn in range(2):
                if color[node][node][turn] == DRAW:
                    color[node][node][turn] = CAT
                    queue.append((node, node, turn, CAT))

        def parents(mouse: int, cat: int, turn: int):
            if turn == MOUSE_TURN:
                # Previous was Cat turn
                for prev_cat in graph[cat]:
                    if prev_cat != 0:
                        yield mouse, prev_cat, CAT_TURN
            else:
                # Previous was Mouse turn
                for prev_mouse in graph[mouse]:
                    yield prev_mouse, cat, MOUSE_TURN

        while queue:
            mouse, cat, turn, result = queue.popleft()

            for pmouse, pcat, pturn in parents(mouse, cat, turn):
                if color[pmouse][pcat][pturn] != DRAW:
                    continue

                # Current player can force a win
                if (
                    (pturn == MOUSE_TURN and result == MOUSE)
                    or
                    (pturn == CAT_TURN and result == CAT)
                ):
                    color[pmouse][pcat][pturn] = result
                    queue.append((pmouse, pcat, pturn, result))
                else:
                    degree[pmouse][pcat][pturn] -= 1

                    # All moves lose
                    if degree[pmouse][pcat][pturn] == 0:
                        losing_result = CAT if pturn == MOUSE_TURN else MOUSE

                        color[pmouse][pcat][pturn] = losing_result
                        queue.append(
                            (pmouse, pcat, pturn, losing_result)
                        )

        return color[1][2][MOUSE_TURN]

The implementation begins by defining constants representing game outcomes and player turns. This makes the logic more readable and avoids relying on magic numbers throughout the code.

The color array stores the resolved outcome of every state. Initially, all states are marked as DRAW, meaning unresolved.

The degree array tracks how many legal moves remain from each state. This is essential for determining when a state becomes losing because all options have been exhausted.

The algorithm first initializes terminal states:

• Mouse at node 0 is an immediate Mouse win.
• Mouse and Cat on the same node is an immediate Cat win.

These states are inserted into the BFS queue.

The parents generator computes reverse edges in the game graph. Instead of moving forward from a state, we determine which earlier states could have transitioned into the current state.

During BFS propagation:

• If a predecessor player can move into a state that guarantees victory for themselves, the predecessor becomes winning immediately.
• Otherwise, we decrement the predecessor degree.
• Once all moves are exhausted, the predecessor becomes losing.

At the end, unresolved states remain draws, and we return the value for the initial state (1, 2, MouseTurn).

Go Solution

package main

import "container/list"

func catMouseGame(graph [][]int) int {
	n := len(graph)

	const (
		DRAW  = 0
		MOUSE = 1
		CAT   = 2
	)

	const (
		MOUSE_TURN = 0
		CAT_TURN   = 1
	)

	color := make([][][]int, n)
	degree := make([][][]int, n)

	for i := 0; i < n; i++ {
		color[i] = make([][]int, n)
		degree[i] = make([][]int, n)

		for j := 0; j < n; j++ {
			color[i][j] = make([]int, 2)
			degree[i][j] = make([]int, 2)
		}
	}

	// Compute degrees
	for mouse := 0; mouse < n; mouse++ {
		for cat := 0; cat < n; cat++ {
			degree[mouse][cat][MOUSE_TURN] = len(graph[mouse])

			catMoves := 0
			for _, nxt := range graph[cat] {
				if nxt != 0 {
					catMoves++
				}
			}

			degree[mouse][cat][CAT_TURN] = catMoves
		}
	}

	type State struct {
		mouse  int
		cat    int
		turn   int
		result int
	}

	queue := list.New()

	// Mouse reaches hole
	for cat := 0; cat < n; cat++ {
		for turn := 0; turn < 2; turn++ {
			color[0][cat][turn] = MOUSE
			queue.PushBack(State{0, cat, turn, MOUSE})
		}
	}

	// Cat catches mouse
	for node := 1; node < n; node++ {
		for turn := 0; turn < 2; turn++ {
			color[node][node][turn] = CAT
			queue.PushBack(State{node, node, turn, CAT})
		}
	}

	for queue.Len() > 0 {
		front := queue.Front()
		queue.Remove(front)

		state := front.Value.(State)

		mouse := state.mouse
		cat := state.cat
		turn := state.turn
		result := state.result

		if turn == MOUSE_TURN {
			// Parent was Cat turn
			for _, prevCat := range graph[cat] {
				if prevCat == 0 {
					continue
				}

				pmouse := mouse
				pcat := prevCat
				pturn := CAT_TURN

				if color[pmouse][pcat][pturn] != DRAW {
					continue
				}

				if result == CAT {
					color[pmouse][pcat][pturn] = CAT
					queue.PushBack(State{
						pmouse,
						pcat,
						pturn,
						CAT,
					})
				} else {
					degree[pmouse][pcat][pturn]--

					if degree[pmouse][pcat][pturn] == 0 {
						color[pmouse][pcat][pturn] = MOUSE
						queue.PushBack(State{
							pmouse,
							pcat,
							pturn,
							MOUSE,
						})
					}
				}
			}
		} else {
			// Parent was Mouse turn
			for _, prevMouse := range graph[mouse] {
				pmouse := prevMouse
				pcat := cat
				pturn := MOUSE_TURN

				if color[pmouse][pcat][pturn] != DRAW {
					continue
				}

				if result == MOUSE {
					color[pmouse][pcat][pturn] = MOUSE
					queue.PushBack(State{
						pmouse,
						pcat,
						pturn,
						MOUSE,
					})
				} else {
					degree[pmouse][pcat][pturn]--

					if degree[pmouse][pcat][pturn] == 0 {
						color[pmouse][pcat][pturn] = CAT
						queue.PushBack(State{
							pmouse,
							pcat,
							pturn,
							CAT,
						})
					}
				}
			}
		}
	}

	return color[1][2][MOUSE_TURN]
}

The Go implementation closely mirrors the Python version, but there are a few language-specific differences.

Go does not provide dynamic multidimensional arrays automatically, so we explicitly allocate all three dimensions of color and degree.

The BFS queue uses container/list, since Go does not have a built-in deque structure.

A custom State struct stores the BFS state information cleanly.

Because Go slices are reference types, adjacency traversal remains efficient without copying data.

Integer overflow is not a concern because the state count is very small.

Worked Examples

Example 1

graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]

Initial state:

Mouse	Cat	Turn	State
1	2	Mouse	Unknown

The algorithm first initializes terminal states.

State	Result
(0, c, turn)	Mouse win
(x, x, turn)	Cat win

The BFS queue initially contains all these terminal states.

Now propagation begins.

Suppose we process:

Current State	Result
(0,2,MouseTurn)	Mouse win

We examine predecessor states that could lead here.

If a predecessor Mouse move can force entry into (0,2,MouseTurn), that predecessor becomes Mouse-winning.

As propagation continues, some states become forced Cat wins, while others become Mouse wins.

Eventually, the initial state (1,2,MouseTurn) remains unresolved because both players can avoid losing indefinitely.

Final result:

0

This means optimal play leads to a draw.

Example 2

graph = [[1,3],[0],[3],[0,2]]

Initial state:

Mouse	Cat	Turn
1	2	Mouse

Mouse has an immediate winning move:

1 -> 0

Since node 0 is the hole, Mouse wins instantly.

Propagation quickly marks the initial state as Mouse-winning.

Final result:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n³)	There are O(n²) states and each processes O(n) transitions
Space	O(n³)	Storage for state colors, degrees, and BFS queue

The graph contains at most n² × 2 states because each state depends on Mouse position, Cat position, and turn.

For every state, we may inspect all neighboring transitions. Since each node can connect to up to n neighbors, total processing becomes O(n³).

The space complexity comes from storing:

• The result of every state
• The degree of every state
• The BFS queue

All of these are bounded by the number of game states.

Test Cases

from typing import List

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        from collections import deque

        n = len(graph)

        DRAW = 0
        MOUSE = 1
        CAT = 2

        MOUSE_TURN = 0
        CAT_TURN = 1

        color = [[[DRAW] * 2 for _ in range(n)] for _ in range(n)]
        degree = [[[0] * 2 for _ in range(n)] for _ in range(n)]

        for m in range(n):
            for c in range(n):
                degree[m][c][MOUSE_TURN] = len(graph[m])
                degree[m][c][CAT_TURN] = sum(
                    1 for nxt in graph[c] if nxt != 0
                )

        queue = deque()

        for c in range(n):
            for t in range(2):
                color[0][c][t] = MOUSE
                queue.append((0, c, t, MOUSE))

        for x in range(1, n):
            for t in range(2):
                color[x][x][t] = CAT
                queue.append((x, x, t, CAT))

        def parents(m, c, t):
            if t == MOUSE_TURN:
                for pc in graph[c]:
                    if pc != 0:
                        yield m, pc, CAT_TURN
            else:
                for pm in graph[m]:
                    yield pm, c, MOUSE_TURN

        while queue:
            m, c, t, result = queue.popleft()

            for pm, pc, pt in parents(m, c, t):
                if color[pm][pc][pt] != DRAW:
                    continue

                if (
                    (pt == MOUSE_TURN and result == MOUSE)
                    or
                    (pt == CAT_TURN and result == CAT)
                ):
                    color[pm][pc][pt] = result
                    queue.append((pm, pc, pt, result))
                else:
                    degree[pm][pc][pt] -= 1

                    if degree[pm][pc][pt] == 0:
                        lose = CAT if pt == MOUSE_TURN else MOUSE
                        color[pm][pc][pt] = lose
                        queue.append((pm, pc, pt, lose))

        return color[1][2][MOUSE_TURN]

sol = Solution()

# Example 1, draw state
assert sol.catMouseGame(
    [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
) == 0

# Example 2, mouse wins immediately
assert sol.catMouseGame(
    [[1,3],[0],[3],[0,2]]
) == 1

# Small graph where cat catches mouse quickly
assert sol.catMouseGame(
    [[1],[0,2],[1]]
) == 1

# Mouse trapped by cat eventually
assert sol.catMouseGame(
    [[1],[0,2],[1,3],[2]]
) == 1

# Graph with cycles leading to draw
assert sol.catMouseGame(
    [[1,2],[0,2],[0,1]]
) == 0

# Larger cyclic graph
assert sol.catMouseGame(
    [[1,2],[0,3],[0,3],[1,2]]
) in [0,1,2]

# Dense graph stress case
assert sol.catMouseGame(
    [
        [1,2,3],
        [0,2,3],
        [0,1,3],
        [0,1,2]
    ]
) in [0,1,2]

Test	Why
Example 1	Validates draw detection
Example 2	Validates immediate Mouse victory
Small linear graph	Tests simple path movement
Mouse trapped eventually	Tests forced-win propagation
Triangle cycle	Tests repeated-state draw handling
Larger cycle	Tests complex cyclic interactions
Dense graph	Stress-tests transition handling

Edge Cases

One important edge case occurs when the Mouse can immediately move into the hole. A naive implementation might continue searching deeper game states unnecessarily, but the correct behavior is to terminate immediately with a Mouse win. The implementation handles this by initializing all states where mouse == 0 as terminal Mouse-winning states before BFS propagation begins.

Another critical edge case involves cycles that never resolve into a forced win. Without careful handling, recursive solutions may loop forever or incorrectly classify these states. The reverse BFS approach avoids this problem entirely because unresolved states naturally remain marked as draws after all forced wins and losses have propagated.

A third subtle case occurs because the Cat is forbidden from entering node 0. Forgetting this restriction can completely change the game outcome and produce invalid transitions. The implementation explicitly excludes node 0 whenever generating Cat moves and when computing Cat outdegrees.

A final edge case involves states where every possible move leads to opponent victory. Some implementations incorrectly stop after discovering one losing move. However, a state only becomes losing after all legal moves have been exhausted. The degree-tracking mechanism guarantees this condition is handled correctly by decrementing remaining valid moves until none are left.