749. Contain Virus

HardDepth-First SearchBreadth-First SearchArrayMatrixSimulation
Leetcode Link

Problem Description

In this problem, we're given a representation of a world as an m x n binary grid called isInfected, where each cell can be either infected (1) or uninfected (0). The task is to stop the spread of a virus by building walls. The virus spreads every night to all unblocked, neighboring cells located in any of the four cardinal directions from an infected cell (up, down, left, right). However, we're limited in resources; we can build walls around only one region each day. A region is defined as a connected block of infected cells that directly threaten uninfected cells. The goal is to build walls in the most efficient way, prioritizing the regions that pose the greatest threat to the most uninfected cells. The output should be the total number of walls that needs to be installed to quarantine all the infected areas. If the whole world becomes infected, the output is the number of walls used before that happens.

To clarify, walls are placed between cells and not on the cells themselves. It means that a wall can be shared between two adjacent cells.

Flowchart Walkthrough

Let's determine the appropriate algorithm using the Flowchart for the LeetCode problem 749. Contain Virus. Here's a detailed walkthrough:

Is it a graph?

  • Yes: The problem describes a grid where cells affected with a virus and other cells are interconnected; similar to a graph structure.

Is it a tree?

  • No: The graph-like nature of the design includes multiple connections and does not have the hierarchical, non-cyclic nature of a tree.

Is the problem related to directed acyclic graphs (DAGs)?

  • No: The primary concern is containing the spread of the virus rather than traversing or involving directed acyclic properties.

Is the problem related to shortest paths?

  • No: The issue here relates to maximally containing an outbreak, not finding the shortest path through the grid.

Does the problem involve connectivity?

  • Yes: The goal is to identify and contain the most threatening region of virus spread, by examining the connectivity of infected cells.

Is the graph weighted?

  • No: Each cell can be treated equally; the virus either exists or does not exist in a cell, so it is unweighted in context.

Does the problem have small constraints?

  • Yes: Though not explicitly stated, the problem primarily involves managing and containing finite regions of infection fairly explicitly, which can be implicitly constrained.

DFS/backtracking

  • Yes: Given the nature of the problem with a focus on containment strategies over regions, DFS is apt for exhaustively exploring potential enclosure of infected areas.

Conclusion: The flowchart suggests using DFS/backtracking for efficiently handling the connectivity in unweighted graph scenarios and managing localized problem constraints. This choice is optimal for exploring and acting on all possibilities thoroughly.

Intuition

To solve this problem, we need to think about how to prioritize the regions for wall construction, since we're limited to building around one region each day. The most intuitive approach is to always target the region that will infect the most uninfected cells in the next move. This requires us to understand the three key aspects of our situation each day:

  1. Identifying all the separate regions of connected infected cells.
  2. Determining which uninfected neighboring cells might be threatened by each region.
  3. Figuring out how many new cells each region could potentially infect.

Using Depth First Search (DFS), we can explore each infected region from any starting infected cell. As we move through the region, we keep track of uninfected cells that are directly adjacent to this region. These uninfected cells are the ones "threatened" and could be infected the next night. By doing this for all infected regions, we can compare which region poses the greatest immediate threat by infecting the most uninfected cells.

Once we identify the most threatening region, we install walls around it. This region then gets quarantined and won't be able to spread the virus any further (represented by changing the cell values in this region to a different number, like -1).

For all other regions that we didn't quarantine this day, we allow the virus to spread to immediately neighboring uninfected cells, simulating the passage of one night. This is done by changing the state of these "threatened" cells from uninfected (0) to infected (1).

We repeat this process every day (each loop iteration in the code) until there are no more regions that can infect uninfected cells. The result is the number of walls we installed, which is the total count of cells that were threaten by the most dangerous region each day.

The key to the whole solution is to always choose the region to quarantine in a way that minimizes the spread of the virus, which is what this code aims to do efficiently.

Learn more about Depth-First Search and Breadth-First Search patterns.

Solution Approach

The implementation uses a depth-first search (DFS) algorithm to traverse the grid and identify the regions of connected infected cells, as well as the uninfected cells that could be infected by each region.

