Surrounded Regions - codepath/compsci_guides GitHub Wiki

Unit 11 Session 1 Standard (Click for link to problem statements)

Unit 11 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

💡 Difficulty: Medium
⏰ Time to complete: 45 mins
🛠️ Topics: Grid Traversal, Depth-First Search (DFS)

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

Established a set (2-3) of test cases to verify their own solution later.

Established a set (1-2) of edge cases to verify their solution handles complexities.

Have fully understood the problem and have no clarifying questions.

Have you verified any Time/Space Constraints for this problem?

How do we define a surrounded region?
- An 'O' region is surrounded if it is fully enclosed by 'X' cells and does not touch the edge of the matrix.
Can a region that touches the edge be captured?
- No, regions that touch the edges of the matrix cannot be captured, as they are not fully enclosed.
What should we do with the remaining 'O' regions after identifying the edge-connected regions?
- Replace surrounded 'O' regions with 'X', and restore any edge-connected 'O' regions.

HAPPY CASE
Input: map = [
    ['X', 'X', 'X', 'X'],
    ['X', 'O', 'O', 'X'],
    ['X', 'X', 'O', 'X'],
    ['X', 'O', 'X', 'X']
]
Output: [
    ['X', 'X', 'X', 'X'],
    ['X', 'X', 'X', 'X'],
    ['X', 'X', 'X', 'X'],
    ['X', 'O', 'X', 'X']
]
Explanation: The region in the middle is surrounded by 'X's and is therefore captured, while the region at the bottom is connected to the edge and cannot be captured.

EDGE CASE
Input: map = [
    ['X', 'X', 'X'],
    ['O', 'O', 'O'],
    ['X', 'X', 'X']
]
Output: [
    ['X', 'X', 'X'],
    ['O', 'O', 'O'],
    ['X', 'X', 'X']
]
Explanation: The middle region is connected to the top and bottom edges and thus cannot be captured.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Grid Traversal problems, we want to consider the following approaches:

Depth-First Search (DFS): DFS can be used to explore all 'O' regions connected to the edges and mark them as un-capturable.
Breadth-First Search (BFS): BFS could also be used to explore edge-connected 'O' regions, but DFS is simpler for marking regions recursively.
Boundary Check: Focus on edge-connected 'O' regions, as these cannot be captured.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

Use DFS to mark all 'O' regions connected to the edges of the matrix. These regions cannot be captured, so we mark them with a temporary marker 'T'.
After marking edge-connected regions, iterate through the grid and:
- Replace all remaining 'O' regions (which are fully surrounded) with 'X'.
- Restore 'T' regions back to 'O', as they are edge-connected and cannot be captured.

1) Define a helper function `next_moves` to get valid neighboring cells.
2) Define a DFS function to mark all edge-connected `'O'` regions with `'T'`.
3) Traverse the edges of the grid, and perform DFS from any `'O'` cells found on the edges.
4) Traverse the entire grid:
    a) Replace any remaining `'O'` regions with `'X'`.
    b) Restore any `'T'` regions back to `'O'`.
5) Return the modified grid.

⚠️ Common Mistakes

Forgetting to handle edge cases where the grid has no 'O' regions.
Not marking edge-connected 'O' regions properly, leading to incorrect captures.

4: I-mplement

Implement the code to solve the algorithm.

def capture(map):
    if not map or not map[0]:
        return
    
    rows, cols = len(map), len(map[0])

    # Adapted next_moves function for identifying valid neighboring cells
    def next_moves(map, row, column):
        moves = [
            (row + 1, column),  # down
            (row - 1, column),  # up
            (row, column + 1),  # right
            (row, column - 1)   # left
        ]
        
        possible = []
        for r, c in moves:
            if 0 <= r < rows and 0 <= c < cols and map[r][c] == 'O':
                possible.append((r, c))
        
        return possible
    
    # DFS to mark edge-connected 'O's as 'T'
    def dfs(row, col):
        stack = [(row, col)]
        map[row][col] = 'T'  # Mark as temporary
        while stack:
            r, c = stack.pop()
            for nr, nc in next_moves(map, r, c):
                if map[nr][nc] == 'O':
                    map[nr][nc] = 'T'  # Mark connected 'O's as 'T'
                    stack.append((nr, nc))
    
    # Step 1: Mark all 'O's connected to the edges
    for i in range(rows):
        if map[i][0] == 'O':
            dfs(i, 0)  # Left edge
        if map[i][cols - 1] == 'O':
            dfs(i, cols - 1)  # Right edge
    
    for j in range(cols):
        if map[0][j] == 'O':
            dfs(0, j)  # Top edge
        if map[rows - 1][j] == 'O':
            dfs(rows - 1, j)  # Bottom edge
    
    # Step 2: Flip remaining 'O's to 'X' and restore 'T's to 'O'
    for i in range(rows):
        for j in range(cols):
            if map[i][j] == 'O':
                map[i][j] = 'X'  # Capture surrounded regions
            elif map[i][j] == 'T':
                map[i][j] = 'O'  # Restore edge-connected regions

    return map

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Example 1:

Input: map = [ ['X', 'X', 'X', 'X'], ['X', 'O', 'O', 'X'], ['X', 'X', 'O', 'X'], ['X', 'O', 'X', 'X'] ]
Expected Output: [ ['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'O', 'X', 'X'] ]
Watchlist:
- Check that all edge-connected 'O' regions are marked correctly with 'T'.
- Ensure that all fully surrounded regions are captured.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume m is the number of rows and n is the number of columns in the grid.

Time Complexity: O(m * n) because each cell is visited at most twice (once during DFS and once during the final traversal).
Space Complexity: O(m * n) due to the stack used in DFS.