Watch 10 video solutions for Battleships in a Board, a medium level problem involving Array, Depth-First Search, Matrix. This walkthrough by Kevin Naughton Jr. has 39,280 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an m x n matrix board where each cell is a battleship 'X' or empty '.', return the number of the battleships on board.
Battleships can only be placed horizontally or vertically on board. In other words, they can only be made of the shape 1 x k (1 row, k columns) or k x 1 (k rows, 1 column), where k can be of any size. At least one horizontal or vertical cell separates between two battleships (i.e., there are no adjacent battleships).
Example 1:
Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]] Output: 2
Example 2:
Input: board = [["."]] Output: 0
Constraints:
m == board.lengthn == board[i].length1 <= m, n <= 200board[i][j] is either '.' or 'X'.
Follow up: Could you do it in one-pass, using only O(1) extra memory and without modifying the values board?
Problem Overview: You are given an m x n grid representing a battleship board. Cells contain either 'X' (part of a ship) or '.' (empty). Ships are placed only horizontally or vertically and never touch each other. The task is to count how many distinct battleships exist on the board.
Approach 1: Brute Force DFS Traversal (O(m*n) time, O(m*n) space)
Treat the board as a graph and explore each ship using Depth-First Search. Iterate through every cell of the matrix. When you encounter an 'X' that hasn't been visited, start a DFS and mark all connected 'X' cells belonging to that ship. Because ships are guaranteed to be straight lines, the DFS will only extend horizontally or vertically. Maintain a visited structure (array or hash set) to avoid revisiting cells. Each DFS traversal corresponds to exactly one battleship, so increment the count when a new traversal begins. This approach is straightforward and mirrors typical Depth-First Search problems on grids.
Approach 2: Optimized Linear Scan (O(m*n) time, O(1) space)
A more efficient observation eliminates the need for DFS or extra memory. Instead of exploring entire ships, count only the starting cell of each battleship. A cell is the start of a ship if it contains 'X' and there is no 'X' directly above it and no 'X' directly to its left. Iterate through the grid once using simple array indexing. When a cell satisfies this condition, it must represent the top-left segment of a battleship, so increment the count. All other segments belong to ships already counted. This works because ships never touch and are always straight lines.
Recommended for interviews: The optimized linear scan is what interviewers expect. It shows you can recognize structural constraints in the grid and reduce the problem to a single pass with O(1) extra space. Explaining the DFS approach first demonstrates understanding of grid traversal, but identifying the start-cell trick highlights stronger problem-solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force DFS Traversal | O(m*n) | O(m*n) | When learning grid traversal or when ships could have arbitrary shapes requiring full exploration |
| Optimized Linear Scan (Start Cell Detection) | O(m*n) | O(1) | Best approach when ships are guaranteed to be straight and non-touching |