Reinforce the Kingdom's Strongholds - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 50 mins
  • 🛠️ Topics: Union Find, Graph 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?
  • What is the goal of the problem?
    • The goal is to remove the maximum number of strongholds while maintaining at least one stronghold per row and column.
  • How is a stronghold removed?
    • A stronghold can be removed if there is another stronghold in the same row or column.
HAPPY CASE
Input: 
    strongholds = [0,0], [0,1], [1,0], [1,2], [2,1], [2,2](/codepath/compsci_guides/wiki/0,0],-[0,1],-[1,0],-[1,2],-[2,1],-[2,2)
Output: 
    5
Explanation:
    5 strongholds can be removed while maintaining at least one stronghold per row and column.

EDGE CASE
Input: 
    strongholds = [0,0](/codepath/compsci_guides/wiki/0,0)
Output: 
    0
Explanation:
    No strongholds can be removed since there is only one stronghold.

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

  • Union-Find: This problem involves grouping connected components (strongholds in the same row or column), which is efficiently handled by the Union-Find (Disjoint Set Union) technique.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use the Union-Find data structure to group strongholds that share the same row or column. Once grouped, the number of removable strongholds is the total number of strongholds minus the number of connected components (i.e., distinct groups).

Steps:

  1. Union-Find Initialization:

    • Create a Union-Find data structure to track connected components.
    • Use a row_map and col_map to keep track of the last stronghold seen in each row and column.

  2. Union Connected Strongholds:

    • For each stronghold, union it with the last stronghold seen in its row and column (if applicable).

  3. Count Removable Strongholds:

    • The number of removable strongholds is the total number of strongholds minus the number of distinct connected components.

4: I-mplement

Implement the code to solve the algorithm.

class UnionFind:
    def __init__(self):
        self.parent = {}
        self.rank = {}
        self.count = 0  # Count of distinct components
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]
    
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        
        if rootX != rootY:
            # Union by rank
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1
            self.count -= 1  # Merging two components reduces the component count
    
    def add(self, x):
        if x not in self.parent:
            self.parent[x] = x
            self.rank[x] = 0
            self.count += 1

def reinforce_strongholds(strongholds):
    uf = UnionFind()
    
    row_map = {}
    col_map = {}
    
    for x, y in strongholds:
        # Add the stronghold to UnionFind
        uf.add((x, y))
        
        # Union strongholds that share the same row
        if x in row_map:
            uf.union((x, y), (x, row_map[x]))
        row_map[x] = y
        
        # Union strongholds that share the same column
        if y in col_map:
            uf.union((x, y), (col_map[y], y))
        col_map[y] = x
    
    # The number of removable strongholds is the total number of strongholds
    # minus the number of unique connected components.
    return len(strongholds) - 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: strongholds = [0,0], [0,1], [1,0], [1,2], [2,1], 2,2
  • Expected Output: 5

Example 2:

  • Input: strongholds = [0,0], [0,2], [1,1], [2,0], 2,2
  • Expected Output: 3

Example 3:

  • Input: strongholds = 0,0
  • Expected Output: 0

6: E-valuate

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

Assume n is the number of strongholds.

  • Time Complexity: O(n log n) due to Union-Find operations (find and union) being nearly constant time (amortized O(log n) due to path compression).
  • Space Complexity: O(n) to store the Union-Find structure and maps for rows and columns.