0211MediumDepth-First SearchBreadth-First SearchUnion-FindGraph Theory

Count the Sensor Meshes

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A field crew scatters n battery-powered sensors across a valley and reads off which pairs of them can hear each other over the radio. The readings arrive as an n x n grid linked, where linked[i][j] is 1 when sensor i and sensor j exchange packets straight across and 0 when they do not. Hearing is mutual, so the grid reads the same either way round, and every sensor hears itself, so the diagonal is all 1.

Traffic can be relayed. If sensor i reaches sensor j straight across, and sensor j reaches sensor k straight across, then anything sensor i sends can still land at sensor k by way of j, and chains of relays can run as long as they like.

Call a mesh a group of sensors that can all get traffic to one another over some chain of hops, and that cannot be widened: no sensor left outside the group is able to join in. A sensor that hears nobody at all forms a mesh on its own.

Return how many meshes the crew has deployed.

Examples

Example 1

Input: linked = [[1, 1, 0, 0, 0], [1, 1, 0, 1, 0], [0, 0, 1, 0, 1], [0, 1, 0, 1, 0], [0, 0, 1, 0, 1]]
Output: 2

Sensors 0, 1 and 3 sit in one mesh, since 0 gets traffic to 3 by way of 1. Sensors 2 and 4 hear each other and make up the other. All five sensors are accounted for.

Example 2

Input: linked = [[1, 1, 0, 1], [1, 1, 1, 0], [0, 1, 1, 1], [1, 0, 1, 1]]
Output: 1

Every sensor reaches every other one along the ring of hops 0-1, 1-2, 2-3, 3-0, so the four of them form a single mesh.

Example 3

Input: linked = [[1, 0, 1, 0, 0, 0], [0, 1, 0, 0, 1, 0], [1, 0, 1, 0, 0, 1], [0, 0, 0, 1, 0, 0], [0, 1, 0, 0, 1, 0], [0, 0, 1, 0, 0, 1]]
Output: 3

Sensors 0, 2 and 5 chain together, sensors 1 and 4 pair up, and sensor 3 hears nobody, which still counts as a mesh of one.

Constraints

1 <= n <= 200
n == linked.length
n == linked[i].length
linked[i][j] is 1 or 0.
linked[i][i] == 1
linked[i][j] == linked[j][i]

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def count_the_sensor_meshes(linked: list[list[int]]) -> int:

Java

public int countTheSensorMeshes(int[][] linked)

The intended approach

Time O(n^2)Space O(n)

Take the sensors in index order. Whenever one has not been reached yet, count a new mesh and walk out from it, driving the walk with an explicit stack: pop a sensor, scan its whole row, and push every partner not yet flagged, flagging it as it goes on so no sensor ever enters the stack twice. Each sensor is therefore popped once and has its row scanned once, and the count of walks started is the count of meshes.

Pythonentry point: count_the_sensor_meshes

def count_the_sensor_meshes(linked):
    # Time: O(n^2) -- each sensor is walked once and its row scanned once.
    # Space: O(n) -- the flag array and the walking stack.
    n = len(linked)
    reached = [False] * n
    meshes = 0
    for start in range(n):
        if reached[start]:
            continue
        meshes += 1
        reached[start] = True
        stack = [start]
        while stack:
            here = stack.pop()
            row = linked[here]
            for other in range(n):
                if row[other] == 1 and not reached[other]:
                    reached[other] = True
                    stack.append(other)
    return meshes

The obvious version

Spread reachability across the whole grid until nothing changes, so each row ends up listing everything that sensor can eventually reach, then count how many distinct rows are left.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_count_the_sensor_meshes(linked):
    n = len(linked)
    reach = [[linked[i][j] == 1 or i == j for j in range(n)] for i in range(n)]
    spreading = True
    while spreading:
        spreading = False
        for i in range(n):
            for k in range(n):
                if reach[i][k]:
                    for j in range(n):
                        if reach[k][j] and not reach[i][j]:
                            reach[i][j] = True
                            spreading = True
    groups = []
    for row in reach:
        if row not in groups:
            groups.append(row)
    return len(groups)

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in