Heaps, Priority Queues & Graphs: Advanced Structures

# Heap stored as an array:
#
#           1           index 0
#          / \
#         3   5         index 1, 2
#        / \ / \
#       7  8 6  9       index 3, 4, 5, 6
#
# Array: [1, 3, 5, 7, 8, 6, 9]
#
# Parent of index 3 (value 7)? (3 - 1) // 2 = 1  (value 3) ✓
# Parent of index 5 (value 6)? (5 - 1) // 2 = 2  (value 5) ✓
# Left child of index 1 (value 3)? 2*1+1 = 3     (value 7) ✓
# Right child of index 1 (value 3)? 2*1+2 = 4    (value 8) ✓

heap = [1, 3, 5, 7, 8, 6, 9]

def parent(i: int) -> int:
    return (i - 1) // 2

def left_child(i: int) -> int:
    return 2 * i + 1

def right_child(i: int) -> int:
    return 2 * i + 2

# Verify heap property: every parent <= its children
def is_min_heap(arr: list) -> bool:
    """Check if array satisfies the min-heap property."""
    n = len(arr)
    for i in range(n):
        l = left_child(i)
        r = right_child(i)
        if l < n and arr[i] > arr[l]:
            return False
        if r < n and arr[i] > arr[r]:
            return False
    return True

print(is_min_heap([1, 3, 5, 7, 8, 6, 9]))   # True
print(is_min_heap([1, 3, 5, 2, 8, 6, 9]))   # False (2 < parent 3, but at index 3, parent is index 1 = 3, 2 < 3)

import heapq

# --- heapq.heappush(h, item) --- O(log n)
# Insert an item while maintaining the heap property
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 8)
heapq.heappush(h, 3)
print(h)  # [1, 3, 8, 5]  -- internal array (NOT sorted, just heap-valid)

# --- heapq.heappop(h) --- O(log n)
# Remove and return the minimum element
print(heapq.heappop(h))  # 1  (the minimum)
print(heapq.heappop(h))  # 3
print(h)                 # [5, 8]

# --- heapq.heapify(list) --- O(n)  in-place conversion (Floyd's algorithm)
data = [10, 4, 7, 1, 9, 2, 6]
heapq.heapify(data)
print(data)  # [1, 4, 2, 10, 9, 7, 6]  -- heap-valid min-heap

# --- heapq.heappushpop(h, item) --- O(log n)
# Push item, then pop and return the minimum. More efficient than push+pop.
h = [1, 3, 5]
heapq.heapify(h)
result = heapq.heappushpop(h, 2)
print(result)  # 1  (pushed 2, then popped the new min which is 1)
print(h)       # [2, 3, 5]

# --- heapq.heapreplace(h, item) --- O(log n)
# Pop and return the minimum, then push item. Raises IndexError if empty.
# Faster than heappop + heappush because it avoids one sift-up.
h = [1, 3, 5]
heapq.heapify(h)
result = heapq.heapreplace(h, 4)
print(result)  # 1  (popped min, then pushed 4)
print(h)       # [3, 4, 5]

# --- heapq.nlargest(n, iterable, key=None) --- O(n log k)
# Return the k largest items (more efficient than sorted()[-k:] for small k)
scores = [88, 95, 72, 100, 63, 91, 77, 85]
print(heapq.nlargest(3, scores))         # [100, 95, 91]

students = [("Alice", 88), ("Bob", 95), ("Carol", 72), ("Dana", 100)]
print(heapq.nlargest(2, students, key=lambda s: s[1]))
# [('Dana', 100), ('Bob', 95)]

# --- heapq.nsmallest(n, iterable, key=None) --- O(n log k)
print(heapq.nsmallest(3, scores))        # [63, 72, 77]

# When to prefer nlargest/nsmallest over sorted():
# - If k << n: nlargest is O(n log k) vs sorted's O(n log n)
# - If k is close to n: just use sorted() -- it is faster overall