Here is a step-by-step breakdown of the approach:

  1. Initialize variables:

    • A list vis marks visited cells.
    • areas will contain lists where each list represents an infected region.
    • boundaries keeps track of the sets of threatened cells for each region.
    • c stores the count of threatened cells for each region.
    • ans accumulates the total number of walls built.

  2. Loop through the grid to identify infected areas:

    • For each infected and unvisited cell, perform a DFS. The DFS will:
      • Mark the cell as visited.
      • Add the cell to the current region's list in areas.
      • Look at the four cardinal directions. If it's an uninfected cell, increment the threatened cell count c for this region and add the cell to the current region's boundary set in boundaries.
      • If it's an infected and unvisited cell, continue the DFS from that cell.

  3. Find the most threatening region:

    • After all regions and their boundaries are identified, find the index (idx) of the region with the largest boundary set. This region threatens to infect the most uninfected cells and will be the target for wall construction.

  4. Build walls and update the grid:

    • Add the number of threatened cells by the most dangerous region (c[idx]) to ans.
    • Quarantine the most threatening region by setting its cells' values to -1 in isInfected.
    • For the non-quarantined areas, simulate the spread of the virus to their threatened cells by setting these cells' values to 1.

  5. Repeat the whole process:

    • Continue running steps 2-4 until there are no more regions that can infect uninfected cells.

  6. Return the result:

    • The variable ans now has the total count of walls built, which is returned as the result.

By applying DFS, this solution effectively maps out each unique region, determines the potential impact of its spread, and applies a greedy strategy by always quarantining the region that poses the greatest immediate threat, thereby minimizing the total number of walls required.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's use the solution approach on a small 3x3 isInfected grid world as an example:

0 1 0
0 1 0
0 0 0

Step 1: Initialize variables.

We initialize our variables:

  • vis set to all False, indicating no cells have been visited.
  • areas, boundaries, c, all empty, and ans set to 0.

Step 2: Loop through the grid to identify infected areas.

We start at cell [0,0] and see it's uninfected, so we move to cell [0,1] which is infected and unvisited. We begin DFS from this cell.

  • Mark [0,1] as visited, add it to the current region list in areas, and initialize boundary set for this region in boundaries.
  • Check its four neighbors. The ones with 0 increase c for this region and get added to its boundary set.
  • Continue DFS for any unvisited infected neighbors, we visit [1,1] and repeat the same process.

After this DFS, we have:

  • vis: Updated to reflect visited cells.
  • areas contains one list with cells [0,1] and [1,1].
  • boundaries contains the boundary cells [0,0], [1,0], [2,1], and [0,2].
  • c has only one element with value 4 as there are four cells threatened by this infection.
  • ans remains 0.

Step 3: Find the most threatening region.

  • We find idx of the region with the largest c value, which is 0 in this case because we have only one region.

Step 4: Build walls and update the grid.

  • We add c[0], which is 4, to ans.
  • We set the values of cells in the most threatening region [0,1] and [1,1] to -1 to indicate they're quarantined.

Our isInfected grid looks like this now:

0 -1 0
0 -1 0
0  0 0
  • We simulate the spread of the virus by changing the values of the boundary cells to 1, so none remain for the next iteration because the virus spread everywhere, and there are no new uninfected cells threatened.

Our grid after simulating the spread:

1 -1 1
1 -1 1
0  1 0

Step 5: Repeat the whole process.

  • We start another round of checks, but there are no more infectable regions left. Thus, we don't repeat the DFS.

Step 6: Return the result.

  • The total count of walls ans is returned, which is 4.

We placed a total of 4 walls to quarantine the only threatening region in this example.

Solution Implementation

