Battleships in a Board
Given an $m \times n$ board where 'X's represent battleships and '.'s represent water, count the number of battleships. Battleships are placed horizontally or vertically, and are separated by water. Solve in $O(n)$ without modifying the board.
Why Interviewers Ask This
Uber interviewers use this problem to assess a candidate's ability to optimize for space complexity while maintaining algorithmic clarity. They specifically evaluate if you can identify that battleships are contiguous components and count only their unique starting points, rather than using BFS or DFS which would require O(m*n) extra space. This tests your understanding of greedy strategies and single-pass iteration constraints.
How to Answer This Question
1. Clarify Constraints: Immediately confirm the rules regarding horizontal vs. vertical placement and the prohibition on modifying the input board. Mention Uber's focus on efficiency by stating you aim for O(1) space.
2. Identify the Core Logic: Explain that counting every 'X' will overcount ships. Instead, propose counting only the top-leftmost cell of each ship. A cell is a start if it is an 'X' and has no 'X' immediately above it and no 'X' immediately to its left.
3. Define the Algorithm: Describe a nested loop iterating through rows and columns. For each cell, apply the 'start' condition check before incrementing the counter.
4. Handle Edge Cases: Briefly mention checking boundary conditions where accessing row-1 or col-1 might be out of bounds.
5. Complexity Analysis: Conclude by explicitly stating the time complexity is O(m*n) and space complexity is O(1), satisfying the strict requirements without auxiliary data structures.
Key Points to Cover
- Recognizing that counting ship starts avoids overcounting contiguous segments
- Explicitly addressing the O(1) space constraint by rejecting BFS/DFS
- Defining the precise condition for a cell being a ship's head
- Handling boundary checks for the top row and leftmost column safely
- Demonstrating clear communication of time and space complexity trade-offs
Sample 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.
Common Mistakes to Avoid
- Using a visited array or recursion stack which violates the O(1) space requirement
- Iterating through the board twice or using complex data structures unnecessarily
- Failing to check both the top and left neighbors, leading to incorrect counts
- Attempting to mark visited cells by modifying the input board directly
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.