import heapq

# Max-heap via negation
max_heap = []
for value in [5, 1, 8, 3, 9, 2]:
    heapq.heappush(max_heap, -value)  # store negated

print(max_heap)  # [-9, -8, -5, -1, -3, -2] -- internally a min-heap of negatives

# Extract maximum: pop and negate
while max_heap:
    print(-heapq.heappop(max_heap), end=" ")
# 9 8 5 3 2 1  -- extracted in descending order

# Priority queue pattern: (priority, item) tuples
# Lower number = higher priority (min-heap pops smallest first)
task_queue = []
heapq.heappush(task_queue, (3, "low-priority task"))
heapq.heappush(task_queue, (1, "urgent task"))
heapq.heappush(task_queue, (2, "medium-priority task"))

while task_queue:
    priority, task = heapq.heappop(task_queue)
    print(f"Processing (priority {priority}): {task}")
# Processing (priority 1): urgent task
# Processing (priority 2): medium-priority task
# Processing (priority 3): low-priority task

# Tie-breaking with a counter for stable ordering
import itertools
counter = itertools.count()  # monotonically increasing counter

stable_queue = []
heapq.heappush(stable_queue, (2, next(counter), "first medium task"))
heapq.heappush(stable_queue, (2, next(counter), "second medium task"))
# Same priority? The counter ensures FIFO order between equal priorities.

