How do you solve Cat and Mouse on LeetCode?

Cat and Mouse (LeetCode #913) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(n²) space complexity. Key insight: Optimal play is crucial for both players.

What is the brute force solution for Cat and Mouse?

The brute force approach for Cat and Mouse is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach explores all possible moves for both the mouse and the cat. It simulates the game by recursively checking each possible state until a win, loss, or draw condition is met. The optimal Optimal Solution approach improves this to O(n²).

What are the interview tips for Cat and Mouse?

Explain your thought process clearly. Discuss edge cases and how they affect the game. Be prepared to optimize your solution and explain your reasoning.

What are common mistakes when solving Cat and Mouse?

Not considering all possible moves for both players. Ignoring memoization leading to redundant calculations.

#913

Cat and Mouse

Hard

MathDynamic ProgrammingGraph TheoryTopological SortMemoizationGame TheoryDynamic ProgrammingMemoization

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(n²)

💡

Intuition

Time O(n²)Space O(n²)

The optimal solution uses dynamic programming with memoization to store results of previous states. This prevents redundant calculations and allows us to efficiently determine the outcome of the game based on optimal moves.

⚙️

Algorithm

5 steps

1Step 1: Create a memoization table to store results for each state (mouse position, cat position, turn).
2Step 2: Define a recursive function that checks win/loss conditions and explores possible moves.
3Step 3: For the mouse's turn, check all possible moves and see if any lead to a guaranteed win.
4Step 4: For the cat's turn, check all possible moves and see if any lead to a guaranteed win for the cat.
5Step 5: Return the result based on the best possible outcome for the current player.

solution.py22 lines

1def catMouseGame(graph):
2    memo = {}
3    def dfs(mouse, cat, turn):
4        if mouse == 0: return 1
5        if mouse == cat: return 2
6        if (mouse, cat, turn) in memo: return memo[(mouse, cat, turn)]
7        if turn % 2 == 0:
8            for next_mouse in graph[mouse]:
9                if dfs(next_mouse, cat, turn + 1) == 1:
10                    memo[(mouse, cat, turn)] = 1
11                    return 1
12            memo[(mouse, cat, turn)] = 0
13            return 0
14        else:
15            for next_cat in graph[cat]:
16                if next_cat == 0: continue
17                if dfs(mouse, next_cat, turn + 1) == 2:
18                    memo[(mouse, cat, turn)] = 2
19                    return 2
20            memo[(mouse, cat, turn)] = 0
21            return 0
22    return dfs(1, 2, 0)

ℹ

Complexity note: The time complexity is O(n²) due to the memoization of states, where n is the number of nodes. The space complexity is also O(n²) because we store results for each unique combination of mouse, cat, and turn.

1Optimal play is crucial for both players.
2Understanding game states and transitions is key.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.