Cat and Mouse

Hard

#0867Time: O(N^5) in the worst case. The number of states is O(N^2). The loop can run up to O(N^2) times (the number of states that can change color). Inside the loop, we iterate over all O(N^2) states, and for each, we check its neighbors, which takes O(N) time. This gives a total complexity of O(N^2 * N^2 * N) = O(N^5).Space: O(N^2), where N is the number of nodes. This is for the `color` table which stores the outcome for each pair of mouse/cat positions and turn.

Patterns

Math Dynamic Programming Memoization Game Theory

Algorithms

Topological Sort

Data structures

Graph

Prompt

A game on an undirected graph is played by two players, Mouse and Cat, who alternate turns.

The graph is given as follows: graph[a] is a list of all nodes b such that ab is an edge of the graph.

The mouse starts at node 1 and goes first, the cat starts at node 2 and goes second, and there is a hole at node 0.

During each player's turn, they must travel along one edge of the graph that meets where they are. For example, if the Mouse is at node 1, it must travel to any node in graph[1].

Additionally, it is not allowed for the Cat to travel to the Hole (node 0).

Then, the game can end in three ways:

If ever the Cat occupies the same node as the Mouse, the Cat wins.
If ever the Mouse reaches the Hole, the Mouse wins.
If ever a position is repeated (i.e., the players are in the same position as a previous turn, and it is the same player's turn to move), the game is a draw.

Given a graph, and assuming both players play optimally, return

1 if the mouse wins the game,
2 if the cat wins the game, or
0 if the game is a draw.

Example 1:

Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0

Example 2:

Input: graph = [[1,3],[0],[3],[0,2]]
Output: 1

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a technique called value iteration. It's a form of dynamic programming where we repeatedly update the value (outcome) of each game state based on the values of the states it can transition to. We start by identifying the definite win/loss states (terminal states) and consider all other states as potential draws. Then, we loop through all states, refining their outcomes based on whether a player can force a win or is forced into a loss. This process continues until the outcomes for all states stabilize.

Algorithm

Define the game state by (mouse_position, cat_position, turn).
Use a 3D array, color[N][N][2], to store the outcome for each state (0: DRAW, 1: MOUSE_WIN, 2: CAT_WIN).
Initialize the color array. All non-terminal states are initially considered DRAW (0). Terminal states are set as wins for the appropriate player:
- If Mouse is at the hole (node 0), it's a MOUSE_WIN.
- If Cat and Mouse are at the same node, it's a CAT_WIN.
Repeatedly iterate through all undecided states until no state's outcome changes in a full pass (i.e., the outcomes have converged).
In each iteration, for every state, re-evaluate its outcome based on the current outcomes of its successor states:
- Mouse's Turn: The state is a MOUSE_WIN if the mouse can move to any state that is a MOUSE_WIN. It's a CAT_WIN if all possible moves lead to CAT_WIN states. Otherwise, it remains a DRAW.
- Cat's Turn: The state is a CAT_WIN if the cat can move to any state that is a CAT_WIN. It's a MOUSE_WIN if all possible moves lead to MOUSE_WIN states. Otherwise, it remains a DRAW.
Once the color table stabilizes, the outcome for the starting state (mouse=1, cat=2, turn=MOUSE) is the answer.

Walkthrough

The core idea is to model the game as a state graph and iteratively determine the outcome of each state. A state is defined by (mouse_position, cat_position, turn). We maintain a 3D array, color, to store the outcome for each state: 0 for Draw, 1 for Mouse Win, and 2 for Cat Win.

Initially, we set the outcomes for the terminal states: any state where the mouse is at node 0 is a win for the mouse, and any state where the cat and mouse are on the same node is a win for the cat. All other states are initialized to Draw.

The algorithm then enters a loop. In each pass, it attempts to update the color of each undecided state based on the colors of its successor states. For a player to win from a state, they must have at least one move to a state that results in a win for them. For a player to lose, all of their possible moves must lead to states where the opponent wins. If neither of these conditions is met, the state's outcome remains a draw for that iteration.

This iterative process continues until a full pass over all states results in no changes to the color array. At this point, the outcomes have converged, and we can return the outcome for the initial state (mouse=1, cat=2, turn=MOUSE).

1class Solution {2    private static final int DRAW = 0;3    private static final int MOUSE_WIN = 1;4    private static final int CAT_WIN = 2;5 6    public int catMouseGame(int[][] graph) {7        int n = graph.length;8        int[][][] color = new int[n][n][2];9 10        // Initialize terminal states11        for (int i = 0; i < n; i++) {12            for (int t = 0; t < 2; t++) {13                if (i > 0) {14                    color[0][i][t] = MOUSE_WIN; // Mouse at hole15                    color[i][i][t] = CAT_WIN;   // Cat catches mouse16                }17            }18        }19 20        while (true) {21            boolean changed = false;22            // Iterate over all non-terminal states23            for (int m = 1; m < n; m++) {24                for (int c = 1; c < n; c++) {25                    if (m == c) continue;26                    for (int t = 0; t < 2; t++) {27                        if (color[m][c][t] != DRAW) continue;28 29                        if (t == 0) { // Mouse's turn30                            boolean canMouseWin = false;31                            boolean allCatWin = true;32                            for (int next_m : graph[m]) {33                                if (color[next_m][c][1] == MOUSE_WIN) {34                                    canMouseWin = true;35                                    break;36                                }37                                if (color[next_m][c][1] != CAT_WIN) {38                                    allCatWin = false;39                                }40                            }41                            if (canMouseWin) {42                                color[m][c][0] = MOUSE_WIN;43                                changed = true;44                            } else if (allCatWin) {45                                color[m][c][0] = CAT_WIN;46                                changed = true;47                            }48                        } else { // Cat's turn49                            boolean canCatWin = false;50                            boolean allMouseWin = true;51                            for (int next_c : graph[c]) {52                                if (next_c == 0) continue;53                                if (color[m][next_c][0] == CAT_WIN) {54                                    canCatWin = true;55                                    break;56                                }57                                if (color[m][next_c][0] != MOUSE_WIN) {58                                    allMouseWin = false;59                                }60                            }61                            if (canCatWin) {62                                color[m][c][1] = CAT_WIN;63                                changed = true;64                            } else if (allMouseWin) {65                                color[m][c][1] = MOUSE_WIN;66                                changed = true;67                            }68                        }69                    }70                }71            }72            if (!changed) {73                break;74            }75        }76 77        return color[1][2][0];78    }79}

Complexity

Time

O(N^5) in the worst case. The number of states is O(N^2). The loop can run up to O(N^2) times (the number of states that can change color). Inside the loop, we iterate over all O(N^2) states, and for each, we check its neighbors, which takes O(N) time. This gives a total complexity of O(N^2 * N^2 * N) = O(N^5).

Space

O(N^2), where N is the number of nodes. This is for the `color` table which stores the outcome for each pair of mouse/cat positions and turn.

Trade-offs

Pros

Conceptually straightforward, as it directly models the iterative nature of determining game outcomes.
Avoids the complexity of managing recursion stacks and explicit cycle detection.

Cons

Significantly less efficient than the BFS-based approach due to repeated re-evaluation of states.
The number of iterations required for convergence can be large, proportional to the number of states, leading to a high overall time complexity.

This is the most efficient approach, treating the problem as a search on the game's state graph. It works backward from the terminal states (where the game outcome is known) and uses a Breadth-First Search (BFS) to propagate these outcomes to other states. This method is often called a "coloring" algorithm.

We start by "coloring" the terminal states as either a win for the Mouse or a win for the Cat. These states are added to a queue. Then, we process the queue, and for each state, we examine its "parent" states (the states that could have led to it). If a player can move from a parent state to a state that is a win for them, we color that parent state as a win. If all of a player's moves from a parent state lead to losses, we color that parent state as a loss. States that are never colored are part of a cycle where neither player can force a win, and are thus draws.

Algorithm

Define the game state as (mouse_pos, cat_pos, turn).
Initialize a color[N][N][2] array to 0 (DRAW) to store the final outcome of each state.
Initialize a degree[N][N][2] array to store the number of available moves for the current player from each state.
Create a queue for Breadth-First Search (BFS) and add all terminal states (where Mouse is at hole, or Cat catches Mouse).
Set the color for these terminal states to MOUSE_WIN (1) or CAT_WIN (2) accordingly.
While the queue is not empty, dequeue a state S = (m, c, t) with a determined outcome.
For each "parent" state P that can transition to S:
- If P is already colored, skip it.
- Winning Propagation: If the player at P wins by moving to S, color P with the winning outcome and enqueue P.
- Losing Propagation: If moving to S is a losing move for the player at P, decrement the degree of P. If degree[P] becomes 0, it means all moves from P are losing moves. Color P as a loss and enqueue P.
After the BFS completes, any state still colored 0 is a draw. Return color[1][2][0].

Walkthrough

This optimal approach uses a bottom-up dynamic programming strategy with a Breadth-First Search (BFS). We determine the outcome of states whose results are certain and propagate this information to their predecessor states.

State Representation: The state is (mouse_pos, cat_pos, turn), where turn=0 for Mouse and turn=1 for Cat.
Data Structures:
- color[n][n][2]: Stores the outcome (0: Draw, 1: Mouse Win, 2: Cat Win).
- degree[n][n][2]: Stores the number of outgoing moves from a state that lead to an undecided (Draw) state. This is key to determining forced losses.
- Queue<int[]>: A queue to manage states whose outcomes have been determined, for the BFS process.
Initialization:
- We first populate the color array and the queue with all terminal states. These are states where the mouse is at the hole (node 0) or the cat is at the same position as the mouse.
- We initialize the degree for each state. For a mouse's turn state (m, c, 0), the degree is the number of neighbors of m. For a cat's turn state (m, c, 1), it's the number of neighbors of c (excluding the hole).
BFS Propagation:
- We dequeue a state (m, c, t) whose outcome outcome is known.
- We then find all parent states P that could transition into (m, c, t). A parent state P has the opposite turn 1-t.
- For each uncolored parent state P:
  - If the player at P can move to (m, c, t) and outcome is a win for them, we color P as a win and enqueue it. This is because an optimal player will always choose a winning move.
  - If outcome is a loss for the player at P, we decrement P's degree. If the degree becomes zero, it means all possible moves from P lead to a loss. Thus, P itself is a losing state. We color P as a loss and enqueue it.
Result: After the BFS completes, any state remaining with color = 0 is a draw. The final answer is the color of the initial state (1, 2, 0).

1class Solution {2    private static final int DRAW = 0;3    private static final int MOUSE_WIN = 1;4    private static final int CAT_WIN = 2;5 6    public int catMouseGame(int[][] graph) {7        int n = graph.length;8        // state: (mouse_pos, cat_pos, turn), turn 0 for mouse, 1 for cat9        int[][][] color = new int[n][n][2];10        // out-degree for each state11        int[][][] degree = new int[n][n][2];12 13        // Initialize degrees14        for (int m = 0; m < n; m++) {15            for (int c = 0; c < n; c++) {16                degree[m][c][0] = graph[m].length;17                degree[m][c][1] = graph[c].length;18                for (int neighbor : graph[c]) {19                    if (neighbor == 0) {20                        degree[m][c][1]--;21                        break;22                    }23                }24            }25        }26 27        Queue<int[]> queue = new LinkedList<>();28 29        // Initialize terminal states30        for (int i = 1; i < n; i++) {31            color[0][i][0] = MOUSE_WIN;32            color[0][i][1] = MOUSE_WIN;33            queue.offer(new int[]{0, i, 0});34            queue.offer(new int[]{0, i, 1});35 36            color[i][i][0] = CAT_WIN;37            color[i][i][1] = CAT_WIN;38            queue.offer(new int[]{i, i, 0});39            queue.offer(new int[]{i, i, 1});40        }41 42        while (!queue.isEmpty()) {43            int[] state = queue.poll();44            int m = state[0], c = state[1], t = state[2];45            int outcome = color[m][c][t];46 47            int prev_turn = 1 - t;48            if (prev_turn == 0) { // Parent state was Mouse's turn49                for (int prev_m : graph[m]) {50                    if (color[prev_m][c][0] == DRAW) {51                        if (outcome == MOUSE_WIN) { // Mouse found a winning move52                            color[prev_m][c][0] = MOUSE_WIN;53                            queue.offer(new int[]{prev_m, c, 0});54                        } else { // outcome == CAT_WIN, a losing move for Mouse55                            degree[prev_m][c][0]--;56                            if (degree[prev_m][c][0] == 0) { // All moves are losing57                                color[prev_m][c][0] = CAT_WIN;58                                queue.offer(new int[]{prev_m, c, 0});59                            }60                        }61                    }62                }63            } else { // Parent state was Cat's turn64                for (int prev_c : graph[c]) {65                    if (prev_c == 0) continue;66                    if (color[m][prev_c][1] == DRAW) {67                        if (outcome == CAT_WIN) { // Cat found a winning move68                            color[m][prev_c][1] = CAT_WIN;69                            queue.offer(new int[]{m, prev_c, 1});70                        } else { // outcome == MOUSE_WIN, a losing move for Cat71                            degree[m][prev_c][1]--;72                            if (degree[m][prev_c][1] == 0) { // All moves are losing73                                color[m][prev_c][1] = MOUSE_WIN;74                                queue.offer(new int[]{m, prev_c, 1});75                            }76                        }77                    }78                }79            }80        }81 82        return color[1][2][0];83    }84}

Complexity

Time

O(N^3). The number of states is O(N^2). Each state is enqueued and processed exactly once. When processing a state, we iterate through its parent states. The number of parents is bounded by the maximum degree of a node in the graph, D (where D < N). Thus, the total time complexity is O(N^2 * D), which simplifies to O(N^3).

Space

O(N^2), where N is the number of nodes. This space is used for the `color` table, the `degree` table, and the BFS queue.

Trade-offs

Pros

Highly efficient, solving the problem in a single pass over the state graph.
Guaranteed to find the optimal strategy for both players and correctly identify draws.
It is the standard and most effective algorithm for solving such impartial games with draws.

Cons

The logic for propagating results backward from child to parent states can be complex to implement correctly.
Requires careful management of the degree array to correctly identify when a player is forced into a loss.

Solutions

Solution

1using System ; using System.Collections.Generic ; public class Solution { private int n ; private int [][] g ; private int [,,] ans ; private int [,,] degree ; private const int HOLE = 0 , MOUSE_START = 1 , CAT_START = 2 ; private const int MOUSE_TURN = 0 , CAT_TURN = 1 ; private const int MOUSE_WIN = 1 , CAT_WIN = 2 , TIE = 0 ; public int CatMouseGame ( int [][] graph ) { n = graph . Length ; g = graph ; ans = new int [ n , n , 2 ]; degree = new int [ n , n , 2 ]; for ( int i = 0 ; i < n ; i ++) { for ( int j = 1 ; j < n ; j ++) { degree [ i , j , MOUSE_TURN ] = g [ i ]. Length ; degree [ i , j , CAT_TURN ] = g [ j ]. Length ; } } for ( int i = 0 ; i < n ; i ++) { foreach ( int j in g [ HOLE ]) { degree [ i , j , CAT_TURN ]--; } } Queue < int [ ]> q = new Queue < int [ ]> (); for ( int j = 1 ; j < n ; j ++) { ans [ 0 , j , MOUSE_TURN ] = MOUSE_WIN ; ans [ 0 , j , CAT_TURN ] = MOUSE_WIN ; q . Enqueue ( new int [] { 0 , j , MOUSE_TURN }); q . Enqueue ( new int [] { 0 , j , CAT_TURN }); } for ( int i = 1 ; i < n ; i ++) { ans [ i , i , MOUSE_TURN ] = CAT_WIN ; ans [ i , i , CAT_TURN ] = CAT_WIN ; q . Enqueue ( new int [] { i , i , MOUSE_TURN }); q . Enqueue ( new int [] { i , i , CAT_TURN }); } while ( q . Count > 0 ) { int [] state = q . Dequeue (); int t = ans [ state [ 0 ], state [ 1 ], state [ 2 ]]; List < int [ ]> prevStates = GetPrevStates ( state ); foreach ( var prevState in prevStates ) { int pm = prevState [ 0 ], pc = prevState [ 1 ], pt = prevState [ 2 ]; if ( ans [ pm , pc , pt ] == TIE ) { bool win = ( t == MOUSE_WIN && pt == MOUSE_TURN ) || ( t == CAT_WIN && pt == CAT_TURN ); if ( win ) { ans [ pm , pc , pt ] = t ; q . Enqueue ( prevState ); } else { if (-- degree [ pm , pc , pt ] == 0 ) { ans [ pm , pc , pt ] = t ; q . Enqueue ( prevState ); } } } } } return ans [ MOUSE_START , CAT_START , MOUSE_TURN ]; } private List < int [ ]> GetPrevStates ( int [] state ) { List < int [ ]> pre = new List < int [ ]> (); int m = state [ 0 ], c = state [ 1 ], t = state [ 2 ]; int pt = t ^ 1 ; if ( pt == CAT_TURN ) { foreach ( int pc in g [ c ]) { if ( pc != HOLE ) { pre . Add ( new int [] { m , pc , pt }); } } } else { foreach ( int pm in g [ m ]) { pre . Add ( new int [] { pm , c , pt }); } } return pre ; } }

1class Solution {2private3  int n;4private5  int[][] g;6private7  int[][][] res;8private9  int[][][] degree;10private11  static final int HOLE = 0, MOUSE_START = 1, CAT_START = 2;12private13  static final int MOUSE_TURN = 0, CAT_TURN = 1;14private15  static final int MOUSE_WIN = 1, CAT_WIN = 2, TIE = 0;16public17  int catMouseGame(int[][] graph) {18    n = graph.length;19    g = graph;20    res = new int[n][n][2];21    degree = new int[n][n][2];22    for (int i = 0; i < n; ++i) {23      for (int j = 1; j < n; ++j) {24        degree[i][j][MOUSE_TURN] = g[i].length;25        degree[i][j][CAT_TURN] = g[j].length;26      }27    }28    for (int i = 0; i < n; ++i) {29      for (int j : g[HOLE]) {30        --degree[i][j][CAT_TURN];31      }32    }33    Deque<int[]> q = new ArrayDeque<>();34    for (int j = 1; j < n; ++j) {35      res[0][j][MOUSE_TURN] = MOUSE_WIN;36      res[0][j][CAT_TURN] = MOUSE_WIN;37      q.offer(new int[]{0, j, MOUSE_TURN});38      q.offer(new int[]{0, j, CAT_TURN});39    }40    for (int i = 1; i < n; ++i) {41      res[i][i][MOUSE_TURN] = CAT_WIN;42      res[i][i][CAT_TURN] = CAT_WIN;43      q.offer(new int[]{i, i, MOUSE_TURN});44      q.offer(new int[]{i, i, CAT_TURN});45    }46    while (!q.isEmpty()) {47      int[] state = q.poll();48      int t = res[state[0]][state[1]][state[2]];49      List<int[]> prevStates = getPrevStates(state);50      for (var prevState : prevStates) {51        int pm = prevState[0], pc = prevState[1], pt = prevState[2];52        if (res[pm][pc][pt] == TIE) {53          boolean win = (t == MOUSE_WIN && pt == MOUSE_TURN) ||54                        (t == CAT_WIN && pt == CAT_TURN);55          if (win) {56            res[pm][pc][pt] = t;57            q.offer(prevState);58          } else {59            if (--degree[pm][pc][pt] == 0) {60              res[pm][pc][pt] = t;61              q.offer(prevState);62            }63          }64        }65      }66    }67    return res[MOUSE_START][CAT_START][MOUSE_TURN];68  }69private70  List<int[]> getPrevStates(int[] state) {71    List<int[]> pre = new ArrayList<>();72    int m = state[0], c = state[1], t = state[2];73    int pt = t ^ 1;74    if (pt == CAT_TURN) {75      for (int pc : g[c]) {76        if (pc != HOLE) {77          pre.add(new int[]{m, pc, pt});78        }79      }80    } else {81      for (int pm : g[m]) {82        pre.add(new int[]{pm, c, pt});83      }84    }85    return pre;86  }87}

1const int HOLE = 0 ; const int MOUSE_START = 1 ; const int CAT_START = 2 ; const int MOUSE_TURN = 0 ; const int CAT_TURN = 1 ; const int MOUSE_WIN = 1 ; const int CAT_WIN = 2 ; const int TIE = 0 ; class Solution { public: int catMouseGame ( vector < vector < int >>& graph ) { int n = graph . size (); int res [ n ][ n ][ 2 ]; int degree [ n ][ n ][ 2 ]; memset ( res , 0 , sizeof res ); memset ( degree , 0 , sizeof degree ); for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 1 ; j < n ; ++ j ) { degree [ i ][ j ][ MOUSE_TURN ] = graph [ i ]. size (); degree [ i ][ j ][ CAT_TURN ] = graph [ j ]. size (); } for ( int j : graph [ HOLE ]) { -- degree [ i ][ j ][ CAT_TURN ]; } } auto getPrevStates = [ & ]( int m , int c , int t ) { int pt = t ^ 1 ; vector < tuple < int , int , int >> pre ; if ( pt == CAT_TURN ) { for ( int pc : graph [ c ]) { if ( pc != HOLE ) { pre . emplace_back ( m , pc , pt ); } } } else { for ( int pm : graph [ m ]) { pre . emplace_back ( pm , c , pt ); } } return pre ; }; queue < tuple < int , int , int >> q ; for ( int j = 1 ; j < n ; ++ j ) { res [ 0 ][ j ][ MOUSE_TURN ] = res [ 0 ][ j ][ CAT_TURN ] = MOUSE_WIN ; q . emplace ( 0 , j , MOUSE_TURN ); q . emplace ( 0 , j , CAT_TURN ); } for ( int i = 1 ; i < n ; ++ i ) { res [ i ][ i ][ MOUSE_TURN ] = res [ i ][ i ][ CAT_TURN ] = CAT_WIN ; q . emplace ( i , i , MOUSE_TURN ); q . emplace ( i , i , CAT_TURN ); } while ( ! q . empty ()) { auto [ m , c , t ] = q . front (); q . pop (); int x = res [ m ][ c ][ t ]; for ( auto [ pm , pc , pt ] : getPrevStates ( m , c , t )) { if ( res [ pm ][ pc ][ pt ] == TIE ) { bool win = ( x == MOUSE_WIN && pt == MOUSE_TURN ) || ( x == CAT_WIN && pt == CAT_TURN ); if ( win ) { res [ pm ][ pc ][ pt ] = x ; q . emplace ( pm , pc , pt ); } else { if ( -- degree [ pm ][ pc ][ pt ] == 0 ) { res [ pm ][ pc ][ pt ] = x ; q . emplace ( pm , pc , pt ); } } } } } return res [ MOUSE_START ][ CAT_START ][ MOUSE_TURN ]; } };

1HOLE , MOUSE_START , CAT_START = 0 , 1 , 2 MOUSE_TURN , CAT_TURN = 0 , 1 MOUSE_WIN , CAT_WIN , TIE = 1 , 2 , 0 class Solution : def catMouseGame ( self , graph : List [ List [ int ]]) -> int : def get_prev_states ( state ): m , c , t = state pt = t ^ 1 pre = [] if pt == CAT_TURN : for pc in graph [ c ]: if pc != HOLE : pre . append (( m , pc , pt )) else : for pm in graph [ m ]: pre . append (( pm , c , pt )) return pre n = len ( graph ) res = [[[ 0 , 0 ] for _ in range ( n )] for _ in range ( n )] degree = [[[ 0 , 0 ] for _ in range ( n )] for _ in range ( n )] for i in range ( n ): for j in range ( 1 , n ): degree [ i ][ j ][ MOUSE_TURN ] = len ( graph [ i ]) degree [ i ][ j ][ CAT_TURN ] = len ( graph [ j ]) for j in graph [ HOLE ]: degree [ i ][ j ][ CAT_TURN ] -= 1 q = deque () for j in range ( 1 , n ): res [ 0 ][ j ][ MOUSE_TURN ] = res [ 0 ][ j ][ CAT_TURN ] = MOUSE_WIN q . append (( 0 , j , MOUSE_TURN )) q . append (( 0 , j , CAT_TURN )) for i in range ( 1 , n ): res [ i ][ i ][ MOUSE_TURN ] = res [ i ][ i ][ CAT_TURN ] = CAT_WIN q . append (( i , i , MOUSE_TURN )) q . append (( i , i , CAT_TURN )) while q : state = q . popleft () t = res [ state [ 0 ]][ state [ 1 ]][ state [ 2 ]] for prev_state in get_prev_states ( state ): pm , pc , pt = prev_state if res [ pm ][ pc ][ pt ] == TIE : win = ( t == MOUSE_WIN and pt == MOUSE_TURN ) or ( t == CAT_WIN and pt == CAT_TURN ) if win : res [ pm ][ pc ][ pt ] = t q . append ( prev_state ) else : degree [ pm ][ pc ][ pt ] -= 1 if degree [ pm ][ pc ][ pt ] == 0 : res [ pm ][ pc ][ pt ] = t q . append ( prev_state ) return res [ MOUSE_START ][ CAT_START ][ MOUSE_TURN ]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem