0379MediumArrayDepth-First SearchBreadth-First SearchMatrix

Rooftop Twin Drainage

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 flat roof is paved with square tiles laid out in a rows x cols grid. levels[r][c] is the height of the tile in row r, column c.

Rain that lands on a tile spreads to any tile sharing an edge with it whose height is the same or lower, and keeps spreading from there under the same rule. Two gutters collect the runoff:

the front gutter runs along the top row and the left column, so water standing on any tile of row 0 or column 0 is collected there;
the back gutter runs along the bottom row and the right column, so water standing on any tile of row rows - 1 or column cols - 1 is collected there.

A tile is twin-draining when rain landing on it can reach the front gutter and can also reach the back gutter. Return the coordinates [r, c] of every twin-draining tile. The coordinates may be listed in any order.

Examples

Example 1

Input: levels = [[4, 2, 7, 3], [3, 5, 6, 1], [8, 4, 2, 9], [2, 1, 3, 5]]
Output: [[0, 2], [0, 3], [1, 1], [1, 2], [2, 0], [3, 0]]

Tile [1, 1] stands at height 5. Water runs from it to [0, 1] at height 2, which lies in the top row and so reaches the front gutter, and it runs to [2, 1] and on to [3, 1], which lies in the bottom row and so reaches the back gutter.

Example 2

Input: levels = [[1, 5, 2], [4, 3, 6]]
Output: [[0, 1], [0, 2], [1, 0], [1, 2]]

Tile [1, 2] lies in the right column, and water runs from it to [0, 2] in the top row, so both gutters are reached. Tile [0, 0] lies in the top row, but both of its neighbours stand higher, so no water leaves it and the back gutter stays out of reach.

Example 3

Input: levels = [[9, 3, 9], [9, 3, 9], [9, 3, 9]]
Output: [[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]

From tile [1, 1] at height 3 the only tiles at the same height or lower are [0, 1] in the top row and [2, 1] in the bottom row, so both gutters are reached.

Example 4

Input: levels = [[7]]
Output: [[0, 0]]

The single tile lies in the top row and in the bottom row at once.

Constraints

rows == levels.length
cols == levels[r].length
1 <= rows, cols <= 200
0 <= levels[r][c] <= 10^5

The values you return may be in any order.

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 pacific_atlantic(levels: list[list[int]]) -> list[list[int]]:

Java

public List<List<Integer>> pacificAtlantic(int[][] levels)

The intended approach

Time O(rows * cols)Space O(rows * cols)

Instead of asking where the water on each tile ends up, ask which tiles can feed a given gutter. Seed a walk with every tile that touches the front gutter and move only to neighbours that are the same height or higher, which is exactly the reverse of the spreading rule; every tile the walk marks can send water to that gutter. Do the same for the back gutter and report the tiles marked by both walks. The walk is driven by an explicit stack, so a 200 x 200 grid cannot exhaust the interpreter's call depth.

Pythonentry point: pacific_atlantic

def pacific_atlantic(levels):
    # Time O(m * n) -- each tile is marked at most once per gutter.
    # Space O(m * n) for the two reachability grids, the explicit stack and the answer.
    rows = len(levels)
    cols = len(levels[0])
    steps = ((1, 0), (-1, 0), (0, 1), (0, -1))

    def uphill(seeds):
        seen = [[False] * cols for _ in range(rows)]
        stack = []
        for r, c in seeds:
            if not seen[r][c]:
                seen[r][c] = True
                stack.append((r, c))
        while stack:
            r, c = stack.pop()
            here = levels[r][c]
            for dr, dc in steps:
                nr = r + dr
                nc = c + dc
                if 0 <= nr < rows and 0 <= nc < cols and not seen[nr][nc]:
                    if levels[nr][nc] >= here:
                        seen[nr][nc] = True
                        stack.append((nr, nc))
        return seen

    front = uphill([(0, c) for c in range(cols)] + [(r, 0) for r in range(rows)])
    back = uphill([(rows - 1, c) for c in range(cols)] + [(r, cols - 1) for r in range(rows)])
    return [[r, c] for r in range(rows) for c in range(cols)
            if front[r][c] and back[r][c]]

The obvious version

Start a fresh forward flood from every tile, following the spreading rule downhill, and note whether that flood ever touches a front-gutter tile and a back-gutter tile. Quadratic in the number of tiles.

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_pacific_atlantic(levels):
    rows = len(levels)
    cols = len(levels[0])
    steps = ((1, 0), (-1, 0), (0, 1), (0, -1))
    out = []
    for sr in range(rows):
        for sc in range(cols):
            seen = {(sr, sc)}
            stack = [(sr, sc)]
            hits_front = False
            hits_back = False
            while stack:
                r, c = stack.pop()
                if r == 0 or c == 0:
                    hits_front = True
                if r == rows - 1 or c == cols - 1:
                    hits_back = True
                for dr, dc in steps:
                    nr = r + dr
                    nc = c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen:
                        if levels[nr][nc] <= levels[r][c]:
                            seen.add((nr, nc))
                            stack.append((nr, nc))
            if hits_front and hits_back:
                out.append([sr, sc])
    return out

How this problem was checked

Reference solution executed against 8 test cases — 8 passed
4 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