Shortest Distance in an Unweighted Adjacency-Matrix Graph
Company: BCG
Role: Forward Deploy Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Shortest Distance in an Unweighted Adjacency-Matrix Graph
You are given the Boolean adjacency matrix of a connected, undirected, unweighted graph. Return the minimum number of edges on a path between two specified vertices.
Implement `shortestDistance(matrix, vertex1, vertex2)`.
## Input and Output
- `matrix` is an `n x n` Boolean matrix.
- `matrix[i][j]` is `true` exactly when an edge joins vertices `i` and `j`.
- `vertex1` and `vertex2` are zero-based vertex indexes.
- Return the fewest edges needed to travel from `vertex1` to `vertex2`.
## Constraints
- `1 <= n <= 2,000`
- `matrix[i][i]` is always `false`.
- `matrix[i][j] == matrix[j][i]` for all valid `i` and `j`.
- The graph has no loops or parallel edges and is connected.
- `0 <= vertex1, vertex2 < n`
- If the two vertices are equal, return `0`.
## Example 1
```text
Input: matrix = [[false, false, true], [false, false, true], [true, true, false]], vertex1 = 0, vertex2 = 1
Output: 2
```
One shortest path is `0 -> 2 -> 1`.
## Example 2
```text
Input: matrix = [[false, true, false, false], [true, false, true, true], [false, true, false, false], [false, true, false, false]], vertex1 = 2, vertex2 = 3
Output: 2
```
One shortest path is `2 -> 1 -> 3`.
Overview: Find the minimum edge count between two vertices in a connected, undirected graph represented by a Boolean adjacency matrix. The problem tests traversal order, visited-state handling, the same-vertex case, and matrix-specific complexity.
Read the full BCG Forward Deploy Engineer interview experience this question came from
Implement shortestDistance(matrix, vertex1, vertex2). matrix is the Boolean adjacency matrix of a connected, undirected, unweighted simple graph. Return the minimum number of edges on a path from the zero-based vertex1 to vertex2. The matrix is symmetric, its diagonal is false, and equal endpoints have distance 0.
Constraints
- 1 <= n <= 2,000
- matrix is n by n and contains Boolean values.
- matrix[i][i] is false and matrix[i][j] equals matrix[j][i].
- The graph is connected and has no loops or parallel edges.
- 0 <= vertex1, vertex2 < n
- Return 0 when vertex1 equals vertex2.
Examples
Input: ([[False]], 0, 0)
Expected Output: 0
Explanation: The only vertex is already the destination.
Input: ([[False, True], [True, False]], 0, 1)
Expected Output: 1
Explanation: A direct edge has distance one.
Hints
- In an unweighted graph, explore vertices in layers of increasing edge distance.
- An adjacency matrix requires scanning a whole row to find a vertex's neighbors.