How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Tesla.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Tesla during technical interviews.

Shortest Bridge to Connect Two Islands

Quick Overview

This question evaluates understanding of grid-based graph traversal, specifically combining flood fill with multi-source breadth-first search. It tests the ability to identify connected components and compute shortest paths between them, a common pattern in coding interviews assessing practical algorithm design on 2D matrices.

Company: Tesla

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Onsite

You are given an `n x n` grid where each cell is either water (`0`) or land (`1`). Land cells that are adjacent **horizontally or vertically** belong to the same landmass (an "island"). The grid is guaranteed to contain **exactly two** separate islands. You want to build a bridge by converting some water cells into land cells so that the two islands become connected — meaning you can travel from any land cell of one island to any land cell of the other by repeatedly stepping up, down, left, or right onto land cells. Each water cell you convert to land counts as **one unit** of bridge. Return the **minimum** number of water cells you must convert to land in order to connect the two islands into one. ### Examples - `grid = [[0,1],[1,0]]` → `1` Converting the single water cell at row `0`, column `0` (or the one at row `1`, column `1`) joins the two land cells. - `grid = [[0,1,0],[0,0,0],[0,0,1]]` → `2` The two islands are the single land cells at `(0,1)` and `(2,2)`; the shortest bridge between them spans two water cells. - `grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]` → `1` The outer ring is one island and the center cell is the other; converting one adjacent water cell connects them. ### Constraints - `n == grid.length == grid[i].length` - `2 <= n <= 100` - Each `grid[i][j]` is either `0` or `1`. - There are exactly two islands in `grid`. ### Output Return a single integer: the minimum number of water cells that must be converted to land to connect the two islands.

Quick Answer: This question evaluates understanding of grid-based graph traversal, specifically combining flood fill with multi-source breadth-first search. It tests the ability to identify connected components and compute shortest paths between them, a common pattern in coding interviews assessing practical algorithm design on 2D matrices.

You are given an `n x n` grid where each cell is either water (`0`) or land (`1`). Land cells adjacent horizontally or vertically belong to the same island. The grid contains exactly two separate islands. Build a bridge by converting some water cells into land so the two islands become connected (you can travel between them by stepping up/down/left/right onto land). Each converted water cell counts as one unit of bridge. Return the minimum number of water cells you must convert to land to connect the two islands into one. Example: `grid = [[0,1],[1,0]]` returns `1`. `grid = [[0,1,0],[0,0,0],[0,0,1]]` returns `2`. Constraints: `n == grid.length == grid[i].length`, `2 <= n <= 100`, each cell is `0` or `1`, and there are exactly two islands.

Constraints

n == grid.length == grid[i].length
2 <= n <= 100
Each grid[i][j] is either 0 or 1
There are exactly two islands in grid

Examples

Input: ([[0,1],[1,0]],)

Expected Output: 1

Explanation: Islands are the single cells (0,1) and (1,0); converting one adjacent water cell (e.g. (0,0)) joins them.

Input: ([[0,1,0],[0,0,0],[0,0,1]],)

Expected Output: 2

Explanation: Single-cell islands at (0,1) and (2,2); the shortest bridge spans two water cells.

Input: ([[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]],)

Expected Output: 1

Explanation: Outer ring is one island, the center cell the other; one adjacent water flip connects them.

Input: ([[1,0],[0,1]],)

Expected Output: 1

Explanation: Diagonal single-cell islands at (0,0) and (1,1); one water flip bridges them.

Input: ([[0,0,0,0,0],[0,1,0,0,0],[0,0,0,0,0],[0,0,0,1,0],[0,0,0,0,0]],)

Expected Output: 3

Explanation: Islands at (1,1) and (3,3) are Manhattan distance 4 apart, so 3 intermediate water cells must be converted.

Input: ([[1,1,0,0,0],[1,1,0,0,0],[0,0,0,0,0],[0,0,0,1,1],[0,0,0,1,1]],)

Expected Output: 3

Explanation: Two 2x2 block islands; the closest cells are (1,1) and (3,3), needing 3 water conversions.

Hints

First isolate ONE island completely (DFS or BFS from any land cell) and mark all of its cells so you can tell them apart from the other island.
From every cell of that first island simultaneously, run a layer-by-layer BFS through water. The first time you step onto a cell of the other island, the number of water layers you crossed is the answer.
Count a BFS 'level' as one converted water cell. Returning at the moment you touch a 1 (before incrementing) gives the count of water cells between the islands.

Quick Overview