Surveying the Kingdom - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 45 mins
• 🛠️ Topics: Grid Traversal, DFS/BFS

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 are the farmland groups identified?
  • A farmland group is a rectangular region of 1s that are connected, and no two groups are adjacent to each other.
• What should the output format be?
  • For each farmland group, return a 4-length array representing the top-left and bottom-right corners.

HAPPY CASE
Input: land = [
    [1, 0, 0],
    [1, 0, 1],
    [1, 1, 1]
]
Output: [
    [0, 0, 2, 0],
    [1, 2, 2, 2]
]
Explanation: There are two farmland groups:
- The first group starts at (0,0) and ends at (2,0).
- The second group starts at (1,2) and ends at (2,2).

EDGE CASE
Input: land = [
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 0]
]
Output: []
Explanation: There are no farmland groups in this case.

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:

• DFS/BFS: We need to explore all connected farmland (1s) in the grid to identify the boundaries of each rectangular plot.
• Boundary Detection: For each unvisited farmland cell, we need to find the farthest row and column that forms the bottom-right corner of the rectangle.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Perform DFS/BFS starting from each unvisited farmland cell to determine the boundaries of the rectangular plot. After finding the boundaries, mark all cells within the rectangle as visited to avoid revisiting them.

1) Define a helper function `find_bottom_right` that, starting from the top-left corner, expands downward and rightward to find the bottom-right corner of the farmland group.
2) Initialize a set to keep track of visited cells.
3) Traverse the grid. For each unvisited farmland cell (`1`):
    a) Call `find_bottom_right` to determine the bottom-right corner of the farmland group.
    b) Mark all cells within the rectangle as visited.
    c) Add the coordinates of the top-left and bottom-right corners to the result.
4) Return the list of farmland groups.

⚠️ Common Mistakes

• Forgetting to mark cells within a farmland group as visited, leading to redundant exploration.
• Not properly handling edge cases where the grid contains no farmland.

4: I-mplement

Implement the code to solve the algorithm.

# Helper function to find the bottom-right corner of the farmland group
def find_bottom_right(land, row, col, visited):
    max_row, max_col = row, col
    
    # Expand downward to find the last row of the rectangle
    while max_row + 1 < len(land) and land[max_row + 1][col] == 1:
        max_row += 1
    
    # Expand rightward to find the last column of the rectangle
    while max_col + 1 < len(land[0]) and land[row][max_col + 1] == 1:
        max_col += 1
    
    # Mark the entire rectangle as visited
    for r in range(row, max_row + 1):
        for c in range(col, max_col + 1):
            visited.add((r, c))
    
    return max_row, max_col

# Main function to find all farmland groups
def find_farmland_groups(land):
    visited = set()
    farmland_groups = []
    
    for row in range(len(land)):
        for col in range(len(land[0])):
            # If we find an unvisited farmland cell, we have the top-left corner of a new group
            if land[row][col] == 1 and (row, col) not in visited:
                bottom_right_row, bottom_right_col = find_bottom_right(land, row, col, visited)
                # Record the farmland group's top-left and bottom-right corners
                farmland_groups.append([row, col, bottom_right_row, bottom_right_col])
    
    return farmland_groups

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: land = [ [1, 0, 0], [1, 0, 1], [1, 1, 1] ]
• Expected Output: [ [0, 0, 2, 0], [1, 2, 2, 2] ]
• Watchlist:
  • Ensure that find_bottom_right correctly identifies the boundaries of each farmland group.
  • Verify that all cells within a group are marked as visited.

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 once while marking the farmland group.
• Space Complexity: O(m * n) due to the visited set and recursive DFS/BFS calls.