How hard is LeetCode 913. Cat and Mouse?

LeetCode 913. Cat and Mouse is rated Hard on LeetCode.

What is the time complexity of LeetCode 913. Cat and Mouse?

The Python solution on this page runs in O(n^3).

What is the space complexity of LeetCode 913. Cat and Mouse?

The Python solution on this page uses O(n^2) auxiliary space.

Cat and Mouse — LeetCode 913 Python Solution

HardGraphTopological SortMemoizationMathDynamic ProgrammingGame Theory

Problem: #913
Pattern: Topological Sort
Reading time: 10 min
Source: leetcode.com

The problem

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.

Example

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

Python solution

Python

HOLE, 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)
        ans = [[[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):
            ans[0][j][MOUSE_TURN] = ans[0][j][CAT_TURN] = MOUSE_WIN
            q.append((0, j, MOUSE_TURN))
            q.append((0, j, CAT_TURN))
        for i in range(1, n):
            ans[i][i][MOUSE_TURN] = ans[i][i][CAT_TURN] = CAT_WIN
            q.append((i, i, MOUSE_TURN))
            q.append((i, i, CAT_TURN))
        while q:
            state = q.popleft()
            t = ans[state[0]][state[1]][state[2]]
            for prev_state in get_prev_states(state):
                pm, pc, pt = prev_state
                if ans[pm][pc][pt] == TIE:
                    win = (t == MOUSE_WIN and pt == MOUSE_TURN) or (
                        t == CAT_WIN and pt == CAT_TURN
                    )
                    if win:
                        ans[pm][pc][pt] = t
                        q.append(prev_state)
                    else:
                        degree[pm][pc][pt] -= 1
                        if degree[pm][pc][pt] == 0:
                            ans[pm][pc][pt] = t
                            q.append(prev_state)
        return ans[MOUSE_START][CAT_START][MOUSE_TURN]

Complexity

Measure	Complexity
Time	O(n^3)
Space	O(n^2) auxiliary

Pattern: Topological Sort

Order a set of tasks so that every dependency comes before the thing that needs it. LeetCode 913. Cat and Mouse is filed here because LeetCode tags it Topological Sort, which is the vocabulary this hub collects.

The topological sort guide has the Python template for the pattern and the 32 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 913. Cat and Mouse?: LeetCode 913. Cat and Mouse is rated Hard on LeetCode.
What is the time complexity of LeetCode 913. Cat and Mouse?: The Python solution on this page runs in O(n^3).
What is the space complexity of LeetCode 913. Cat and Mouse?: The Python solution on this page uses O(n^2) auxiliary space.
What topics does LeetCode 913. Cat and Mouse cover?: LeetCode 913. Cat and Mouse is tagged Graph, Topological Sort, Memoization, Math, Dynamic Programming and Game Theory on LeetCode.