Battleships in a Board

Question

Accepted Answer

To solve this efficiently within Uber's high-performance standards, I would avoid standard graph traversal algorithms like BFS or DFS because they typically require a visited array or recursion stack, violating the O(1) space constraint. Instead, I'll use a greedy approach that counts only the head of each battleship.

The logic relies on the fact that every ship has exactly one top-left corner. If I iterate through the grid cell by cell, I can determine if a specific 'X' is the start of a new ship by checking its immediate neighbors. Specifically, a cell at (i, j) is the start of a ship if it contains an 'X', the cell above it (i-1, j) is not an 'X', and the cell to its left (i, j-1) is not an 'X'.

For example, consider a board with a horizontal ship at row 0, columns 0 and 1. When I visit (0,0), there is no cell above or to the left, so it counts as 1. When I visit (0,1), there is an 'X' to its left, so I skip it. Similarly, for a vertical ship, the bottom cells will have an 'X' above them and won't be counted. This ensures each ship contributes exactly one to the total count.

This approach requires a single pass through the m x n grid, resulting in O(m*n) time complexity. Since we only use a few integer variables for indices and the counter, the space complexity remains O(1). We never modify the board, adhering strictly to the prompt's constraints.

Battleships in a Board

Why Interviewers Ask This

How to Answer This Question

Key Points to Cover

Sample Answer

Common Mistakes to Avoid

Sound confident on this question in 5 minutes

Related Interview Questions

Search in Rotated Sorted Array

Merge Intervals

Shortest Word Distance