1class Solution:
2    def contain_virus(self, is_infected: List[List[int]]) -> int:
3        # Helper function to perform depth-first search.
4        def dfs(i, j):
5            visited[i][j] = True  # Mark the node as visited.
6            areas[-1].append((i, j))  # Add the node to the current area.
7            # Check all four directions.
8            for delta_x, delta_y in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
9                x, y = i + delta_x, j + delta_y
10                # If indices are within the grid.
11                if 0 <= x < rows and 0 <= y < cols:
12                    if is_infected[x][y] == 1 and not visited[x][y]:
13                        dfs(x, y)  # DFS if the cell is infected but not visited.
14                    elif is_infected[x][y] == 0:
15                        walls_needed[-1] += 1  # A wall is needed.
16                        boundaries[-1].add((x, y))  # Add to boundaries.
17
18        # Get the size of the grid.
19        rows, cols = len(is_infected), len(is_infected[0])
20        total_walls = 0  # Total walls needed to contain the virus.
21
22        while True:
23            visited = [[False] * cols for _ in range(rows)]  # Visited cells.
24            areas = []  # Infected areas.
25            walls_needed = []  # Walls needed for each area.
26            boundaries = []  # Boundary cells for each area.
27
28            # Traverse all cells in the grid.
29            for i, row in enumerate(is_infected):
30                for j, val in enumerate(row):
31                    # If cell is infected and not visited, start new search.
32                    if val == 1 and not visited[i][j]:
33                        areas.append([])
34                        boundaries.append(set())
35                        walls_needed.append(0)
36                        dfs(i, j)
37
38            if not areas:  # If no infected areas are left, break.
39                break
40
41            # Find the most threatening area (with the most boundaries).
42            index_most_boundaries = boundaries.index(max(boundaries, key=len))
43            total_walls += walls_needed[index_most_boundaries]  # Add the walls needed.
44
45            # In each area...
46            for k, area in enumerate(areas):
47                if k == index_most_boundaries:
48                    # Contain the most threatening virus.
49                    for i, j in area:
50                        is_infected[i][j] = -1  # Mark the contained virus.
51                else:
52                    # Spread the virus in other areas.
53                    for i, j in area:
54                        for delta_x, delta_y in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
55                            x, y = i + delta_x, j + delta_y
56                            if 0 <= x < rows and 0 <= y < cols and is_infected[x][y] == 0:
57                                is_infected[x][y] = 1  # Infect the neighboring cell.
58
59        return total_walls  # Return the total walls needed.
60
1class Solution {
2    // DIRECTIONS array used to explore in four direct neighboring positions (up, right, down, left)
3    private static final int[] DIRECTIONS = {-1, 0, 1, 0, -1};
4    private List<Integer> wallCount = new ArrayList<>();
5    private List<List<Integer>> infectedAreas = new ArrayList<>();
6    private List<Set<Integer>> areaBoundaries = new ArrayList<>();
7    private int[][] isInfected;
8    private boolean[][] visited;
9    private int rowCount;
10    private int colCount;
11
12    public int containVirus(int[][] isInfected) {
13        this.isInfected = isInfected;
14        this.rowCount = isInfected.length;
15        this.colCount = isInfected[0].length;
16        this.visited = new boolean[rowCount][colCount];
17        int wallsRequired = 0;
18
19        while (true) {
20            // Resetting visited for the new iteration
21            for (boolean[] row : visited) {
22                Arrays.fill(row, false);
23            }
24            wallCount.clear();
25            infectedAreas.clear();
26            areaBoundaries.clear();
27
28            // Iterate over each cell in the grid
29            for (int i = 0; i < rowCount; ++i) {
30                for (int j = 0; j < colCount; ++j) {
31                    // for each unvisited infected cell start a new exploration
32                    if (isInfected[i][j] == 1 && !visited[i][j]) {
33                        wallCount.add(0);
34                        infectedAreas.add(new ArrayList<>());
35                        areaBoundaries.add(new HashSet<>());
36                        deepFirstSearch(i, j);
37                    }
38                }
39            }
40
41            // If no areas are infected, break the loop as no further action is required
42            if (infectedAreas.isEmpty()) {
43                break;
44            }
45
46            // Choose the most threatening area (one that affects most uninfected cells)
47            int mostThreatIndex = getMaxBoundaryIndex();
48            // Add the wall count for the most threatening area to the answer
49            wallsRequired += wallCount.get(mostThreatIndex);
50
51            // Process each infected area
52            for (int index = 0; index < infectedAreas.size(); ++index) {
53                if (index == mostThreatIndex) {
54                    // For the most threatening area, add walls (mark as -1)
55                    for (int infectedCell : infectedAreas.get(index)) {
56                        int row = infectedCell / colCount;
57                        int col = infectedCell % colCount;
58                        isInfected[row][col] = -1;
59                    }
60                } else {
61                    // Spread the virus from the other areas
62                    for (int infectedCell : infectedAreas.get(index)) {
63                        int row = infectedCell / colCount;
64                        int col = infectedCell % colCount;
65                        for (int k = 0; k < 4; ++k) {
66                            int newRow = row + DIRECTIONS[k];
67                            int newCol = col + DIRECTIONS[k + 1];
68                            if (isValidPosition(newRow, newCol) && isInfected[newRow][newCol] == 0) {
69                                isInfected[newRow][newCol] = 1;
70                            }
71                        }
72                    }
73                }
74            }
75        }
76        return wallsRequired;
77    }
78
79    // Utility method to get the index of the area which is spreading the virus most
80    private int getMaxBoundaryIndex() {
81        int index = 0;
82        int maxBoundarySize = areaBoundaries.get(0).size();
83        for (int i = 1; i < areaBoundaries.size(); ++i) {
84            int boundarySize = areaBoundaries.get(i).size();
85            if (maxBoundarySize < boundarySize) {
86                maxBoundarySize = boundarySize;
87                index = i;
88            }
89        }
90        return index;
91    }
92
93    // Deep first search to explore and mark all cells in an infected area
94    private void deepFirstSearch(int row, int col) {
95        visited[row][col] = true;
96        int currentAreaIndex = infectedAreas.size() - 1;
97        infectedAreas.get(currentAreaIndex).add(row * colCount + col);
98
99        for (int k = 0; k < 4; ++k) {
100            int newRow = row + DIRECTIONS[k];
101            int newCol = col + DIRECTIONS[k + 1];
102            if (isValidPosition(newRow, newCol)) {
103                if (isInfected[newRow][newCol] == 1 && !visited[newRow][newCol]) {
104                    deepFirstSearch(newRow, newCol);
105                } else if (isInfected[newRow][newCol] == 0) {
106                    // If the neighboring cell is uninfected, count it as a potential wall and add to the boundary
107                    wallCount.set(currentAreaIndex, wallCount.get(currentAreaIndex) + 1);
108                    areaBoundaries.get(currentAreaIndex).add(newRow * colCount + newCol);
109                }
110            }
111        }
112    }
113
114    // Utility method to check if a given position is within the boundaries of the grid
115    private boolean isValidPosition(int row, int col) {
116        return row >= 0 && row < rowCount && col >= 0 && col < colCount;
117    }
118}
119
1class Solution {
2    vector<int> directions = {-1, 0, 1, 0, -1}; // Delta values for row and column for 4 directions (up, right, down, left).
3    vector<int> wallCounts; // Counts of walls needed for each region.
4    vector<vector<int>> regions; // 2D vector to store the regions marked as affected.
5    vector<unordered_set<int>> boundaries; // Contains the boundaries of each region.
6    vector<vector<int>> grid; // To represent whether a cell is infected or not.
7    vector<vector<bool>> visited; // Indicates if the cell has been visited already.
8    int rows; // Total rows in the grid.
9    int cols; // Total columns in the grid.
10
11    int containVirus(vector<vector<int>>& isInfected) {
12        grid = isInfected;
13        rows = grid.size();
14        cols = grid[0].size();
15        visited.assign(rows, vector<bool>(cols)); // Initializes the visited matrix
16        int totalWalls = 0; // Total walls built to contain the virus.
17
18        while (true) {
19            resetState(); // Reset state for the next iteration.
20
21            // Identify regions and their boundaries.
22            for (int r = 0; r < rows; ++r) {
23                for (int c = 0; c < cols; ++c) {
24                    if (grid[r][c] == 1 && !visited[r][c]) {
25                        wallCounts.push_back(0);
26                        regions.push_back({});
27                        boundaries.push_back({});
28                        depthFirstSearch(r, c);
29                    }
30                }
31            }
32
33            // If there are no regions left, break the loop.
34            if (regions.empty()) break;
35
36            // Get index of the region with the most threatening boundary.
37            int index = getMaxBoundaryIndex();
38            totalWalls += wallCounts[index];
39            implementQuarantine(index);
40
41        }
42        return totalWalls;
43    }
44
45    void resetState() { // Helper function to reset state for the next iteration.
46        for (int i = 0; i < rows; ++i)
47            for (int j = 0; j < cols; ++j)
48                visited[i][j] = false;
49        wallCounts.clear();
50        regions.clear();
51        boundaries.clear();
52    }
53
54    int getMaxBoundaryIndex() { // Helper function to get the region with the largest boundary.
55        int index = 0;
56        int maxBoundarySize = boundaries[0].size();
57        for (int i = 1; i < boundaries.size(); ++i) {
58            int currentSize = boundaries[i].size();
59            if (maxBoundarySize < currentSize) {
60                maxBoundarySize = currentSize;
61                index = i;
62            }
63        }
64        return index;
65    }
66
67    void implementQuarantine(int quarantineIndex) { // Quarantine the most dangerous region and allow others to spread.
68        for (int t = 0; t < regions.size(); ++t) {
69            if (t == quarantineIndex) {
70                for (int v : regions[t]) {
71                    int r = v / cols, c = v % cols;
72                    grid[r][c] = -1; // Mark the quarantined region.
73                }
74            } else {
75                spreadVirus(t); // Allow the virus to spread from the other regions.
76            }
77        }
78    }
79
80    void spreadVirus(int regionIndex) { // Helper function to let the virus spread from a given region.
81        for (int v : regions[regionIndex]) {
82            int r = v / cols, c = v % cols;
83            for (int d = 0; d < 4; ++d) {
84                int newX = r + directions[d], newY = c + directions[d + 1];
85                if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && grid[newX][newY] == 0)
86                    grid[newX][newY] = 1; // Infect adjacent uninfected cells.
87            }
88        }
89    }
90
91    void depthFirstSearch(int i, int j) { // DFS to mark the regions and their boundaries.
92        visited[i][j] = true;
93        regions.back().push_back(i * cols + j);
94        for (int d = 0; d < 4; ++d) {
95            int newX = i + directions[d], newY = j + directions[d + 1];
96            if (newX >= 0 && newX < rows && newY >= 0 && newY < cols) {
97                if (grid[newX][newY] == 1 && !visited[newX][newY])
98                    depthFirstSearch(newX, newY);
99                else if (grid[newX][newY] == 0) {
100                    wallCounts.back() += 1;
101                    boundaries.back().insert(newX * cols + newY); // Add uninfected adjacent cells to the boundary.
102                }
103            }
104        }
105    }
106};
107
1// Directions array to move in the grid (up, right, down, left).
2const directions: number[] = [-1, 0, 1, 0, -1];
3// Array to keep track of the number of walls required for each region.
4let wallCounts: number[] = [];
5// 2D array to keep track of infected regions.
6let regions: number[][] = [];
7// Array of sets, each containing the boundaries of the corresponding region.
8let boundaries: Set<number>[] = [];
9// 2D grid to represent the infected cells.
10let grid: number[][] = [];
11// 2D array to keep track if a cell has been visited.
12let visited: boolean[][] = [];
13// The number of rows in the grid.
14let rows: number;
15// The number of columns in the grid.
16let cols: number;
17
18// Function to contain the virus in the grid.
19function containVirus(isInfected: number[][]): number {
20    grid = isInfected;
21    rows = grid.length;
22    cols = grid[0].length;
23    visited = Array.from(Array(rows), () => new Array(cols).fill(false));
24    let totalWalls: number = 0;
25
26    while (true) {
27        resetState();
28
29        // Identify regions and their boundaries.
30        for (let r = 0; r < rows; ++r) {
31            for (let c = 0; c < cols; ++c) {
32                if (grid[r][c] === 1 && !visited[r][c]) {
33                    wallCounts.push(0);
34                    regions.push([]);
35                    boundaries.push(new Set<number>());
36                    depthFirstSearch(r, c);
37                }
38            }
39        }
40
41        // Terminate the loop if no regions are left.
42        if (regions.length === 0) break;
43
44        // Get the region with the most threatening boundary.
45        let index: number = getMaxBoundaryIndex();
46        totalWalls += wallCounts[index];
47        implementQuarantine(index);
48    }
49    return totalWalls;
50}
51
52// Function to reset the state for the next iteration.
53function resetState(): void {
54    for (let i = 0; i < rows; ++i) {
55        for (let j = 0; j < cols; ++j) {
56            visited[i][j] = false;
57        }
58    }
59    wallCounts = [];
60    regions = [];
61    boundaries = [];
62}
63
64// Function to get the index of the region with the largest boundary.
65function getMaxBoundaryIndex(): number {
66    let index: number = 0;
67    let maxBoundarySize: number = boundaries[0].size;
68    for (let i = 1; i < boundaries.length; ++i) {
69        let currentSize = boundaries[i].size;
70        if (maxBoundarySize < currentSize) {
71            maxBoundarySize = currentSize;
72            index = i;
73        }
74    }
75    return index;
76}
77
78// Function to quarantine the most dangerous region and allow other regions to spread.
79function implementQuarantine(quarantineIndex: number): void {
80    for (let t = 0; t < regions.length; ++t) {
81        if (t === quarantineIndex) {
82            for (let v of regions[t]) {
83                let r = Math.floor(v / cols);
84                let c = v % cols;
85                grid[r][c] = -1; // Mark the cells as quarantined.
86            }
87        } else {
88            spreadVirus(t); // Allow the virus to spread in other regions.
89        }
90    }
91}
92
93// Function to let the virus spread from a given region.
94function spreadVirus(regionIndex: number): void {
95    for (let v of regions[regionIndex]) {
96        let r = Math.floor(v / cols);
97        let c = v % cols;
98        for (let d = 0; d < 4; ++d) {
99            let newX = r + directions[d];
100            let newY = c + directions[d + 1];
101            if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && grid[newX][newY] === 0) {
102                grid[newX][newY] = 1; // Infect adjacent uninfected cells.
103            }
104        }
105    }
106}
107
108// Depth-First Search function to identify infected regions and their boundaries.
109function depthFirstSearch(i: number, j: number): void {
110    visited[i][j] = true;
111    regions[regions.length - 1].push(i * cols + j);
112    for (let d = 0; d < 4; ++d) {
113        let newX = i + directions[d];
114        let newY = j + directions[d + 1];
115        if (newX >= 0 && newX < rows && newY >= 0 && newY < cols) {
116            if (grid[newX][newY] === 1 && !visited[newX][newY]) {
117                depthFirstSearch(newX, newY);
118            } else if (grid[newX][newY] === 0) {
119                wallCounts[wallCounts.length - 1]++;
120                boundaries[boundaries.length - 1].add(newX * cols + newY);
121            }
122        }
123    }
124}
125

