Facebook Pixel

913. Cat and Mouse

HardGraphTopological SortMemoizationMathDynamic ProgrammingGame Theory
Leetcode Link

Problem Description

This is a game theory problem where a Mouse and a Cat play a turn-based game on an undirected graph.

Game Setup:

  • The game is played on an undirected graph represented as graph[a], which contains a list of all nodes b such that there's an edge between node a and node b
  • Mouse starts at node 1 and moves first
  • Cat starts at node 2 and moves second
  • There's a hole at node 0
  • Players alternate turns

Movement Rules:

  • On each turn, a player must move along one edge from their current position to an adjacent node
  • For example, if Mouse is at node 1, it must move to one of the nodes in [graph](/problems/graph_intro)[1]
  • Important restriction: The Cat cannot move to node 0 (the hole)

Winning Conditions: The game can end in three ways:

  1. Cat wins: If the Cat ever occupies the same node as the Mouse (catches the Mouse)
  2. Mouse wins: If the Mouse reaches node 0 (the hole)
  3. Draw: If the same game state repeats (same positions for both players with the same player's turn to move)

Problem Task: Given the graph, and assuming both players play optimally (make the best possible moves), determine the outcome of the game:

  • Return 1 if the Mouse wins
  • Return 2 if the Cat wins
  • Return 0 if the game ends in a draw

The key challenge is to analyze all possible game states and determine the optimal strategy for both players, considering that each player will make the best move possible to achieve their winning condition.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

To solve this game theory problem, we need to think backwards from the end states. We know for certain who wins in specific situations - when the Mouse reaches the hole (Mouse wins) or when the Cat catches the Mouse (Cat wins). These are our "boundary states" with known outcomes.

The key insight is that we can work backwards from these known winning/losing states to determine the outcome of earlier game states. If we know the outcomes of all possible next states from a given position, we can determine the outcome of the current position.

Think of it like this: if it's the Mouse's turn and the Mouse can move to at least one position where the Mouse wins, then the Mouse will choose that move (playing optimally). Conversely, if all possible moves lead to Cat winning, then the current position is a losing position for the Mouse.

This naturally leads us to a reverse topological traversal approach. We start from the known end states and propagate the results backwards through the game state graph. Each game state is represented by three components: (mouse_position, cat_position, whose_turn).

The challenge is handling the "degree" concept - we need to know when all possible moves from a state lead to a loss for the current player. We track this by counting how many moves are available from each state. When we find a losing move for a player, we decrease the degree. If the degree reaches 0, it means all moves lead to a loss, so the current state is a losing state for that player.

The draw condition is handled implicitly - if a state doesn't get marked as a win for either player after we've processed all states, it must be a draw. This happens when neither player can force a win from that position.

By using BFS from the boundary states and carefully tracking which states lead to wins/losses, we can determine the outcome of the initial state (1, 2, MOUSE_TURN) - which is exactly what the problem asks for.

Learn more about Graph, Topological Sort, Memoization, Math and Dynamic Programming patterns.

Solution Approach

The solution implements a topological sorting approach using BFS to determine the game outcome by working backwards from known end states.

State Representation:

  • Each game state is represented as (mouse_position, cat_position, turn)
  • turn is either MOUSE_TURN (0) or CAT_TURN (1)
  • Game outcomes are represented as MOUSE_WIN (1), CAT_WIN (2), or TIE (0)

Data Structures:

  1. Answer Array: ans[m][c][t] - 3D array storing the outcome for each state
  2. Degree Array: degree[m][c][t] - tracks the number of possible moves from each state
  3. Queue: Used for BFS traversal of states

Algorithm Steps:

  1. Initialize Degree Array:

    • For each state (i, j, turn):
      • If it's Mouse's turn: degree[i][j][MOUSE_TURN] = len([graph](/problems/graph_intro)[i]) (number of Mouse's adjacent nodes)
      • If it's Cat's turn: degree[i][j][CAT_TURN] = len(graph[j]) (number of Cat's adjacent nodes)
    • Special case: Subtract 1 from Cat's degree if the hole (node 0) is adjacent, since Cat cannot move there

  2. Initialize Boundary States:

    • Mouse wins: When Mouse reaches hole: ans[0][j][turn] = MOUSE_WIN for all j and both turns
    • Cat wins: When Cat catches Mouse: ans[i][i][turn] = CAT_WIN for all i and both turns
    • Add all boundary states to the queue

  3. BFS Propagation:

    • Process each state from the queue
    • For each current state, find all possible previous states using get_prev_states():
      • If current turn is Mouse's, previous turn was Cat's: Cat could have been at any adjacent position
      • If current turn is Cat's, previous turn was Mouse's: Mouse could have been at any adjacent position

  4. Update Previous States:

    • For each previous state (pm, pc, pt):
      • If already determined (ans[pm][pc][pt] != TIE), skip
      • Immediate win condition: If the player in the previous turn matches the winner of current state (e.g., Mouse's turn and current state is Mouse win), mark previous state as a win for that player
      • All moves lose condition: Otherwise, decrement the degree. If degree[pm][pc][pt] reaches 0, all moves from that state lead to loss, so mark it as a win for the opponent

  5. Return Result:

    • After processing all states, return ans[MOUSE_START][CAT_START][MOUSE_TURN]
    • This gives the outcome when Mouse starts at node 1, Cat at node 2, and it's Mouse's turn

The algorithm ensures that all reachable states are evaluated, and states that remain unmarked after the BFS are draws (neither player can force a win).

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider a simple graph with 4 nodes:

    0 (hole)
   / \
  1---3
   \ /
    2

Graph representation: graph = [[1,3], [0,2,3], [1,3], [0,1,2]]

  • Node 0 connects to nodes 1 and 3
  • Node 1 connects to nodes 0, 2, and 3
  • Node 2 connects to nodes 1 and 3
  • Node 3 connects to nodes 0, 1, and 2

Initial setup: Mouse at node 1, Cat at node 2, Mouse moves first.

Step 1: Initialize Degree Array

For each state (mouse_pos, cat_pos, turn), count possible moves:

  • State (1, 2, MOUSE_TURN): Mouse at 1 can move to [0,2,3] → degree = 3
  • State (1, 2, CAT_TURN): Cat at 2 can move to [1,3] → degree = 2 (node 0 excluded)
  • State (3, 2, MOUSE_TURN): Mouse at 3 can move to [0,1,2] → degree = 3
  • And so on for all states...

Step 2: Initialize Boundary States

Mouse wins (reaches hole):

  • (0, 1, MOUSE_TURN) = MOUSE_WIN
  • (0, 1, CAT_TURN) = MOUSE_WIN
  • (0, 2, MOUSE_TURN) = MOUSE_WIN
  • (0, 2, CAT_TURN) = MOUSE_WIN
  • (0, 3, MOUSE_TURN) = MOUSE_WIN
  • (0, 3, CAT_TURN) = MOUSE_WIN

Cat wins (catches Mouse):

  • (1, 1, MOUSE_TURN) = CAT_WIN
  • (1, 1, CAT_TURN) = CAT_WIN
  • (2, 2, MOUSE_TURN) = CAT_WIN
  • (2, 2, CAT_TURN) = CAT_WIN
  • (3, 3, MOUSE_TURN) = CAT_WIN
  • (3, 3, CAT_TURN) = CAT_WIN

Step 3: BFS Propagation

Process boundary state (0, 2, CAT_TURN) = MOUSE_WIN:

  • Previous states (Cat just moved to 2 from adjacent nodes):
    • Could have been (0, 1, MOUSE_TURN) → Cat was at 1, moved to 2
    • Could have been (0, 3, MOUSE_TURN) → Cat was at 3, moved to 2
  • Both are already MOUSE_WIN, so skip

Process boundary state (1, 1, MOUSE_TURN) = CAT_WIN:

  • Previous states (Mouse just moved to 1):
    • Could have been (0, 1, CAT_TURN) → Mouse was at 0, moved to 1
    • Could have been (2, 1, CAT_TURN) → Mouse was at 2, moved to 1
    • Could have been (3, 1, CAT_TURN) → Mouse was at 3, moved to 1
  • State (3, 1, CAT_TURN): Since current is CAT_WIN and previous turn was Cat's, mark as CAT_WIN immediately

Step 4: Continue Processing

Process state (3, 1, CAT_TURN) = CAT_WIN:

  • Previous states (Cat just moved to 1):
    • Could have been (3, 0, MOUSE_TURN) → Invalid (Cat can't be at 0)
    • Could have been (3, 2, MOUSE_TURN) → Cat was at 2, moved to 1
    • Could have been (3, 3, MOUSE_TURN) → Already CAT_WIN
  • For (3, 2, MOUSE_TURN): Current is CAT_WIN, previous turn was Mouse's
    • Decrement degree[3][2][MOUSE_TURN] by 1
    • If degree reaches 0, all Mouse's moves lead to Cat winning

Step 5: Trace Back to Initial State

Continue this process until we determine ans[1][2][MOUSE_TURN].

In this example, from the initial state (1, 2, MOUSE_TURN):

  • Mouse can move to node 0 (hole) → MOUSE_WIN
  • Since Mouse has at least one winning move, the initial state is MOUSE_WIN

The algorithm returns 1, indicating the Mouse wins with optimal play.

Solution Implementation

1from collections import deque
2from typing import List
3
4# Game constants
5HOLE, MOUSE_START, CAT_START = 0, 1, 2
6MOUSE_TURN, CAT_TURN = 0, 1
7MOUSE_WIN, CAT_WIN, TIE = 1, 2, 0
8
9
10class Solution:
11    def catMouseGame(self, graph: List[List[int]]) -> int:
12        """
13        Determines the outcome of the cat and mouse game.
14      
15        Args:
16            graph: Adjacency list representation of the game board
17          
18        Returns:
19            0 if tie, 1 if mouse wins, 2 if cat wins
20        """
21      
22        def get_previous_states(current_state: tuple) -> List[tuple]:
23            """
24            Get all possible previous states that could lead to current state.
25          
26            Args:
27                current_state: (mouse_pos, cat_pos, turn)
28              
29            Returns:
30                List of previous states (mouse_pos, cat_pos, turn)
31            """
32            mouse_pos, cat_pos, turn = current_state
33            previous_turn = turn ^ 1  # Toggle turn using XOR
34            previous_states = []
35          
36            if previous_turn == CAT_TURN:
37                # If it was cat's turn, cat could have moved from any adjacent position
38                for previous_cat_pos in graph[cat_pos]:
39                    if previous_cat_pos != HOLE:  # Cat cannot be at hole
40                        previous_states.append((mouse_pos, previous_cat_pos, previous_turn))
41            else:
42                # If it was mouse's turn, mouse could have moved from any adjacent position
43                for previous_mouse_pos in graph[mouse_pos]:
44                    previous_states.append((previous_mouse_pos, cat_pos, previous_turn))
45          
46            return previous_states
47      
48        n = len(graph)
49      
50        # Initialize result array: result[mouse][cat][turn] = game outcome
51        result = [[[0, 0] for _ in range(n)] for _ in range(n)]
52      
53        # Initialize degree array: tracks number of possible moves from each state
54        degree = [[[0, 0] for _ in range(n)] for _ in range(n)]
55      
56        # Calculate degrees for each state
57        for mouse_pos in range(n):
58            for cat_pos in range(1, n):  # Cat cannot be at position 0 (hole)
59                degree[mouse_pos][cat_pos][MOUSE_TURN] = len(graph[mouse_pos])
60                degree[mouse_pos][cat_pos][CAT_TURN] = len(graph[cat_pos])
61          
62            # Adjust cat's degree since it cannot move to hole
63            for adjacent_to_hole in graph[HOLE]:
64                degree[mouse_pos][adjacent_to_hole][CAT_TURN] -= 1
65      
66        # BFS queue for processing states
67        queue = deque()
68      
69        # Initialize known winning states: mouse at hole
70        for cat_pos in range(1, n):
71            result[0][cat_pos][MOUSE_TURN] = MOUSE_WIN
72            result[0][cat_pos][CAT_TURN] = MOUSE_WIN
73            queue.append((0, cat_pos, MOUSE_TURN))
74            queue.append((0, cat_pos, CAT_TURN))
75      
76        # Initialize known winning states: cat catches mouse
77        for pos in range(1, n):
78            result[pos][pos][MOUSE_TURN] = CAT_WIN
79            result[pos][pos][CAT_TURN] = CAT_WIN
80            queue.append((pos, pos, MOUSE_TURN))
81            queue.append((pos, pos, CAT_TURN))
82      
83        # Process states using BFS
84        while queue:
85            current_state = queue.popleft()
86            current_mouse, current_cat, current_turn = current_state
87            current_result = result[current_mouse][current_cat][current_turn]
88          
89            # Check all states that could lead to current state
90            for previous_state in get_previous_states(current_state):
91                prev_mouse, prev_cat, prev_turn = previous_state
92              
93                # Skip if this previous state already has a determined outcome
94                if result[prev_mouse][prev_cat][prev_turn] != TIE:
95                    continue
96              
97                # Check if previous player can force a win
98                is_winning_move = (
99                    (current_result == MOUSE_WIN and prev_turn == MOUSE_TURN) or
100                    (current_result == CAT_WIN and prev_turn == CAT_TURN)
101                )
102              
103                if is_winning_move:
104                    # Previous player found a winning move
105                    result[prev_mouse][prev_cat][prev_turn] = current_result
106                    queue.append(previous_state)
107                else:
108                    # Decrease the degree (number of unexplored moves)
109                    degree[prev_mouse][prev_cat][prev_turn] -= 1
110                  
111                    # If all moves lead to loss, previous player loses
112                    if degree[prev_mouse][prev_cat][prev_turn] == 0:
113                        result[prev_mouse][prev_cat][prev_turn] = current_result
114                        queue.append(previous_state)
115      
116        # Return the result for initial state
117        return result[MOUSE_START][CAT_START][MOUSE_TURN]
118
1class Solution {
2    // Graph dimensions and structure
3    private int numberOfNodes;
4    private int[][] adjacencyGraph;
5  
6    // Game state results: [mousePosition][catPosition][turn]
7    private int[][][] gameResults;
8  
9    // Degree tracking for minimax algorithm: [mousePosition][catPosition][turn]
10    private int[][][] stateDegrees;
11
12    // Position constants
13    private static final int HOLE = 0;
14    private static final int MOUSE_START = 1;
15    private static final int CAT_START = 2;
16  
17    // Turn constants
18    private static final int MOUSE_TURN = 0;
19    private static final int CAT_TURN = 1;
20  
21    // Game outcome constants
22    private static final int TIE = 0;
23    private static final int MOUSE_WIN = 1;
24    private static final int CAT_WIN = 2;
25
26    public int catMouseGame(int[][] graph) {
27        // Initialize game parameters
28        numberOfNodes = graph.length;
29        adjacencyGraph = graph;
30        gameResults = new int[numberOfNodes][numberOfNodes][2];
31        stateDegrees = new int[numberOfNodes][numberOfNodes][2];
32      
33        // Initialize degrees for each state
34        // Degree represents the number of possible moves from each state
35        for (int mousePos = 0; mousePos < numberOfNodes; ++mousePos) {
36            for (int catPos = 1; catPos < numberOfNodes; ++catPos) {
37                stateDegrees[mousePos][catPos][MOUSE_TURN] = adjacencyGraph[mousePos].length;
38                stateDegrees[mousePos][catPos][CAT_TURN] = adjacencyGraph[catPos].length;
39            }
40        }
41      
42        // Cat cannot move to hole (position 0), so reduce cat's degree accordingly
43        for (int mousePos = 0; mousePos < numberOfNodes; ++mousePos) {
44            for (int neighbor : adjacencyGraph[HOLE]) {
45                --stateDegrees[mousePos][neighbor][CAT_TURN];
46            }
47        }
48      
49        // Queue for BFS traversal of game states
50        Deque<int[]> stateQueue = new ArrayDeque<>();
51      
52        // Initialize winning states for mouse (mouse reaches hole)
53        for (int catPos = 1; catPos < numberOfNodes; ++catPos) {
54            gameResults[HOLE][catPos][MOUSE_TURN] = MOUSE_WIN;
55            gameResults[HOLE][catPos][CAT_TURN] = MOUSE_WIN;
56            stateQueue.offer(new int[] {HOLE, catPos, MOUSE_TURN});
57            stateQueue.offer(new int[] {HOLE, catPos, CAT_TURN});
58        }
59      
60        // Initialize winning states for cat (cat catches mouse)
61        for (int position = 1; position < numberOfNodes; ++position) {
62            gameResults[position][position][MOUSE_TURN] = CAT_WIN;
63            gameResults[position][position][CAT_TURN] = CAT_WIN;
64            stateQueue.offer(new int[] {position, position, MOUSE_TURN});
65            stateQueue.offer(new int[] {position, position, CAT_TURN});
66        }
67      
68        // Perform backward induction using BFS
69        while (!stateQueue.isEmpty()) {
70            int[] currentState = stateQueue.poll();
71            int currentResult = gameResults[currentState[0]][currentState[1]][currentState[2]];
72          
73            // Get all states that can lead to current state
74            List<int[]> previousStates = getPrevStates(currentState);
75          
76            for (int[] prevState : previousStates) {
77                int prevMousePos = prevState[0];
78                int prevCatPos = prevState[1];
79                int prevTurn = prevState[2];
80              
81                // Only process undecided states
82                if (gameResults[prevMousePos][prevCatPos][prevTurn] == TIE) {
83                    // Check if previous player can win by moving to current state
84                    boolean canWin = (currentResult == MOUSE_WIN && prevTurn == MOUSE_TURN) || 
85                                    (currentResult == CAT_WIN && prevTurn == CAT_TURN);
86                  
87                    if (canWin) {
88                        // Previous player wins immediately
89                        gameResults[prevMousePos][prevCatPos][prevTurn] = currentResult;
90                        stateQueue.offer(prevState);
91                    } else {
92                        // Decrease degree; if all moves lead to loss, mark as loss
93                        if (--stateDegrees[prevMousePos][prevCatPos][prevTurn] == 0) {
94                            gameResults[prevMousePos][prevCatPos][prevTurn] = currentResult;
95                            stateQueue.offer(prevState);
96                        }
97                    }
98                }
99            }
100        }
101      
102        // Return the result of initial game state
103        return gameResults[MOUSE_START][CAT_START][MOUSE_TURN];
104    }
105
106    /**
107     * Get all possible previous states that can lead to the given state
108     * @param state Current state [mousePosition, catPosition, turn]
109     * @return List of previous states
110     */
111    private List<int[]> getPrevStates(int[] state) {
112        List<int[]> previousStates = new ArrayList<>();
113        int mousePos = state[0];
114        int catPos = state[1];
115        int currentTurn = state[2];
116      
117        // Previous turn is opposite of current turn
118        int previousTurn = currentTurn ^ 1;
119      
120        if (previousTurn == CAT_TURN) {
121            // If it was cat's turn, cat moved to current position
122            for (int prevCatPos : adjacencyGraph[catPos]) {
123                // Cat cannot move to hole
124                if (prevCatPos != HOLE) {
125                    previousStates.add(new int[] {mousePos, prevCatPos, previousTurn});
126                }
127            }
128        } else {
129            // If it was mouse's turn, mouse moved to current position
130            for (int prevMousePos : adjacencyGraph[mousePos]) {
131                previousStates.add(new int[] {prevMousePos, catPos, previousTurn});
132            }
133        }
134      
135        return previousStates;
136    }
137}
138
1class Solution {
2public:
3    int catMouseGame(vector<vector<int>>& graph) {
4        // Constants for better readability
5        const int HOLE = 0;
6        const int MOUSE_START = 1;
7        const int CAT_START = 2;
8        const int MOUSE_TURN = 0;
9        const int CAT_TURN = 1;
10        const int MOUSE_WIN = 1;
11        const int CAT_WIN = 2;
12        const int TIE = 0;
13      
14        int n = graph.size();
15      
16        // dp[mousePos][catPos][turn] = game result
17        // turn: 0 = mouse's turn, 1 = cat's turn
18        int dp[n][n][2];
19      
20        // degree[mousePos][catPos][turn] = number of possible moves from this state
21        // Used for counting losing states in minimax algorithm
22        int degree[n][n][2];
23      
24        // Initialize all states as TIE (unknown result)
25        memset(dp, 0, sizeof(dp));
26        memset(degree, 0, sizeof(degree));
27      
28        // Calculate the degree (number of possible moves) for each state
29        for (int mousePos = 0; mousePos < n; ++mousePos) {
30            for (int catPos = 1; catPos < n; ++catPos) {
31                // Mouse can move to any adjacent node
32                degree[mousePos][catPos][MOUSE_TURN] = graph[mousePos].size();
33                // Cat can move to any adjacent node except the hole
34                degree[mousePos][catPos][CAT_TURN] = graph[catPos].size();
35            }
36            // Cat cannot move to the hole, so reduce the degree for positions adjacent to hole
37            for (int adjacentToHole : graph[HOLE]) {
38                --degree[mousePos][adjacentToHole][CAT_TURN];
39            }
40        }
41      
42        // Lambda function to get all previous states that can lead to current state
43        auto getPreviousStates = [&](int mousePos, int catPos, int turn) {
44            int previousTurn = turn ^ 1;  // Toggle turn using XOR
45            vector<tuple<int, int, int>> previousStates;
46          
47            if (previousTurn == CAT_TURN) {
48                // If previous turn was cat's, cat could have come from any adjacent position
49                for (int prevCatPos : graph[catPos]) {
50                    if (prevCatPos != HOLE) {  // Cat cannot be at hole
51                        previousStates.emplace_back(mousePos, prevCatPos, previousTurn);
52                    }
53                }
54            } else {
55                // If previous turn was mouse's, mouse could have come from any adjacent position
56                for (int prevMousePos : graph[mousePos]) {
57                    previousStates.emplace_back(prevMousePos, catPos, previousTurn);
58                }
59            }
60            return previousStates;
61        };
62      
63        // BFS queue for propagating known results
64        queue<tuple<int, int, int>> bfsQueue;
65      
66        // Initialize winning states for mouse (mouse reaches hole)
67        for (int catPos = 1; catPos < n; ++catPos) {
68            dp[0][catPos][MOUSE_TURN] = MOUSE_WIN;
69            dp[0][catPos][CAT_TURN] = MOUSE_WIN;
70            bfsQueue.emplace(0, catPos, MOUSE_TURN);
71            bfsQueue.emplace(0, catPos, CAT_TURN);
72        }
73      
74        // Initialize winning states for cat (cat catches mouse)
75        for (int pos = 1; pos < n; ++pos) {
76            dp[pos][pos][MOUSE_TURN] = CAT_WIN;
77            dp[pos][pos][CAT_TURN] = CAT_WIN;
78            bfsQueue.emplace(pos, pos, MOUSE_TURN);
79            bfsQueue.emplace(pos, pos, CAT_TURN);
80        }
81      
82        // BFS to propagate results backwards using minimax logic
83        while (!bfsQueue.empty()) {
84            auto [currentMousePos, currentCatPos, currentTurn] = bfsQueue.front();
85            bfsQueue.pop();
86            int currentResult = dp[currentMousePos][currentCatPos][currentTurn];
87          
88            // Check all states that can lead to current state
89            for (auto [prevMousePos, prevCatPos, prevTurn] : getPreviousStates(currentMousePos, currentCatPos, currentTurn)) {
90                // Skip if result already determined
91                if (dp[prevMousePos][prevCatPos][prevTurn] != TIE) {
92                    continue;
93                }
94              
95                // Check if the player in previous turn can win
96                bool canWin = (currentResult == MOUSE_WIN && prevTurn == MOUSE_TURN) || 
97                             (currentResult == CAT_WIN && prevTurn == CAT_TURN);
98              
99                if (canWin) {
100                    // If player can win by moving to current state, mark as winning
101                    dp[prevMousePos][prevCatPos][prevTurn] = currentResult;
102                    bfsQueue.emplace(prevMousePos, prevCatPos, prevTurn);
103                } else {
104                    // If this move leads to a loss, decrease the degree
105                    // When degree reaches 0, all moves lead to loss, so player loses
106                    if (--degree[prevMousePos][prevCatPos][prevTurn] == 0) {
107                        dp[prevMousePos][prevCatPos][prevTurn] = currentResult;
108                        bfsQueue.emplace(prevMousePos, prevCatPos, prevTurn);
109                    }
110                }
111            }
112        }
113      
114        // Return the result for initial state
115        return dp[MOUSE_START][CAT_START][MOUSE_TURN];
116    }
117};
118
1/**
2 * Determines the winner of the Cat and Mouse game
3 * @param graph - Adjacency list representation of the game graph
4 * @returns 1 if mouse wins, 2 if cat wins, 0 if tie
5 */
6function catMouseGame(graph: number[][]): number {
7    // Game constants
8    const HOLE = 0;
9    const MOUSE_START = 1;
10    const CAT_START = 2;
11  
12    // Turn indicators
13    const MOUSE_TURN = 0;
14    const CAT_TURN = 1;
15  
16    // Game outcomes
17    const TIE = 0;
18    const MOUSE_WIN = 1;
19    const CAT_WIN = 2;
20
21    /**
22     * Gets all possible previous states that could lead to the current state
23     * @param state - Current game state [mousePosition, catPosition, turn]
24     * @returns Array of previous states
25     */
26    function getPreviousStates(state: [number, number, number]): [number, number, number][] {
27        const [mousePos, catPos, currentTurn] = state;
28        const previousTurn = currentTurn ^ 1; // XOR to flip turn
29        const previousStates: [number, number, number][] = [];
30
31        if (previousTurn === CAT_TURN) {
32            // If previous turn was cat's, iterate through all positions cat could have been
33            for (const previousCatPos of graph[catPos]) {
34                // Cat cannot enter the hole
35                if (previousCatPos !== HOLE) {
36                    previousStates.push([mousePos, previousCatPos, previousTurn]);
37                }
38            }
39        } else {
40            // If previous turn was mouse's, iterate through all positions mouse could have been
41            for (const previousMousePos of graph[mousePos]) {
42                previousStates.push([previousMousePos, catPos, previousTurn]);
43            }
44        }
45      
46        return previousStates;
47    }
48
49    const graphSize = graph.length;
50  
51    // Initialize result matrix: ans[mousePos][catPos][turn] = game outcome
52    const gameResults: number[][][] = Array.from({ length: graphSize }, () =>
53        Array.from({ length: graphSize }, () => [TIE, TIE])
54    );
55  
56    // Initialize degree matrix: tracks remaining moves for each state
57    const stateDegrees: number[][][] = Array.from({ length: graphSize }, () =>
58        Array.from({ length: graphSize }, () => [0, 0])
59    );
60
61    // Calculate degrees for each state
62    for (let mousePos = 0; mousePos < graphSize; mousePos++) {
63        for (let catPos = 1; catPos < graphSize; catPos++) {
64            // Mouse's degree is the number of adjacent nodes
65            stateDegrees[mousePos][catPos][MOUSE_TURN] = graph[mousePos].length;
66            // Cat's degree is the number of adjacent nodes
67            stateDegrees[mousePos][catPos][CAT_TURN] = graph[catPos].length;
68        }
69        // Adjust cat's degree by removing edges to hole (cat cannot enter hole)
70        for (const adjacentToHole of graph[HOLE]) {
71            stateDegrees[mousePos][adjacentToHole][CAT_TURN] -= 1;
72        }
73    }
74
75    // BFS queue for processing states
76    const stateQueue: [number, number, number][] = [];
77
78    // Initialize base cases: mouse at hole (mouse wins)
79    for (let catPos = 1; catPos < graphSize; catPos++) {
80        gameResults[0][catPos][MOUSE_TURN] = MOUSE_WIN;
81        gameResults[0][catPos][CAT_TURN] = MOUSE_WIN;
82        stateQueue.push([0, catPos, MOUSE_TURN]);
83        stateQueue.push([0, catPos, CAT_TURN]);
84    }
85  
86    // Initialize base cases: mouse and cat at same position (cat wins)
87    for (let position = 1; position < graphSize; position++) {
88        gameResults[position][position][MOUSE_TURN] = CAT_WIN;
89        gameResults[position][position][CAT_TURN] = CAT_WIN;
90        stateQueue.push([position, position, MOUSE_TURN]);
91        stateQueue.push([position, position, CAT_TURN]);
92    }
93
94    // BFS to determine outcomes for all states
95    while (stateQueue.length > 0) {
96        const currentState = stateQueue.shift()!;
97        const [mousePos, catPos, turn] = currentState;
98        const currentResult = gameResults[mousePos][catPos][turn];
99
100        // Process all states that could lead to current state
101        for (const previousState of getPreviousStates(currentState)) {
102            const [prevMousePos, prevCatPos, prevTurn] = previousState;
103          
104            // Skip if this previous state already has a determined outcome
105            if (gameResults[prevMousePos][prevCatPos][prevTurn] !== TIE) {
106                continue;
107            }
108
109            // Check if the player in the previous turn can force a win
110            const canForceWin = 
111                (currentResult === MOUSE_WIN && prevTurn === MOUSE_TURN) ||
112                (currentResult === CAT_WIN && prevTurn === CAT_TURN);
113          
114            if (canForceWin) {
115                // Player can force a win from this previous state
116                gameResults[prevMousePos][prevCatPos][prevTurn] = currentResult;
117                stateQueue.push(previousState);
118            } else {
119                // Decrease degree (one less option that doesn't lead to win)
120                stateDegrees[prevMousePos][prevCatPos][prevTurn] -= 1;
121              
122                // If all moves lead to opponent winning, this player loses
123                if (stateDegrees[prevMousePos][prevCatPos][prevTurn] === 0) {
124                    gameResults[prevMousePos][prevCatPos][prevTurn] = currentResult;
125                    stateQueue.push(previousState);
126                }
127            }
128        }
129    }
130
131    // Return the result for the initial game state
132    return gameResults[MOUSE_START][CAT_START][MOUSE_TURN];
133}
134

Time and Space Complexity

Time Complexity: O(n^3)

The algorithm uses BFS to traverse game states. Each state is represented by (mouse_position, cat_position, turn), giving us n × n × 2 possible states (mouse can be at any of n positions, cat can be at any of n positions, and there are 2 possible turns).

For each state processed in the queue, we examine its previous states through get_prev_states():

  • When looking at previous cat turns, we iterate through all neighbors of the current cat position (at most n-1 neighbors)
  • When looking at previous mouse turns, we iterate through all neighbors of the current mouse position (at most n neighbors)

Since each state can be added to the queue at most once (when its outcome is determined), and for each state we do O(n) work to process previous states, the total time complexity is O(n^2 × 2 × n) = O(n^3).

Space Complexity: O(n^2)

The algorithm uses several 3D arrays:

  • ans[n][n][2]: stores the outcome for each state, requiring O(n^2) space
  • degree[n][n][2]: stores the out-degree for each state, requiring O(n^2) space
  • The queue can contain at most O(n^2) states since each state is added at most once

The total space complexity is O(n^2).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Cat's Movement Restriction at Node 0

The Pitfall: A common mistake is forgetting to properly handle the restriction that the Cat cannot move to node 0 (the hole). This affects two critical parts of the algorithm:

  1. Degree Calculation: When calculating the number of possible moves for the Cat, developers often use degree[m][c][CAT_TURN] = len(graph[c]) without accounting for the fact that if node 0 is adjacent to the Cat's position, it should not be counted as a valid move.

  2. Previous State Generation: When generating previous states where the Cat could have come from, developers might include node 0 as a possible previous position for the Cat.

Incorrect Implementation Example:

# WRONG: Not adjusting degree for cat's restriction
for mouse_pos in range(n):
    for cat_pos in range(1, n):
        degree[mouse_pos][cat_pos][CAT_TURN] = len(graph[cat_pos])  # Includes node 0!

# WRONG: Not filtering out node 0 in previous states
if previous_turn == CAT_TURN:
    for previous_cat_pos in graph[cat_pos]:
        # Missing check for HOLE!
        previous_states.append((mouse_pos, previous_cat_pos, previous_turn))

Correct Solution:

# Correctly adjust degree by subtracting 1 if node 0 is adjacent
for adjacent_to_hole in graph[HOLE]:
    degree[mouse_pos][adjacent_to_hole][CAT_TURN] -= 1

# Correctly filter out node 0 when generating previous cat positions
if previous_turn == CAT_TURN:
    for previous_cat_pos in graph[cat_pos]:
        if previous_cat_pos != HOLE:  # Essential check!
            previous_states.append((mouse_pos, previous_cat_pos, previous_turn))

2. Misunderstanding the Win Condition Logic in BFS

The Pitfall: Another common error is incorrectly determining when a previous state should inherit the current state's outcome. The logic is subtle:

  • If the current state is a win for a player AND it was that player's turn in the previous state, then the previous state is also a win for that player (they can choose to move to this winning position).
  • Otherwise, we decrement the degree, and only when ALL moves lead to losses (degree becomes 0) do we mark it as a loss for that player.

Incorrect Implementation Example:

# WRONG: Oversimplified win condition check
if current_result == MOUSE_WIN:
    result[prev_mouse][prev_cat][prev_turn] = MOUSE_WIN
    queue.append(previous_state)

Correct Solution:

# Check if the player whose turn it was can force a win
is_winning_move = (
    (current_result == MOUSE_WIN and prev_turn == MOUSE_TURN) or
    (current_result == CAT_WIN and prev_turn == CAT_TURN)
)

if is_winning_move:
    result[prev_mouse][prev_cat][prev_turn] = current_result
    queue.append(previous_state)
else:
    degree[prev_mouse][prev_cat][prev_turn] -= 1
    if degree[prev_mouse][prev_cat][prev_turn] == 0:
        # All moves lead to loss for the player whose turn it was
        result[prev_mouse][prev_cat][prev_turn] = current_result
        queue.append(previous_state)

3. Initializing States Where Cat is at Node 0

The Pitfall: Since the Cat can never be at node 0, some developers might accidentally initialize states with cat_pos = 0 or iterate through all positions including 0 for the Cat.

Incorrect Implementation Example:

# WRONG: Including cat_pos = 0
for mouse_pos in range(n):
    for cat_pos in range(n):  # Should start from 1!
        degree[mouse_pos][cat_pos][MOUSE_TURN] = len(graph[mouse_pos])

Correct Solution:

# Correctly skip cat_pos = 0
for mouse_pos in range(n):
    for cat_pos in range(1, n):  # Start from 1, not 0
        degree[mouse_pos][cat_pos][MOUSE_TURN] = len(graph[mouse_pos])
        degree[mouse_pos][cat_pos][CAT_TURN] = len(graph[cat_pos])

These pitfalls can lead to incorrect game outcomes because they either allow invalid moves or incorrectly propagate win/loss states through the game tree.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Recommended Readings

Graph Fundamentals

https assets algo monster cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could be disconnected A tree

Topological Sort Introduction

Topological Sort Topological Order Prereq Breadth First Search Review problems graph_bfs Directed Graph Before we get started on topological order let's talk about directed graphs first A graph is directed when its edges have directions these edges are also called arcs Suppose that v w are vertices in a directed

Memoization

Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More