Minimum Path Node Count with an Optional Broken Vertex
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Minimum Path Node Count with an Optional Broken Vertex
You are given an undirected graph as an adjacency list `connections`, two vertices `start` and `destination`, one vertex `broken`, and a Boolean `allowBroken`.
Return the minimum number of vertices on a path from `start` to `destination`. When `allowBroken` is `false`, the path may not contain `broken`. When it is `true`, treat `broken` like any other vertex. Return `-1` if no valid path exists.
Implement `minPathNodes(connections, start, destination, broken, allowBroken)`.
## Constraints
- `1 <= connections.length <= 200,000`
- Vertices are indexed from `0` through `connections.length - 1`.
- Every neighbor index is valid, and adjacency is symmetric.
- Each adjacency list contains no duplicate neighbor.
- `start`, `destination`, and `broken` are valid vertex indexes.
- If `start == destination`, return `1` unless that vertex is disallowed as broken.
- If `allowBroken` is `false` and either endpoint equals `broken`, return `-1`.
## Example 1
```text
Input: connections = [[1, 2], [0, 4], [0, 3], [2, 4], [1, 3]], start = 0, destination = 4, broken = 1, allowBroken = false
Output: 4
```
The shortest valid path is `0 -> 2 -> 3 -> 4`, which contains four vertices.
## Example 2
```text
Input: connections = [[1, 2], [0, 4], [0, 3], [2, 4], [1, 3]], start = 0, destination = 4, broken = 1, allowBroken = true
Output: 3
```
Allowing the broken vertex makes `0 -> 1 -> 4` valid.
Quick Answer: Return the fewest vertices on a graph path while optionally excluding one broken vertex, then compare the follow-up that permits it. The problem covers endpoint rules, unreachable results, same-vertex paths, adjacency-list scale, and precise node-versus-edge distance.
Given a symmetric undirected adjacency list, start and destination vertices, one broken vertex, and allowBroken, return the minimum number of vertices on a valid start-to-destination path. A false flag forbids broken; a true flag treats it like any other vertex. Return -1 when no valid path exists. If start equals destination, return 1 unless that endpoint is the disallowed broken vertex.
Constraints
- 1 <= connections.length <= 200,000
- Vertices are indexed from 0 through connections.length - 1.
- Every neighbor is valid, adjacency is symmetric, and each adjacency list has no duplicate neighbor.
- start, destination, and broken are valid indices.
- A disallowed broken endpoint returns -1, including when start equals destination.
Examples
Input: ([[1, 2], [0, 4], [0, 3], [2, 4], [1, 3]], 0, 4, 1, False)
Expected Output: 4
Explanation: The first source example must avoid vertex 1 and uses four vertices through 2 and 3.
Input: ([[1, 2], [0, 4], [0, 3], [2, 4], [1, 3]], 0, 4, 1, True)
Expected Output: 3
Explanation: The second source example allows the broken vertex and uses 0, 1, and 4.
Hints
- Forbid broken during neighbor expansion when allowBroken is false.
- Initialize the start distance to one because the requested metric counts vertices, not edges.