913. Cat and Mouse
Problem Description
The given problem is a simulation of a game played on an undirected graph between two players: Mouse and Cat. The game's configuration is a graph where each element graph[a]
is a list of nodes b
that can be reached from node a
via a single edge. The mouse starts at node 1
, the cat at node 2
, and node 0
represents a hole. The mouse moves first, followed by the cat, and the game alternates turns.
Here's what each player must do and how the game can conclude:
- On each turn, a player must move to an adjacent node listed in
[graph](/problems/graph_intro)
. - The cat is not allowed to move to the hole (node
0
).
The game can end in one of three ways:
- If the cat and mouse occupy the same node, the cat wins.
- If the mouse reaches the hole safely, the mouse wins.
- If the game reaches a repeated state (same positions for mouse and cat, with the same player to move as a previous turn), it is considered a draw.
The objective is to determine the outcome of the game, assuming both players play optimally, with the possible outcomes being: mouse wins (return 1
), cat wins (return 2
), or the game is a draw (return 0
).
Intuition
The intuition behind the solution is based on game theory, particularly the concept of "minimax" where each player minimizes the potential loss for a worst-case scenario. Since both players play optimally, we need to predict the outcome from any position in the game.
To do this optimally, we use dynamic programming. We define a state in our DP as a combination of positions of the mouse and the cat and whose turn it is, and then we compute the outcome of the game from that state.
We initialize the DP states with the base cases:
- If the mouse is at the hole at any point, the mouse wins.
- If the cat catches up to the mouse (both in the same node), the cat wins.
From there, we perform a breadth-first search (BFS) on the state graph in reverse, starting from the known outcomes (mouse wins or cat wins) and propagating these results backward to the initial position (mouse at node 1
, cat at node 2
) to compute its outcome. If a state could lead to a win (for the respective player's turn), we mark it as a win. If a state could lead to a loss for both players (depending on their moves), we reduce the degree of uncertainty (used here as a heuristic) until it becomes deterministic (win or lose). If a state cannot lead to a loss but all moves lead to states that eventually would lead to a win, we consider this a losing state as well.
This propagation continues until no more states can be resolved, at which point we can return the result for the starting position, which is stored in res[MOUSE_START][CAT_START][MOUSE_TURN]
.
The provided solution uses top-down dynamic programming with memoization (storing results of subproblems) to avoid recomputing the result for the same state multiple times, and a 3D array (res
) to keep track of the result from each state, along with a degree array (degree
) to help determine draw conditions by tracking the number of unresolved transitions from each state.
Learn more about Graph, Topological Sort, Memoization, Math and Dynamic Programming patterns.
Solution Approach
The solution applies graph search techniques combined with dynamic programming to predict the outcome of the game from any state.
-
Data Structures Used:
- A 2D array
g
to store the graph. - A 3D array
res
to cache the outcomes of states[mouse_position][cat_position][turn]
. Each entry can be either1
for a mouse win,2
for a cat win, or0
for pending/draw. - A 3D array
degree
is used to track the number of possible exit states from each[mouse_position][cat_position][turn]
state that are not yet resolved. - A queue
q
implemented with aDeque
for the BFS.
- A 2D array
-
Initialization:
- Before starting the BFS, we identify obviously winning states — those where the mouse is at the hole (a mouse win) and those where the cat is at the same position as the mouse (a cat win). These states are enqueued into
q
to serve as starting points for the BFS.
- Before starting the BFS, we identify obviously winning states — those where the mouse is at the hole (a mouse win) and those where the cat is at the same position as the mouse (a cat win). These states are enqueued into
-
Breadth-First Search in Reverse:
- The BFS is started in reverse from the winning states. From any given state
(mouse, cat, turn)
in the queue, we attempt to find all predecessor states(pm, pc, pt)
— states from which a player could move to the current state. - If a predecessor state results in the current player's victory, we can immediately assign the victory to the predecessor state and enqueue it.
- If a predecessor state doesn't lead to an immediate win, we decrement the degree of that state. If the degree reaches zero, which means all subsequent moves lead to the opponent winning, we assign a loss to the state and enqueue it.
- The BFS is started in reverse from the winning states. From any given state
-
Finding Predecessor States:
- To find predecessor states, we determine whether it was the mouse's or cat's turn. If it was the mouse's turn, we look at all the cat's previous moves; if it was the cat's turn, we look at all the mouse's previous moves. This is done without considering invalid moves (like the cat moving to the hole).
-
Termination and Result:
- The algorithm runs until there are no more states to evaluate (i.e., the queue
q
is empty). - The result for the starting position is retrieved from
res[1][2][0]
, which represents the game's outcome when the mouse starts at node1
, the cat at node2
, and it’s the mouse's turn.
- The algorithm runs until there are no more states to evaluate (i.e., the queue
-
Complexity Analysis:
- Let
N
be the number of nodes in the graph. The complexity of this algorithm is challenging to determine precisely because it involves an adversarial search where the exact number of states explored depends on the graph's structure. However, each state is considered at most once per player, leading to a time complexity upper bound ofO(N^2)
and similar space complexity for storing theres
anddegree
arrays.
- Let
The implementation of the solution uses a depth-first search in reverse to efficiently propagate the outcomes from known win/lose states towards the initial state, using a careful tracking of state progression to avoid cycles that would result in draws.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Imagine a graph setup with the following edges:
1graph[0] = [] // The hole, which only the mouse can enter. 2graph[1] = [2, 3, 6] // The mouse starts here and can move to the nodes 2, 3, or 6. 3graph[2] = [1, 3, 5] // The cat starts here and can move to the nodes 1, 3, or 5. 4graph[3] = [1, 2] // An intermediate node. 5graph[4] = [5] // The cat can't reach this node, but the mouse can if it starts here. 6graph[5] = [2, 4] // An intermediate node. 7graph[6] = [1, 0] // An escape path where the mouse can move to the hole (0).
Let's walk through one scenario:
- Initial Position: The mouse is at node
1
, and the cat is at node2
. It is the mouse's turn. - Mouse's Optimized Decision: The mouse can move to node
3
,6
, or stay at1
. The optimal move for the mouse is towards node6
because it provides a path to the hole at0
. - Cat's Optimized Decision: After the mouse moves to
6
, the cat can choose to go to1
,3
, or5
. The cat will move to1
to anticipate blocking the mouse's return past6
. - End Game State Evaluation:
- If the mouse moves to node
0
from node6
, the mouse wins. - If the mouse were to move back to node
1
, the cat would be there and win the game.
- If the mouse moves to node
Using the solution approach:
- Data Structure Initialization: The
res
array is initialized, and the winning states ofres[6][any_node][mouse_turn]
are marked as1
because the mouse wins if it gets to node6
, then to0
. Also,res[any_node][same_as_mouse][cat_turn]
is marked as2
, indicating that the cat will win if it is on the same node as the mouse on the cat's turn. - Breadth-First Search in Reverse: The BFS begins from the end states, filling out the
res
anddegree
arrays.res[6][1][1]
is marked as1
because the mouse can win from here by moving to node0
.- From node
1
, where the cat is (and it's now the mouse's turn), any movement to a mouse victory state (6
, then0
) leads to updating the stateres[1][2][0]
towards a mouse victory. Similarly, cat victory states are deduced.
- Backtracking to Initial State: We deduce the results for other states by considering possible moves backwards.
- Returning the Outcome: After filling out the
res
anddegree
arrays through this backtracking process, the final result can be read fromres[1][2][0]
. In the given example, since the mouse can reach a win state from the starting position,res[1][2][0]
will be set to1
, indicating a mouse win.
The above walkthrough provides an example of how the game might play out, demonstrating the propagation of win/loss states back to the initial state to predict the outcome, assuming optimal play by both the mouse and the cat.
Solution Implementation
1from collections import deque
2
3# Constants to improve readability.
4HOLE = 0
5MOUSE_START = 1
6CAT_START = 2
7MOUSE_TURN = 0
8CAT_TURN = 1
9MOUSE_WIN = 1
10CAT_WIN = 2
11DRAW = 0
12
13class Solution:
14 def cat_mouse_game(self, graph):
15 nodes_count = len(graph)
16 # Initialize results and degrees for dynamic programming.
17 result = [[[DRAW] * 2 for _ in range(nodes_count)] for _ in range(nodes_count)]
18 degrees = [[[0] * 2 for _ in range(nodes_count)] for _ in range(nodes_count)]
19
20 # Initialize the degrees and result matrices.
21 for mouse_pos in range(nodes_count):
22 for cat_pos in range(1, nodes_count):
23 degrees[mouse_pos][cat_pos][MOUSE_TURN] = len(graph[mouse_pos])
24 degrees[mouse_pos][cat_pos][CAT_TURN] = len(graph[cat_pos]) - graph[cat_pos].count(HOLE)
25
26 # Helper function to get previous states for mouse and cat turns.
27 def get_prev_states(mouse_pos, cat_pos, turn):
28 previous_states = []
29 prev_turn = 1 - turn # Toggle turn
30 if prev_turn == CAT_TURN:
31 # Possible positions for the cat's previous turn.
32 for prev_cat_pos in graph[cat_pos]:
33 if prev_cat_pos != HOLE:
34 previous_states.append((mouse_pos, prev_cat_pos, prev_turn))
35 else:
36 # Possible positions for the mouse's previous turn.
37 for prev_mouse_pos in graph[mouse_pos]:
38 previous_states.append((prev_mouse_pos, cat_pos, prev_turn))
39 return previous_states
40
41 # Queue for processing states using BFS.
42 states_queue = deque()
43
44 # Initialize the queue with base cases where the game is already decided.
45 for i in range(1, nodes_count):
46 result[HOLE][i][MOUSE_TURN] = result[HOLE][i][CAT_TURN] = MOUSE_WIN
47 states_queue.append((HOLE, i, MOUSE_TURN))
48 states_queue.append((HOLE, i, CAT_TURN))
49
50 result[i][i][MOUSE_TURN] = result[i][i][CAT_TURN] = CAT_WIN
51 states_queue.append((i, i, MOUSE_TURN))
52 states_queue.append((i, i, CAT_TURN))
53
54 # Process the queue using BFS to determine the rest of the game states.
55 while states_queue:
56 mouse_pos, cat_pos, turn = states_queue.popleft()
57 curr_result = result[mouse_pos][cat_pos][turn]
58
59 # Evaluate all previous states.
60 for prev_mouse_pos, prev_cat_pos, prev_turn in get_prev_states(mouse_pos, cat_pos, turn):
61 # If the outcome has not been determined for this state.
62 if result[prev_mouse_pos][prev_cat_pos][prev_turn] == DRAW:
63 can_win = (curr_result == MOUSE_WIN and prev_turn == MOUSE_TURN) or (curr_result == CAT_WIN and prev_turn == CAT_TURN)
64 if can_win:
65 # Update the state directly if we know it leads to a win.
66 result[prev_mouse_pos][prev_cat_pos][prev_turn] = curr_result
67 states_queue.append((prev_mouse_pos, prev_cat_pos, prev_turn))
68 else:
69 # Decrement the degree and check if we can conclude the result.
70 degrees[prev_mouse_pos][prev_cat_pos][prev_turn] -= 1
71 if degrees[prev_mouse_pos][prev_cat_pos][prev_turn] == 0:
72 result[prev_mouse_pos][prev_cat_pos][prev_turn] = curr_result
73 states_queue.append((prev_mouse_pos, prev_cat_pos, prev_turn))
74
75 # Return the result for the starting state of the game.
76 return result[MOUSE_START][CAT_START][MOUSE_TURN]
77
1import java.util.ArrayDeque;
2import java.util.ArrayList;
3import java.util.Deque;
4import java.util.List;
5
6class Solution {
7 private int nodeCount;
8 private int[][] graph;
9 private int[][][] result;
10 private int[][][] nodeDegree;
11
12 // Constants representing different states and entities in the game
13 private static final int HOLE = 0, MOUSE_START = 1, CAT_START = 2;
14 private static final int MOUSE_TURN = 0, CAT_TURN = 1;
15 private static final int MOUSE_WIN = 1, CAT_WIN = 2, DRAW = 0;
16
17 public int catMouseGame(int[][] graph) {
18 nodeCount = graph.length;
19 this.graph = graph;
20 result = new int[nodeCount][nodeCount][2];
21 nodeDegree = new int[nodeCount][nodeCount][2];
22
23 // Initialize degrees based on possible moves from each node
24 for (int mousePosition = 0; mousePosition < nodeCount; ++mousePosition) {
25 for (int catPosition = 1; catPosition < nodeCount; ++catPosition) {
26 nodeDegree[mousePosition][catPosition][MOUSE_TURN] = this.graph[mousePosition].length;
27 nodeDegree[mousePosition][catPosition][CAT_TURN] = this.graph[catPosition].length;
28 }
29 }
30 // Decrease the cat's degree for positions connected to the hole
31 for (int catNextPosition : graph[HOLE]) {
32 --nodeDegree[HOLE][catNextPosition][CAT_TURN];
33 }
34
35 Deque<int[]> queue = new ArrayDeque<>();
36 // Initialize the result and queue for the cases where mouse wins
37 for (int catPosition = 1; catPosition < nodeCount; ++catPosition) {
38 result[HOLE][catPosition][MOUSE_TURN] = MOUSE_WIN;
39 result[HOLE][catPosition][CAT_TURN] = MOUSE_WIN;
40 queue.offer(new int[] {HOLE, catPosition, MOUSE_TURN});
41 queue.offer(new int[] {HOLE, catPosition, CAT_TURN});
42 }
43
44 // Initialize the result and queue for the cases where cat wins
45 for (int position = 1; position < nodeCount; ++position) {
46 result[position][position][MOUSE_TURN] = CAT_WIN;
47 result[position][position][CAT_TURN] = CAT_WIN;
48 queue.offer(new int[] {position, position, MOUSE_TURN});
49 queue.offer(new int[] {position, position, CAT_TURN});
50 }
51
52 // Perform breadth-first search to determine the result of the game
53 while (!queue.isEmpty()) {
54 int[] currentState = queue.poll();
55 int currentResult = result[currentState[0]][currentState[1]][currentState[2]];
56 List<int[]> previousStates = getPreviousStates(currentState);
57
58 // Process all previous states that can lead to the current state
59 for (int[] prevState : previousStates) {
60 int prevMouse = prevState[0], prevCat = prevState[1], prevTurn = prevState[2];
61 if (result[prevMouse][prevCat][prevTurn] == DRAW) {
62 boolean isWin = (currentResult == MOUSE_WIN && prevTurn == MOUSE_TURN) ||
63 (currentResult == CAT_WIN && prevTurn == CAT_TURN);
64 if (isWin) {
65 result[prevMouse][prevCat][prevTurn] = currentResult;
66 queue.offer(prevState);
67 } else {
68 if (--nodeDegree[prevMouse][prevCat][prevTurn] == 0) {
69 result[prevMouse][prevCat][prevTurn] = currentResult;
70 queue.offer(prevState);
71 }
72 }
73 }
74 }
75 }
76
77 return result[MOUSE_START][CAT_START][MOUSE_TURN];
78 }
79
80 // Helper method to get all previous states that can lead to the current state
81 private List<int[]> getPreviousStates(int[] state) {
82 List<int[]> previousStates = new ArrayList<>();
83 int mousePosition = state[0], catPosition = state[1], turn = state[2];
84 int previousTurn = turn ^ 1; // Toggle turn
85
86 // If it was the cat's turn, get all mouse positions that lead here
87 if (previousTurn == CAT_TURN) {
88 for (int previousCat : graph[catPosition]) {
89 if (previousCat != HOLE) {
90 previousStates.add(new int[] {mousePosition, previousCat, previousTurn});
91 }
92 }
93 } else { // Otherwise, get all cat positions that lead here
94 for (int previousMouse : graph[mousePosition]) {
95 previousStates.add(new int[] {previousMouse, catPosition, previousTurn});
96 }
97 }
98
99 return previousStates;
100 }
101}
102
1#include <vector>
2#include <queue>
3#include <tuple>
4#include <cstring>
5
6using namespace std;
7
8const int HOLE = 0;
9const int MOUSE_START = 1;
10const int CAT_START = 2;
11const int MOUSE_TURN = 0;
12const int CAT_TURN = 1;
13const int MOUSE_WIN = 1;
14const int CAT_WIN = 2;
15const int DRAW = 0;
16
17class Solution {
18public:
19 int catMouseGame(vector<vector<int>>& graph) {
20 int nodes_count = graph.size();
21 int result[nodes_count][nodes_count][2];
22 int degrees[nodes_count][nodes_count][2];
23 memset(result, 0, sizeof result);
24 memset(degrees, 0, sizeof degrees);
25
26 // Initialize the degrees and result matrices
27 for (int mouse_pos = 0; mouse_pos < nodes_count; ++mouse_pos) {
28 for (int cat_pos = 1; cat_pos < nodes_count; ++cat_pos) {
29 degrees[mouse_pos][cat_pos][MOUSE_TURN] = graph[mouse_pos].size();
30 degrees[mouse_pos][cat_pos][CAT_TURN] = graph[cat_pos].size();
31 // Exclude the hole position from the cat's move
32 for (int hole_neighbor : graph[HOLE]) {
33 --degrees[mouse_pos][hole_neighbor][CAT_TURN];
34 }
35 }
36 }
37
38 // Helper lambda function to retrieve previous states for mouse and cat turns
39 auto getPrevStates = [&](int mouse_pos, int cat_pos, int turn) {
40 vector<tuple<int, int, int>> previous_states;
41 int prev_turn = turn ^ 1; // Toggle turn
42 if (prev_turn == CAT_TURN) {
43 // Get all possible positions for the previous cat's turn
44 for (int prev_cat_pos : graph[cat_pos]) {
45 if (prev_cat_pos != HOLE) {
46 previous_states.emplace_back(mouse_pos, prev_cat_pos, prev_turn);
47 }
48 }
49 } else {
50 // Get all possible positions for the previous mouse's turn
51 for (int prev_mouse_pos : graph[mouse_pos]) {
52 previous_states.emplace_back(prev_mouse_pos, cat_pos, prev_turn);
53 }
54 }
55 return previous_states;
56 };
57
58 // Queue to use BFS approach
59 queue<tuple<int, int, int>> states_queue;
60
61 // Initialize results for cases where game is over
62 for (int i = 1; i < nodes_count; ++i) {
63 result[0][i][MOUSE_TURN] = result[0][i][CAT_TURN] = MOUSE_WIN;
64 states_queue.emplace(0, i, MOUSE_TURN);
65 states_queue.emplace(0, i, CAT_TURN);
66
67 result[i][i][MOUSE_TURN] = result[i][i][CAT_TURN] = CAT_WIN;
68 states_queue.emplace(i, i, MOUSE_TURN);
69 states_queue.emplace(i, i, CAT_TURN);
70 }
71
72 // Process the queue until there are no more states to evaluate
73 while (!states_queue.empty()) {
74 auto [mouse_pos, cat_pos, turn] = states_queue.front();
75 states_queue.pop();
76 int curr_result = result[mouse_pos][cat_pos][turn];
77
78 // Evaluate all previous states
79 for (auto [prev_mouse_pos, prev_cat_pos, prev_turn] : getPrevStates(mouse_pos, cat_pos, turn)) {
80 // Outcome has yet to be determined for this state
81 if (result[prev_mouse_pos][prev_cat_pos][prev_turn] == DRAW) {
82 bool is_win = (curr_result == MOUSE_WIN && prev_turn == MOUSE_TURN) ||
83 (curr_result == CAT_WIN && prev_turn == CAT_TURN);
84 if (is_win) {
85 // If result is win, update the state directly
86 result[prev_mouse_pos][prev_cat_pos][prev_turn] = curr_result;
87 states_queue.emplace(prev_mouse_pos, prev_cat_pos, prev_turn);
88 } else {
89 // If not a win, decrement degree and check if it's time to update state
90 if (--degrees[prev_mouse_pos][prev_cat_pos][prev_turn] == 0) {
91 result[prev_mouse_pos][prev_cat_pos][prev_turn] = curr_result;
92 states_queue.emplace(prev_mouse_pos, prev_cat_pos, prev_turn);
93 }
94 }
95 }
96 }
97 }
98 // Result for starting state of the game
99 return result[MOUSE_START][CAT_START][MOUSE_TURN];
100 }
101};
102
1const HOLE = 0;
2const MOUSE_START = 1;
3const CAT_START = 2;
4const MOUSE_TURN = 0;
5const CAT_TURN = 1;
6const MOUSE_WIN = 1;
7const CAT_WIN = 2;
8const DRAW = 0;
9
10function catMouseGame(graph: number[][]): number {
11 const nodesCount = graph.length;
12 const result: number[][][] = Array.from({ length: nodesCount }, () =>
13 Array.from({ length: nodesCount }, () => Array(2).fill(DRAW))
14 );
15
16 // Initialize the degrees with movement options except for the forbidden moves for the cat
17 const degrees: number[][][] = graph.map((neighbors, mousePos) =>
18 neighbors.map((_, catPos) => [
19 graph[mousePos].length,
20 catPos === HOLE ? 0 : graph[catPos].length - graph[HOLE].length
21 ])
22 );
23
24 // Retrieves all previous states given the current state, based on whose turn it is
25 const getPrevStates = (mousePos: number, catPos: number, turn: number): number[][] => {
26 let previousStates: number[][] = [];
27 const prevTurn = turn ^ 1; // Toggle turn
28 if (prevTurn === CAT_TURN) {
29 // Get previous states for cat
30 graph[catPos].forEach((prevCatPos) => {
31 if (prevCatPos !== HOLE) {
32 previousStates.push([mousePos, prevCatPos, prevTurn]);
33 }
34 });
35 } else {
36 // Get previous states for mouse
37 graph[mousePos].forEach((prevMousePos) => {
38 previousStates.push([prevMousePos, catPos, prevTurn]);
39 });
40 }
41 return previousStates;
42 };
43
44 const statesQueue: number[][] = [];
45
46 // Prepare results for base cases and push them to the states queue
47 for (let i = 1; i < nodesCount; ++i) {
48 result[0][i].fill(MOUSE_WIN);
49 statesQueue.push([0, i, MOUSE_TURN], [0, i, CAT_TURN]);
50
51 result[i][i].fill(CAT_WIN);
52 statesQueue.push([i, i, MOUSE_TURN], [i, i, CAT_TURN]);
53 }
54
55 while (statesQueue.length > 0) {
56 const [mousePos, catPos, turn] = statesQueue.shift() as number[];
57 let currResult = result[mousePos][catPos][turn];
58
59 // Evaluate all previous states
60 getPrevStates(mousePos, catPos, turn).forEach(([prevMousePos, prevCatPos, prevTurn]) => {
61 // Skip already determined states
62 if (result[prevMousePos][prevCatPos][prevTurn] === DRAW) {
63 let isWin = (currResult === MOUSE_WIN && prevTurn === MOUSE_TURN) ||
64 (currResult === CAT_WIN && prevTurn === CAT_TURN);
65 if (isWin) {
66 // Directly update the winning state
67 result[prevMousePos][prevCatPos][prevTurn] = currResult;
68 statesQueue.push([prevMousePos, prevCatPos, prevTurn]);
69 } else {
70 // Decrement degree and check if it's time to update the state
71 if (--degrees[prevMousePos][prevCatPos][prevTurn] === 0) {
72 result[prevMousePos][prevCatPos][prevTurn] = currResult;
73 statesQueue.push([prevMousePos, prevCatPos, prevTurn]);
74 }
75 }
76 }
77 });
78 }
79
80 // Return the result for the starting state of the game
81 return result[MOUSE_START][CAT_START][MOUSE_TURN];
82}
83
Time and Space Complexity
The given Java code implements a solution for the Cat and Mouse game using a top-down dynamic programming approach combined with breadth-first search (BFS). To analyze the computational complexity, we'll examine the time complexity and space complexity separately:
Time Complexity:
-
The main computation involves BFS on the state space graph. Each state is a combination of mouse position (
m
), cat position (c
), and whose turn it is (t
). The state space thus has2 * n * n
states since there aren
mouse positions,n
cat positions (excluding the hole), and2
turns. -
Each state will be processed once in the BFS loop. For each state, we potentially examine all previous states. For the mouse's turn, we look at
g[m].length
previous cat positions and for the cat's turn,g[c].length - 1
previous mouse positions. In the worst case,g[i].length
could ben-1
if the graph is fully connected. -
Initialization of
degree
takesO(n^2)
time as we go through every combination ofi
andj
, not including the hole for the cat.
Considering these points, the time complexity of the code is O(n^3)
, as we process each state once and the amount of work per state is proportional to the degree of the vertices in the graph, which could be O(n)
in the case of a dense graph.
Space Complexity:
-
The space complexity is dominated by the size of the
res
anddegree
arrays, which takeO(n^2)
space. -
In addition to the
res
anddegree
arrays, we have aDeque
that in the worst case might store all of the states. However, since we process and remove each state only once, the queue size at any one point would not exceedO(n^2)
. -
The
getPrevStates
function creates a list of previous states. In the worst case, it will haveO(n)
size (considering a fully connected graph) and is calledO(n^2)
times. This does not add to the overall space complexity, as they are temporary and processed immediately.
With these considerations, the space complexity of the code is O(n^2)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Depth first search is equivalent to which of the tree traversal order?
Recommended Readings
https algomonster s3 us east 2 amazonaws com 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
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 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
Line 32-34 :
Should be outside the for-loop for
cat_pos
since we are doing the above operation only once for eachmouse_pos