913. Cat and Mouse

HardGraphTopological SortMemoizationMathDynamic ProgrammingGame Theory
Leetcode Link

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:

  1. If the cat and mouse occupy the same node, the cat wins.
  2. If the mouse reaches the hole safely, the mouse wins.
  3. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of the following is a good use case for backtracking?

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 either 1 for a mouse win, 2 for a cat win, or 0 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 a Deque for the BFS.

  • 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.

  • 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.

  • 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 node 1, the cat at node 2, and itโ€™s the mouse's turn.

  • 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 of O(N^2) and similar space complexity for storing the res and degree arrays.

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.

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

Which type of traversal does breadth first search do?

Example 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:

  1. Initial Position: The mouse is at node 1, and the cat is at node 2. It is the mouse's turn.
  2. Mouse's Optimized Decision: The mouse can move to node 3, 6, or stay at 1. The optimal move for the mouse is towards node 6 because it provides a path to the hole at 0.
  3. Cat's Optimized Decision: After the mouse moves to 6, the cat can choose to go to 1, 3, or 5. The cat will move to 1 to anticipate blocking the mouse's return past 6.
  4. End Game State Evaluation:
    • If the mouse moves to node 0 from node 6, the mouse wins.
    • If the mouse were to move back to node 1, the cat would be there and win the game.

Using the solution approach:

  • Data Structure Initialization: The res array is initialized, and the winning states of res[6][any_node][mouse_turn] are marked as 1 because the mouse wins if it gets to node 6, then to 0. Also, res[any_node][same_as_mouse][cat_turn] is marked as 2, 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 and degree arrays.
    • res[6][1][1] is marked as 1 because the mouse can win from here by moving to node 0.
    • From node 1, where the cat is (and it's now the mouse's turn), any movement to a mouse victory state (6, then 0) leads to updating the state res[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 and degree arrays through this backtracking process, the final result can be read from res[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 to 1, 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which algorithm should you use to find a node that is close to the root of the tree?

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:

  1. 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 has 2 * n * n states since there are n mouse positions, n cat positions (excluding the hole), and 2 turns.

  2. 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 be n-1 if the graph is fully connected.

  3. Initialization of degree takes O(n^2) time as we go through every combination of i and j, 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:

  1. The space complexity is dominated by the size of the res and degree arrays, which take O(n^2) space.

  2. In addition to the res and degree arrays, we have a Deque 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 exceed O(n^2).

  3. The getPrevStates function creates a list of previous states. In the worst case, it will have O(n) size (considering a fully connected graph) and is called O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings

Graph Fundamentals

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 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

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