class MinHeap:
    """A min-heap implemented over a Python list."""

    def __init__(self) -> None:
        self._data: list = []

    # --- Index helpers ---
    def _parent(self, i: int) -> int:
        return (i - 1) // 2

    def _left(self, i: int) -> int:
        return 2 * i + 1

    def _right(self, i: int) -> int:
        return 2 * i + 2

    # --- Core operations ---
    def push(self, val) -> None:
        """Insert val into the heap. O(log n)."""
        self._data.append(val)        # 1. Add at the end
        self._sift_up(len(self._data) - 1)  # 2. Restore heap property upward

    def pop(self) -> int:
        """Remove and return the minimum. O(log n)."""
        if not self._data:
            raise IndexError("Pop from empty heap")
        # Swap root with last element
        self._data[0], self._data[-1] = self._data[-1], self._data[0]
        minimum = self._data.pop()    # remove the old root (now at end)
        if self._data:
            self._sift_down(0)        # restore heap property downward
        return minimum

    def peek(self):
        """Return the minimum without removing it. O(1)."""
        if not self._data:
            raise IndexError("Peek at empty heap")
        return self._data[0]

    def __len__(self) -> int:
        return len(self._data)

    # --- Heap property restoration ---
    def _sift_up(self, i: int) -> None:
        """Bubble element at index i upward until heap property is restored.

        Visual: newly inserted element at the bottom competes with its parent.
        If it is smaller, they swap. This repeats until the element reaches
        its correct position or the root.

        Before: [1, 3, 5, 7, 8, 6, 9, 2]  (2 just inserted at index 7)
                                        ^
        Step 1: parent(7)=3 has value 7. 2 < 7 → swap
                [1, 3, 5, 2, 8, 6, 9, 7]
        Step 2: parent(3)=1 has value 3. 2 < 3 → swap
                [1, 2, 5, 3, 8, 6, 9, 7]
        Step 3: parent(1)=0 has value 1. 2 > 1 → stop
        """
        while i > 0:
            p = self._parent(i)
            if self._data[i] < self._data[p]:
                self._data[i], self._data[p] = self._data[p], self._data[i]
                i = p
            else:
                break

    def _sift_down(self, i: int) -> None:
        """Bubble element at index i downward until heap property is restored.

        Visual: after removing the root, the last element is placed at the top.
        It then competes with its smaller child, swapping downward until correct.

        Before: [9, 3, 5, 7, 8, 6]  (9 was placed at root after pop)
        Step 1: children of 0 are index 1 (value 3) and index 2 (value 5).
                Smaller child is 3. 9 > 3 → swap.
                [3, 9, 5, 7, 8, 6]
        Step 2: children of 1 are index 3 (value 7) and index 4 (value 8).
                Smaller child is 7. 9 > 7 → swap.
                [3, 7, 5, 9, 8, 6]
        Step 3: children of 3 are index 7, 8 -- out of bounds. Stop.
        """
        n = len(self._data)
        while True:
            smallest = i
            l = self._left(i)
            r = self._right(i)
            if l < n and self._data[l] < self._data[smallest]:
                smallest = l
            if r < n and self._data[r] < self._data[smallest]:
                smallest = r
            if smallest == i:
                break  # heap property satisfied
            self._data[i], self._data[smallest] = self._data[smallest], self._data[i]
            i = smallest

    def heapify(self, arr: list) -> None:
        """Build a heap from an unordered list in O(n) using Floyd's algorithm.

        Key insight: leaf nodes (indices n//2 to n-1) are already valid heaps
        of size 1. We only need to sift_down from the last internal node upward.
        This is O(n), NOT O(n log n) — most nodes are near the bottom and
        travel very short distances.
        """
        self._data = arr.copy()
        n = len(self._data)
        for i in range(n // 2 - 1, -1, -1):  # start from last internal node
            self._sift_down(i)

    def __repr__(self) -> str:
        return f"MinHeap({self._data})"


# --- Demo ---
h = MinHeap()
for v in [5, 3, 8, 1, 9, 2, 6]:
    h.push(v)

print(h)              # MinHeap([1, 3, 2, 5, 9, 8, 6])
print(h.peek())       # 1
print(h.pop())        # 1
print(h.pop())        # 2
print(h)              # MinHeap([3, 5, 6, 8, 9])

# Floyd's heapify -- O(n)
h2 = MinHeap()
h2.heapify([10, 4, 7, 1, 9, 2, 6])
print(h2)             # MinHeap([1, 4, 2, 10, 9, 7, 6])

# Extract sorted order (heap sort)
sorted_output = []
while len(h2):
    sorted_output.append(h2.pop())
print(sorted_output)  # [1, 2, 4, 6, 7, 9, 10]

import heapq
from dataclasses import dataclass, field
from typing import Any

# --- Pattern 1: Simple tuple-based priority queue ---
pq: list = []
heapq.heappush(pq, (1, "critical bug fix"))
heapq.heappush(pq, (3, "refactor module"))
heapq.heappush(pq, (2, "add new feature"))
heapq.heappush(pq, (1, "security patch"))  # same priority as critical bug

while pq:
    p, task = heapq.heappop(pq)
    print(f"[P{p}] {task}")
# [P1] critical bug fix
# [P1] security patch
# [P2] add new feature
# [P3] refactor module

# --- Pattern 2: Stable ordering with counter ---
import itertools
_counter = itertools.count()

def push_task(pq, priority, item):
    """Insert with tie-breaking counter for FIFO order among equal priorities."""
    heapq.heappush(pq, (priority, next(_counter), item))

# --- Pattern 3: queue.PriorityQueue (thread-safe wrapper over heapq) ---
from queue import PriorityQueue

thread_safe_pq = PriorityQueue()
thread_safe_pq.put((2, "task B"))
thread_safe_pq.put((1, "task A"))
thread_safe_pq.put((3, "task C"))

while not thread_safe_pq.empty():
    print(thread_safe_pq.get())
# (1, 'task A')
# (2, 'task B')
# (3, 'task C')

# --- Pattern 4: Max-priority queue (highest number = most important) ---
max_pq: list = []
for priority, task in [(3, "low"), (10, "urgent"), (7, "medium")]:
    heapq.heappush(max_pq, (-priority, task))  # negate priority

while max_pq:
    neg_p, task = heapq.heappop(max_pq)
    print(f"[P{-neg_p}] {task}")
# [P10] urgent
# [P7]  medium
# [P3]  low

import heapq

def kth_largest(nums: list[int], k: int) -> int:
    """Find the k-th largest element using a min-heap of size k.

    Strategy: maintain a min-heap of the k largest elements seen so far.
    The root of the heap is always the k-th largest.

    Why min-heap of size k? When the heap has k elements, its minimum
    (the root) is the k-th largest. Any new element larger than the root
    replaces it, maintaining the invariant.
    """
    min_heap: list[int] = []
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)  # discard smallest -- not in top-k
    return min_heap[0]  # root = k-th largest