Time and Space Complexity

The given Python code defines a Solution class with the method containVirus that implements a containment strategy for a virus spread simulation in a two-dimensional grid. The containment works by finding the infected region that threatens to contaminate the most uninfected cells and then putting a "wall" around that region to prevent its spread. The code uses a depth-first search (DFS) algorithm to find the infected regions and determine the area and boundaries for each of them.

Time Complexity

The time complexity of the algorithm can be analyzed by examining the operations in each significant block of the code:

  • The main loop (while 1) continues until there are no more regions to contain. In the worst case, where each region spreads every turn and is quarantined in the order of individual cells, the main loop can run m*n times, where m is the number of rows and n is the number of columns in the grid.

  • Inside the main loop, a nested loop iterates over each grid cell and potentially calls dfs for infected cells. This nested loop always iterates m*n times.

  • The DFS (dfs) performs a traversal of the infected areas. In the worst case, a complete traversal of the grid is performed if the entire grid becomes infected, which would be another m*n operations.

  • For each area, we also need to consider the boundaries and the updating of the isInfected grid cells. Each of these operations can again take up to m*n in the worst case when updating all cells.

Putting this all together, the worst-case time complexity is O((m*n)^2), since each call to DFS can traverse the entire grid, and we might be doing this for each cell.

Space Complexity

The space complexity of the algorithm is mainly determined by the storage needs:

  • The vis array which is of size m * n.
  • areas, boundaries, and c, all of which in the worst case can store information for every cell.
  • The dfs call stack, which in the worst case might need to go as deep as the number of cells in the grid, m*n.

Therefore, in the worst case, the space complexity of the code is O(m*n), reflecting the storage needed for the auxiliary data structures and the call stack for DFS in the scenario where the entire grid is part of a single connected region.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

LeetCode Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we

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