Battleships in a Board
MedPrompt
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: 2Example 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?
Approaches
2 approaches with complexity analysis and trade-offs.
A standard approach for counting connected components in a grid is to use a graph traversal algorithm like Depth First Search (DFS) or Breadth First Search (BFS). We can treat the grid as a graph where each 'X' is a node and adjacent 'X's have an edge between them. The goal is to count the number of disconnected subgraphs of 'X's.
The algorithm iterates through each cell of the board. If it finds a cell with an 'X' that hasn't been visited yet, it means we've discovered a new battleship. We increment our battleship counter. Then, we start a traversal (DFS) from that cell to find all other 'X's belonging to the same ship. During the traversal, we mark each visited 'X' (e.g., by changing it to '.') to ensure we don't count any part of this ship again. This process is often called "sinking the ship". We continue scanning the grid until all cells have been checked.
Algorithm
- Initialize a battleship counter
countto 0. - Get the dimensions of the board,
mrows andncolumns. - Iterate through each cell
(i, j)of the board from(0, 0)to(m-1, n-1). - If the current cell
board[i][j]contains an 'X': a. Increment thecount. b. Start a Depth First Search (DFS) from this cell to find all connected 'X's that form the complete battleship. c. The DFS function,dfs(board, r, c), works as follows: i. Check for base cases: if the coordinates(r, c)are out of bounds or ifboard[r][c]is not 'X', return. ii. Mark the current cell as visited to prevent recounting. A common way is to changeboard[r][c]to '.' (this modifies the input board). iii. Recursively calldfsfor all four adjacent cells:(r+1, c),(r-1, c),(r, c+1), and(r, c-1). - After the nested loops complete, return the final
count.
Walkthrough
class Solution { public int countBattleships(char[][] board) { if (board == null || board.length == 0) { return 0; } int m = board.length; int n = board[0].length; int count = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == 'X') { count++; dfs(board, i, j); } } } // Note: This approach modifies the board. To restore it, one would need to // store the original 'X' positions and change them back, which adds complexity. return count; } private void dfs(char[][] board, int i, int j) { int m = board.length; int n = board[0].length; if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'X') { return; } // Mark the current cell as visited by changing it to '.' board[i][j] = '.'; // Explore neighbors dfs(board, i + 1, j); dfs(board, i - 1, j); dfs(board, i, j + 1); dfs(board, i, j - 1); }}Complexity
Time
O(m * n), where `m` and `n` are the dimensions of the board. The nested loops iterate through each cell once. The DFS traversal also visits each 'X' cell at most once over the entire execution. Therefore, every cell is processed a constant number of times.
Space
O(m * n) in the worst case. This space is consumed by the recursion stack. For a board filled with a single, long, winding battleship, the recursion depth could be proportional to the total number of cells. If a separate `visited` matrix is used instead of in-place modification, it also requires `O(m * n)` space.
Trade-offs
Pros
The logic is straightforward and a standard application of graph traversal.
It's robust and would work even if battleships had more complex shapes (e.g., 'L' or 'T' shapes), as long as they are contiguous.
Cons
This approach modifies the input board, which might not be permissible in some contexts.
If modification is not allowed, a separate
visitedmatrix of sizem x nis required, leading toO(m * n)space complexity.The recursion depth can, in the worst-case scenario (a long, snake-like ship), be up to
O(m * n), potentially leading to a stack overflow for very large boards.
Solutions
Solution
class Solution {public int countBattleships(char[][] board) { int m = board.length, n = board[0].length; int ans = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (board[i][j] == '.') { continue; } if (i > 0 && board[i - 1][j] == 'X') { continue; } if (j > 0 && board[i][j - 1] == 'X') { continue; } ++ans; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.