This problem requires predicting whether the mouse wins, the cat wins, or the game ends in a draw. Use dynamic programming with memoization over all possible mouse and cat positions, combined with graph indegree tracking and topological sorting. GhostInterview walks through the propagation of winning and losing states efficiently, avoiding cycles and ensuring correct final evaluation.
Problem Statement
You are given an undirected graph representing a game played by two players: Mouse and Cat. The graph is given as an adjacency list graph, where graph[a] contains all nodes b such that there is an edge between nodes a and b. The Mouse starts at node 1, the Cat starts at node 2, and node 0 represents a hole where the Mouse can escape. The players alternate turns with the Mouse moving first.
The game ends if the Mouse reaches the hole, if the Cat catches the Mouse by moving to the same node, or if a position repeats causing a draw. Your task is to determine the result of the game: 1 if the Mouse can guarantee a win, 2 if the Cat can guarantee a win, and 0 if the game results in a draw, applying the graph indegree and topological ordering pattern to compute all reachable states efficiently.
Examples
Example 1
Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0
Example details omitted.
Example 2
Input: graph = [[1,3],[0],[3],[0,2]]
Output: 1
Example details omitted.
Constraints
- 3 <= graph.length <= 50
- 1 <= graph[i].length < graph.length
- 0 <= graph[i][j] < graph.length
- graph[i][j] != i
- graph[i] is unique.
- The mouse and the cat can always move.
Solution Approach
Model All Game States
Represent each combination of Mouse and Cat positions and the player's turn as a distinct state. Initialize winning states for the Mouse reaching node 0 and the Cat catching the Mouse. This state modeling directly maps to the graph indegree pattern used to track topological propagation.
Topological Sort via Indegree
Compute the outdegree of each state and use a queue to propagate results in reverse. When all subsequent moves of a state are winning for one player, mark the current state as losing for the other. This ensures cycles do not prevent correct outcome determination, reflecting the topological ordering method.
Dynamic Programming with Memoization
Memoize the result of each state to avoid recomputation. For each state, propagate the outcome to parent states until the initial configuration is resolved. This DP approach guarantees correctness and efficiency within the O(N^3) time and O(N^2) space bounds for graph length N.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(N^3) |
| Space | O(N^2) |
The algorithm examines each combination of Mouse and Cat positions (O(N^2)) and each possible move from those positions (up to O(N)), yielding O(N^3) time complexity. Storing results for all states and turns requires O(N^2) space.
What Interviewers Usually Probe
- Expect candidates to model states for both players explicitly using graph nodes and turns.
- Look for correct handling of cycles and draw conditions using indegree-based propagation.
- Verify memoization prevents repeated computation across overlapping subgames.
Common Pitfalls or Variants
Common pitfalls
- Failing to account for the Cat cannot move to node 0, breaking correct state transitions.
- Not handling draw conditions when states repeat or indegree propagation stalls.
- Incorrectly updating parent states before all child outcomes are resolved, leading to wrong results.
Follow-up variants
- Change the starting positions of the Mouse and Cat to arbitrary nodes and analyze outcome.
- Introduce multiple holes and adapt topological propagation to multiple winning terminal states.
- Consider directed graphs where edges limit movement direction and recompute outcomes using the same DP pattern.
How GhostInterview Helps
- Automatically tracks all Mouse and Cat states and propagates outcomes with topological ordering.
- Memoizes intermediate states to avoid recomputation and provides a deterministic winning strategy.
- Highlights failure modes like cycles or incorrect indegree updates, ensuring correct evaluation.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main pattern used in Cat and Mouse?
The core pattern is graph indegree plus topological ordering combined with memoized dynamic programming to resolve all game states.
Why do we need memoization in Cat and Mouse?
Memoization prevents recomputation of outcomes for repeated Mouse-Cat position pairs and turn sequences, ensuring efficiency and correctness.
How are draw conditions handled in this problem?
Draws occur when states repeat without reaching terminal conditions, and the algorithm marks such states after indegree propagation stalls.
Can this solution handle cycles in the graph?
Yes, the topological ordering with indegree tracking propagates results correctly even when cycles exist, preventing infinite loops.
What is the expected complexity for the Cat and Mouse solution?
The solution has O(N^3) time and O(N^2) space complexity due to iterating all Mouse-Cat position combinations and possible moves.
Need direct help with Cat and Mouse instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Cat and Mouse from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Cat and Mouse II requires determining if the mouse can reach food before being caught using graph and topological ordering logic.
Open problem page#464 Can I WinDetermine if the first player can guarantee a win in a turn-based number selection game using state transition dynamic programming.
Open problem page#329 Longest Increasing Path in a MatrixFind the length of the longest increasing path in a matrix with given movement constraints using graph techniques.
Open problem page