Number of Survival Camps - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 30 mins
  • 🛠️ Topics: Union Find, Connected Components

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?
  • What is a survival camp in this context?
    • A camp is a group of connected 1s that are adjacent either vertically or horizontally.
  • How are the camps counted?
    • Camps are isolated groups of 1s, and the goal is to return the number of such groups (connected components).
HAPPY CASE
Input: city = [
  [1,1,1,1,0],
  [1,1,0,1,0],
  [1,1,0,0,0],
  [0,0,0,0,0]
]
Output: 1
Explanation: There is only one survival camp because all the `1`s are connected.

EDGE CASE
Input: city = [
  [1,1,0,0,0],
  [1,1,0,0,0],
  [0,0,1,0,0],
  [0,0,0,1,1]
]
Output: 3
Explanation: There are three survival camps, formed by groups of `1`s that are disconnected from each other.

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 Connected Components problems, we want to consider the following approaches:

  • Union-Find (Disjoint Set Union): We can use Union-Find to group connected components of 1s and count how many disjoint sets (survival camps) there are.
  • Grid Traversal: Instead of a DFS/BFS traversal of the grid, we will use Union-Find to efficiently manage merging adjacent cells that are part of the same camp.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a Union-Find (Disjoint Set Union) structure to group connected 1s into distinct components. Initially treat each 1 as a separate camp, then union adjacent 1s into larger connected camps.

1) Initialize the Union-Find structure with `m * n` elements, where `m` is the number of rows and `n` is the number of columns.
2) Traverse the grid and treat each `1` as a potential camp. For each cell with a `1`, union it with its adjacent `1`s (either down or right).
3) Use Union-Find’s `find` and `union` operations to group connected components.
4) Return the total number of distinct camps.

⚠️ Common Mistakes

  • Forgetting to initialize each 1 as its own component (camp).
  • Not correctly mapping the 2D grid coordinates to the 1D array used by Union-Find.

4: I-mplement

Implement the code to solve the algorithm.

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))  # Initially, each element is its own parent
        self.rank = [1] * size  # The rank is initially 1 for all elements
        self.count = 0  # The number of distinct sets (camps)
    
    def find(self, p):
        if self.parent[p] != p:
            self.parent[p] = self.find(self.parent[p])  # Path compression
        return self.parent[p]
    
    def union(self, p, q):
        rootP = self.find(p)
        rootQ = self.find(q)
        
        if rootP != rootQ:
            # Union by rank
            if self.rank[rootP] > self.rank[rootQ]:
                self.parent[rootQ] = rootP
            elif self.rank[rootP] < self.rank[rootQ]:
                self.parent[rootP] = rootQ
            else:
                self.parent[rootQ] = rootP
                self.rank[rootP] += 1
            self.count -= 1  # Decrease the count when two camps are merged

    def add_camp(self):
        self.count += 1  # Add a new distinct camp

# Main function to count the number of survival camps
def num_camps(city):
    if not city:
        return 0
    
    m, n = len(city), len(city[0])
    
    # Initialize UnionFind structure
    uf = UnionFind(m * n)
    
    # Iterate through the grid
    for row in range(m):
        for col in range(n):
            if city[row][col] == 1:
                # Map the 2D grid to a 1D array index
                index = row * n + col
                uf.add_camp()  # Each 1 is initially treated as a separate camp
                
                # Check the neighboring cells (up, down, left, right) and union them if they are also camps (1s)
                for dr, dc in [(1, 0), (0, 1)]:  # Only check down and right to avoid revisiting cells
                    new_row, new_col = row + dr, col + dc
                    if 0 <= new_row < m and 0 <= new_col < n and city[new_row][new_col] == 1:
                        new_index = new_row * n + new_col
                        uf.union(index, new_index)  # Union the current camp with the neighbor camp
    
    return uf.count

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: city = [ [1,1,1,1,0], [1,1,0,1,0], [1,1,0,0,0], [0,0,0,0,0] ]
  • Expected Output: 1
  • Watchlist:
    • Ensure that the Union-Find structure correctly groups all adjacent 1s into one component.
    • Verify that the count reflects the total number of distinct camps.

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 * α(m * n)), where α is the inverse Ackermann function (very slow-growing) because of the Union-Find operations with path compression.
  • Space Complexity: O(m * n) due to the Union-Find data structure.