print(kth_largest([3, 2, 1, 5, 6, 4], k=2))   # 5
print(kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], k=4))  # 4

import heapq

def merge_k_sorted(lists: list[list[int]]) -> list[int]:
    """Merge k sorted lists into one sorted list.

    Strategy: use a min-heap with (value, list_index, element_index).
    Always extract the global minimum efficiently.

    Time: O(n log k) where n = total elements, k = number of lists.
    """
    result: list[int] = []
    heap: list[tuple] = []

    # Initialize heap with the first element from each non-empty list
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))

    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        # Push the next element from the same list
        next_idx = elem_idx + 1
        if next_idx < len(lists[list_idx]):
            heapq.heappush(heap, (lists[list_idx][next_idx], list_idx, next_idx))

    return result

lists = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
print(merge_k_sorted(lists))  # [1, 2, 3, 4, 5, 6, 7, 8, 9]

import heapq
from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    """Return the k most frequent elements.

    Step 1: count frequencies with Counter — O(n)
    Step 2: use nlargest to find top-k — O(n log k)
    """
    counts = Counter(nums)
    return heapq.nlargest(k, counts, key=counts.get)

print(top_k_frequent([1, 1, 1, 2, 2, 3], k=2))     # [1, 2]
print(top_k_frequent([1, 2], k=2))                  # [1, 2]

import heapq

class MedianFinder:
    """Maintain a running median using two heaps.

    Strategy: split the stream into two halves.
    - lower_max_heap: max-heap of the lower half (stored negated)
    - upper_min_heap: min-heap of the upper half

    Invariant: lower_max_heap.size == upper_min_heap.size
               OR lower_max_heap.size == upper_min_heap.size + 1

    Median: if sizes equal -> average of both tops
            if lower is bigger -> lower's top
    """

    def __init__(self) -> None:
        self._lower: list[int] = []  # max-heap (negated values)
        self._upper: list[int] = []  # min-heap

    def add_num(self, num: int) -> None:
        """Add a number to the data structure. O(log n)."""
        # Push to lower half (negate for max-heap behavior)
        heapq.heappush(self._lower, -num)

        # Balance: lower's max must be <= upper's min
        if self._upper and (-self._lower[0]) > self._upper[0]:
            val = -heapq.heappop(self._lower)
            heapq.heappush(self._upper, val)

        # Rebalance sizes: lower can have at most 1 more element than upper
        if len(self._lower) > len(self._upper) + 1:
            val = -heapq.heappop(self._lower)
            heapq.heappush(self._upper, val)
        elif len(self._upper) > len(self._lower):
            val = heapq.heappop(self._upper)
            heapq.heappush(self._lower, -val)

    def find_median(self) -> float:
        """Return the current median. O(1)."""
        if len(self._lower) == len(self._upper):
            return (-self._lower[0] + self._upper[0]) / 2.0
        return float(-self._lower[0])  # lower has the extra element


mf = MedianFinder()
for n in [1, 2, 3, 4, 5]:
    mf.add_num(n)
    print(f"After adding {n}: median = {mf.find_median()}")
# After adding 1: median = 1.0
# After adding 2: median = 1.5
# After adding 3: median = 2.0
# After adding 4: median = 2.5
# After adding 5: median = 3.0

