419. Battleships in a Board
Model: qwen3.5:9b
Topics:
FAANG asked: 1
Acceptance rate: 71.2%
Problem Breakdown
We are given an m x n grid representing a board where 'X' denotes a battleship and '.' represents empty water. We need to return the total count of distinct battleships present on this board.
Key Constraints & Rules:
- Shape: Battleships consist of contiguous cells in either one row (horizontal) or one column (vertical). They cannot be L-shaped, diagonal, or scattered.
- Separation: There is at least one empty cell separating any two battleships horizontally and vertically. This means no two ships share an edge.
- Input Validity: We can assume the input board adheres to these rules (no invalid configurations like touching ships).
Implicit Edge Cases:
- Empty board (
m=0orn=0). - Board with only empty cells.
- Ships located at boundaries of the grid (where neighbors don’t exist).
- Large boards causing potential integer overflow? No, count fits in standard int.
Intuition
A brute-force approach would be to traverse every cell and perform a Depth-First Search (DFS) or Breadth-First Search (BFS) whenever we encounter an 'X' to find the entire connected component representing one ship.
Why Brute Force is Insufficient:
While DFS/BFS correctly identifies ships, it requires O(m * n) space for a recursion stack or queue in the worst case. The follow-up challenge specifically asks us to solve this using one-pass, no modification of board values, and O(1) extra memory.
Key Insight: Since battleships are straight lines (horizontal OR vertical) and separated by gaps, every single ship has exactly one unique “head” or starting cell. If we scan the grid from top-left to bottom-right:
- For any
'X'at(i, j), if there is an'X'immediately above it ((i-1, j)), this current cell belongs to a vertical ship that started earlier in columnj. We ignore it. - If there is an
'X'immediately to its left ((i, j-1)), this current cell belongs to a horizontal ship starting earlier in rowi. We ignore it. - Therefore, we only count the battleship if both neighbors (top and left) are NOT
'X'. This identifies the top-leftmost corner of every distinct battleship exactly once per pass.
Approach
- Initialize a counter to zero.
- Iterate through each cell
(i, j)in the board using nested loops (one-pass). - Check if
board[i][j] == 'X'. - If it is an
'X', check its neighbors:- Is there a ship part above? (
i > 0andboard[i-1][j] == 'X') - Is there a ship part to the left? (
j > 0andboard[i][j-1] == 'X')
- Is there a ship part above? (
- If neither neighbor is an
'X', increment our counter. This cell represents the start of a new battleship relative to our scan order. - Return the final count.
Complexity Analysis
- Time Complexity:
O(m * n). We visit every single cell in the grid exactly once during the iteration. All operations inside the loop are constant time checks. - Space Complexity:
O(1). We use only a few integer variables for counting and boundary checking, regardless of board size. No recursion stack or auxiliary data structures are used.
Solution
def countBattleships(board: List[List[str]]) -> int:
if not board or not board[0]:
return 0
rows = len(board)
cols = len(board[0])
battleship_count = 0
# Iterate through every cell in the grid (One-Pass)
for i in range(rows):
for j in range(cols):
if board[i][j] == 'X':
# Check neighbors to identify the "head" of a ship.
# A new battleship is counted only if it doesn't have
# an adjacent part above or to its left.
has_top = (i > 0 and board[i - 1][j] == 'X')
has_left = (j > 0 and board[i][j - 1] == 'X')
if not has_top and not has_left:
battleship_count += 1
return battleship_count
Edge Cases Handled
- Empty Board: The initial check
if not board or not board[0]:handles cases where rows are empty. - Boundary Ships: When checking neighbors (
i-1,j-1), we explicitly guard against index out of bounds using(i > 0)and(j > 0). This correctly counts ships starting at row 0 or column 0 without crashing. - Single Cell Ship: If the board is just one
'X', both neighbor checks fail (indices invalid), count increments to 1, which is correct. - Full Grid of Ships: The logic ensures we don’t double-count contiguous segments by ignoring any cell that has a predecessor in its row or column direction.