Number of Towns - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 45 mins
  • 🛠️ Topics: Union Find, Grid Traversal

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 towns defined in this map?
    • A town is a group of adjacent urban land squares (1's) connected horizontally or vertically.
  • Can we assume that the grid is surrounded by rural land?
    • Yes, the map is surrounded by rural land (0's).
  • What should be returned if there is no town in the map?
    • Return 0.
HAPPY CASE
Input: kingdom_map = [
    [""""1"""", """"1"""", """"1"""", """"1"""", """"0""""],
    [""""1"""", """"1"""", """"0"""", """"1"""", """"0""""],
    [""""1"""", """"1"""", """"0"""", """"0"""", """"0""""],
    [""""0"""", """"0"""", """"0"""", """"0"""", """"0""""]
]
Output: 1
Explanation: All the urban land squares are connected to each other, so there is only one distinct town.

EDGE CASE
Input: kingdom_map = [
    [""""0"""", """"0"""", """"0"""", """"0"""", """"0""""]
]
Output: 0
Explanation: There are no urban land squares in the grid, so there are no towns.

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

  • Union Find (Disjoint Set): Efficiently group connected components by merging them.
  • DFS/BFS Traversal: Can also be used to explore connected urban lands, but Union Find is more efficient here for larger grids.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use Union Find to group connected urban land squares (1's) into towns. Each distinct connected component will be a separate town.

1) Initialize a Union Find structure to manage all the cells in the grid.
2) Traverse the grid, and for each urban land square (1):
    a) Add it as a new town in the Union Find structure.
    b) Union it with any adjacent urban squares (right, down).
3) After processing the entire grid, count the distinct towns using the Union Find structure.
4) Return the number of distinct towns.

⚠️ Common Mistakes

  • Forgetting to union adjacent cells in both rightward and downward directions.
  • Not handling edge cases where there are no urban squares (1's) in the grid.

4: I-mplement

Implement the code to solve the algorithm.

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [1] * size  # Rank is used to optimize union by rank
        self.count = 0  # Track the number of distinct sets (towns)

    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 number of distinct sets

    def add_town(self):
        self.count += 1  # Increase the number of distinct sets (towns)

    def total_towns(self):
        return self.count


def count_towns(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    uf = UnionFind(rows * cols)

    def get_index(r, c):
        return r * cols + c

    # Traverse the grid and perform union operations on adjacent urban lands (1's)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == ""1"":
                # Mark the cell as a part of a new town
                uf.add_town()
                
                # Union with the right cell if it's also ""1""
                if c + 1 < cols and grid[r][c + 1] == ""1"":
                    uf.union(get_index(r, c), get_index(r, c + 1))
                
                # Union with the cell below if it's also ""1""
                if r + 1 < rows and grid[r + 1][c] == ""1"":
                    uf.union(get_index(r, c), get_index(r + 1, c))

    # After traversing the grid, count distinct town roots
    town_roots = set()
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == ""1"":
                town_roots.add(uf.find(get_index(r, c)))

    return len(town_roots)

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: kingdom_map = [ [""""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 all urban land squares are correctly grouped into the same town.

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) since we visit each cell once and perform union/find operations.
  • Space Complexity: O(m * n) for storing the Union Find structure.