Battleships in a Board

Battleships in a Board

What is this problem about?

The "Battleships in a Board interview question" is a matrix-based counting problem. You are given a 2D grid representing a sea, where 'X' represents a part of a battleship and '.' represents open water. Battleships can only be placed horizontally or vertically and are separated by at least one horizontal or vertical cell of water. Your task is to count the total number of ships without using extra memory or modifying the original board.

Why is this asked in interviews?

Companies like Microsoft and Meta use the "Battleships in a Board coding problem" to test a candidate's ability to find "head" or "representative" elements in a grid. While you could use "Depth-First Search interview pattern" to find connected components, the real test is whether you can find a more efficient $O(1)$ space solution by identifying a unique property of each ship.

Algorithmic pattern used

The most efficient solution uses a Single Pass with Boundary Checking. Instead of traversing the entire ship when you find an 'X', you only count the "top-left" corner of the ship.

1. Iterate through every cell $(r, c)$ in the matrix.
2. If the current cell is an 'X':
   • Check if there is an 'X' above it $(r-1, c)$. If so, this is part of a vertical ship we've already counted.
   • Check if there is an 'X' to the left of it $(r, c-1)$. If so, this is part of a horizontal ship we've already counted.
3. If neither is true, this cell is the "start" of a new ship. Increment the counter.

Example explanation

Board:

X . . X
X . . X
. . . X

1. (0,0): 'X'. Nothing above or left. Count = 1.
2. (1,0): 'X'. There is an 'X' above it at (0,0). Ignore.
3. (0,3): 'X'. Nothing above or left. Count = 2.
4. (1,3): 'X'. 'X' above. Ignore.
5. (2,3): 'X'. 'X' above. Ignore. Total ships: 2.

Common mistakes candidates make

• Using DFS: While DFS works, it often uses extra memory (stack space) or requires modifying the board to "sink" the ships, which the problem may forbid.
• Redundant Counting: Counting every 'X' instead of just the "head" of the ship.
• Boundary Errors: Forgetting to check if r-1 or c-1 is out of bounds before accessing the array.

Interview preparation tip

When asked to count connected components in a grid with strict shapes (like horizontal/vertical only), always look for a "one-pass" strategy. Identifying a unique part of the shape (like the top-left corner) is a powerful "Matrix interview pattern" trick that avoids complex traversals.