from collections import defaultdict

# --- Adjacency List (best for sparse graphs) ---
# Space: O(V + E)
# Check if edge exists: O(degree(v))
# Iterate all neighbors: O(degree(v))

graph_list: dict[str, list[str]] = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

# Weighted adjacency list: {node: [(neighbor, weight)]}
weighted_graph: dict[str, list[tuple[str, int]]] = {
    "A": [("B", 4), ("C", 2)],
    "B": [("A", 4), ("D", 3), ("E", 1)],
    "C": [("A", 2), ("F", 5)],
    "D": [("B", 3)],
    "E": [("B", 1), ("F", 2)],
    "F": [("C", 5), ("E", 2)],
}

# --- Adjacency Matrix (best for dense graphs) ---
# Space: O(V^2)
# Check if edge exists: O(1)
# Iterate all neighbors: O(V)

# For vertices ["A", "B", "C", "D"]
# Row i = from vertex i, Col j = to vertex j
adj_matrix = [
    [0, 1, 1, 0],  # A -> B, C
    [1, 0, 0, 1],  # B -> A, D
    [1, 0, 0, 0],  # C -> A
    [0, 1, 0, 0],  # D -> B
]

# --- Edge List (simple, used in Kruskal's MST) ---
edges: list[tuple[str, str, int]] = [
    ("A", "B", 4),
    ("A", "C", 2),
    ("B", "D", 3),
    ("C", "F", 5),
]

from collections import deque

def bfs(graph: dict, start: str) -> list[str]:
    """Breadth-first search: explores level by level. O(V+E).

    Uses a queue (FIFO). Guarantees shortest path in unweighted graphs.
    """
    visited: set[str] = {start}
    queue: deque[str] = deque([start])
    order: list[str] = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order


def bfs_shortest_path(graph: dict, start: str, end: str) -> list[str] | None:
    """BFS to find the shortest path (fewest edges) between two nodes.

    Track the predecessor of each visited node to reconstruct the path.
    """
    if start == end:
        return [start]

    visited: set[str] = {start}
    queue: deque[list[str]] = deque([[start]])  # queue of paths

    while queue:
        path = queue.popleft()
        node = path[-1]
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                new_path = path + [neighbor]
                if neighbor == end:
                    return new_path
                visited.add(neighbor)
                queue.append(new_path)

    return None  # no path exists


def dfs_iterative(graph: dict, start: str) -> list[str]:
    """Depth-first search (iterative, using explicit stack). O(V+E).

    Goes as deep as possible before backtracking. Useful for cycle
    detection, topological sort, and finding all connected components.
    """
    visited: set[str] = set()
    stack: list[str] = [start]
    order: list[str] = []

    while stack:
        node = stack.pop()  # LIFO: go deep first
        if node not in visited:
            visited.add(node)
            order.append(node)
            for neighbor in reversed(graph.get(node, [])):
                if neighbor not in visited:
                    stack.append(neighbor)

    return order


def dfs_recursive(graph: dict, start: str,
                  visited: set | None = None) -> list[str]:
    """Depth-first search (recursive). O(V+E).

    Cleaner than iterative for problems that naturally recurse,
    like finding all paths or generating combinations.
    """
    if visited is None:
        visited = set()
    visited.add(start)
    order = [start]
    for neighbor in graph.get(start, []):
        if neighbor not in visited:
            order.extend(dfs_recursive(graph, neighbor, visited))
    return order


# Example graph
#  A -- B -- D
#  |    |
#  C -- F -- E
g = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

print("BFS from A:", bfs(g, "A"))                       # A, B, C, D, E, F
print("DFS from A:", dfs_iterative(g, "A"))             # A, B, D, E, F, C
print("Shortest A→F:", bfs_shortest_path(g, "A", "F"))  # ['A', 'C', 'F']

from collections import deque

