36. Count Duplicate Ticket Clusters

Problem

A dedup job lays tickets out on a 2D grid and flags pairwise "duplicate/related" relationships between a ticket and its immediate grid-neighbors: a 1 at position (r, c) means that ticket is related to whichever of its up/down/left/right neighbors are also flagged 1. Given the grid, count the number of distinct connected clusters of related tickets (0s are unrelated filler and never join a cluster).

Cells are connected only orthogonally (up/down/left/right), not diagonally. This is the classic "Number of Islands" problem, reframed around clustering duplicate support tickets instead of counting land masses.

Source: src/36_count_duplicate_ticket_clusters.py

def count_clusters(grid: list[list[int]]) -> int:

>>> count_clusters([[1,1,0,0],[1,1,0,0],[0,0,1,0],[0,0,0,1]])
3
>>> count_clusters([[1,0,1],[0,1,0],[1,0,1]])
5

Step-by-Step Approach

1. Handle the empty-grid edge case up front: an empty grid or a grid with empty rows has zero clusters.
2. Track which cells have been visited (either a separate boolean grid, or mutate the input grid in place by zeroing out visited 1s).
3. Scan every cell in row-major order. Whenever you find a 1 that hasn't been visited yet, that's the top-left-most cell of a brand new cluster: increment the cluster count.
4. From that seed cell, flood-fill outward to mark every orthogonally-connected 1 as visited, so the outer scan never counts the same cluster twice.
5. Use an explicit stack (or queue) for the flood fill rather than naive recursion, so a large, snake-like cluster can't blow the call stack.
6. At each popped cell, check its four neighbors; push any in-bounds, unvisited 1 onto the stack and mark it visited immediately (mark-on-push, not mark-on-pop, to avoid pushing the same cell twice).
7. Continue the outer scan until every cell has been examined; return the accumulated cluster count.

The key insight is that "count connected components" only needs one flood fill per unvisited seed cell — visiting a cell is a one-time cost, so the whole scan-plus-fill process runs in O(rows × cols) time and space, no matter how the 1s are arranged.

Reference solution

def count_clusters(grid: list[list[int]]) -> int:
    # flood-fill each unvisited 1 with an iterative stack, marking visited in place; O(rows*cols) time and space
    # catches [] and [[]] via falsy-empty-list check
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    # comprehension avoids aliased rows
    visited = [[False] * cols for _ in range(rows)]
    clusters = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and not visited[r][c]:
                clusters += 1
                visited[r][c] = True
                # LIFO stack for iterative DFS
                stack = [(r, c)]
                while stack:
                    cr, cc = stack.pop()
                    # 4 orthogonal offsets
                    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        nr, nc = cr + dr, cc + dc
                        # chained bounds check
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and not visited[nr][nc]:
                            visited[nr][nc] = True
                            stack.append((nr, nc))
    return clusters

Key Functions & Tricks

• not grid or not grid[0] — catches both empty rows and empty grid in one check.
• [[False] * cols for _ in range(rows)] — fresh rows to avoid aliasing bug from [[False] * cols] * rows.
• stack.append(...) / stack.pop() — list as LIFO stack for iterative DFS, no recursion limit risk.
• for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)) — unpack fixed offsets to enumerate 4 neighbors.
• 0 <= nr < rows and 0 <= nc < cols — chained comparison for a single-pass bounds check.

How to Recognize This Pattern