Road Continuation: Check if a Series of Road Segments Forms a Valid Continuous Path

Question

## Problem

You are given a list of road segments, each described as `[start, end]` (directed). Determine whether the segments can be arranged to form a single continuous path (each segment's end connects to the next segment's start).

Return `true` if such an arrangement exists, `false` otherwise. The path does not need to be a cycle.

```python
def is_continuous_path(segments: list[list[str]]) -> bool:
    # segments: [["A", "B"], ["C", "D"], ["B", "C"]]
    pass
```

**Example:**
```
Input:  [["A","B"],["C","D"],["B","C"]]
Output: true   (A->B->C->D)

Input:  [["A","B"],["C","D"],["X","Y"]]
Output: false  (no way to chain all three)
```

## Approach

Model segments as edges in a directed graph. A valid Eulerian path exists iff the graph is connected and at most one node has `out_degree - in_degree = 1` (start) and one has `in_degree - out_degree = 1` (end).

## Follow-ups

1. How would you reconstruct and return the actual ordered path?
2. What if segments are bidirectional (undirected roads)?
3. How does your approach scale to a map with millions of segments?
4. What if some segments are optional — maximize the length of a continuous sub-path?

Road Continuation: Check if a Series of Road Segments Forms a Valid Continuous Path

Question Details

Full Details

Topics

More from DoorDash