def topological_sort_kahn(graph: dict[str, list[str]]) -> list[str] | None:
    """Kahn's algorithm: BFS-based topological sort. O(V+E).

    Repeatedly removes nodes with no incoming edges (in-degree 0).
    If not all nodes are removed, a cycle exists.
    """
    # Count incoming edges (in-degree) for each node
    in_degree: dict[str, int] = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] = in_degree.get(neighbor, 0) + 1

    # Start with all nodes that have no prerequisites
    queue: deque[str] = deque(n for n, d in in_degree.items() if d == 0)
    order: list[str] = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # If order doesn't contain all nodes, a cycle was detected
    return order if len(order) == len(graph) else None


def topological_sort_dfs(graph: dict[str, list[str]]) -> list[str] | None:
    """DFS-based topological sort (Tarjan's algorithm). O(V+E).

    Each node has 3 states: unvisited (0), in-progress (1), done (2).
    If we encounter an in-progress node, there is a cycle.
    """
    state: dict[str, int] = {n: 0 for n in graph}
    stack: list[str] = []
    has_cycle = False

    def dfs(node: str) -> None:
        nonlocal has_cycle
        if has_cycle:
            return
        state[node] = 1  # in progress
        for neighbor in graph.get(node, []):
            if state[neighbor] == 1:  # back edge = cycle
                has_cycle = True
                return
            if state[neighbor] == 0:
                dfs(neighbor)
        state[node] = 2  # done
        stack.append(node)  # add to result AFTER processing all deps

    for node in graph:
        if state[node] == 0:
            dfs(node)

    return None if has_cycle else stack[::-1]


# Course prerequisite example:
# CS101 → CS201 → CS301
#       ↘         ↗
#         CS202
prereqs: dict[str, list[str]] = {
    "CS101": ["CS201", "CS202"],
    "CS201": ["CS301"],
    "CS202": ["CS301"],
    "CS301": [],
}

print("Kahn's order:", topological_sort_kahn(prereqs))
# ['CS101', 'CS201', 'CS202', 'CS301'] or similar valid order
print("DFS order:", topological_sort_dfs(prereqs))

class UnionFind:
    """Disjoint Set Union with path compression and union by rank.

    After applying both optimizations:
    - find: O(α(n)) ≈ O(1) amortized (α is the inverse Ackermann function)
    - union: O(α(n)) ≈ O(1) amortized
    """

    def __init__(self, n: int) -> None:
        """Initialize n separate singleton sets."""
        self.parent: list[int] = list(range(n))  # each node is its own root
        self.rank: list[int] = [0] * n            # tree height upper bound
        self.components: int = n                  # number of distinct sets

    def find(self, x: int) -> int:
        """Find the root representative of x's set.

        Path compression: after finding the root, point every node on the
        path directly to the root. Future find() calls will be O(1).
        """
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        """Merge the sets containing x and y.

        Union by rank: attach the shorter tree under the taller one.
        This keeps trees shallow, making find() fast.

        Returns True if they were in different sets (a merge happened).
        """
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False  # already in the same set

        # Attach smaller rank tree under larger rank tree
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1

        self.components -= 1
        return True

    def connected(self, x: int, y: int) -> bool:
        """Check if x and y are in the same set."""
        return self.find(x) == self.find(y)


# --- Number of islands using Union-Find ---
def count_islands(grid: list[list[str]]) -> int:
    """Count connected land masses ('1') in a 2D grid. O(m*n * α(m*n))."""
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    uf = UnionFind(rows * cols)
    land_cells = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                land_cells += 1
                idx = r * cols + c
                for dr, dc in [(0, 1), (1, 0)]:  # only right and down to avoid duplicates
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":
                        uf.union(idx, nr * cols + nc)

    # Count unique roots among land cells
    return len({uf.find(r * cols + c)
                for r in range(rows)
                for c in range(cols)
                if grid[r][c] == "1"})


grid = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"],
]
print(count_islands(grid))  # 3