Battleships in a Board

Med

#0406Time: 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.2 companies

Algorithms

Depth-First Search

Data structures

Array Matrix

Companies

Tinkoff Microstrategy

Prompt

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.length
n == board[i].length
1 <= m, n <= 200
board[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 count to 0.
Get the dimensions of the board, m rows and n columns.
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 the count. 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 if board[r][c] is not 'X', return. ii. Mark the current cell as visited to prevent recounting. A common way is to change board[r][c] to '.' (this modifies the input board). iii. Recursively call dfs for 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

1class Solution {2    public int countBattleships(char[][] board) {3        if (board == null || board.length == 0) {4            return 0;5        }6        int m = board.length;7        int n = board[0].length;8        int count = 0;9 10        for (int i = 0; i < m; i++) {11            for (int j = 0; j < n; j++) {12                if (board[i][j] == 'X') {13                    count++;14                    dfs(board, i, j);15                }16            }17        }18        19        // Note: This approach modifies the board. To restore it, one would need to 20        // store the original 'X' positions and change them back, which adds complexity.21 22        return count;23    }24 25    private void dfs(char[][] board, int i, int j) {26        int m = board.length;27        int n = board[0].length;28 29        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'X') {30            return;31        }32 33        // Mark the current cell as visited by changing it to '.'34        board[i][j] = '.';35 36        // Explore neighbors37        dfs(board, i + 1, j);38        dfs(board, i - 1, j);39        dfs(board, i, j + 1);40        dfs(board, i, j - 1);41    }42}

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 visited matrix of size m x n is required, leading to O(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.

This optimal approach solves the problem in a single pass over the board, using only constant extra memory and without modifying the input array. It perfectly addresses the follow-up question.

The key insight is to count each battleship exactly once by identifying a unique, representative cell for each ship. A convenient choice is the "head" of the ship, which we can define as its top-most, left-most 'X'.

As we iterate through the grid, whenever we encounter an 'X', we simply check if it's a head. An 'X' at (i, j) is a head if there is no 'X' immediately above it (board[i-1][j]) and no 'X' immediately to its left (board[i][j-1]). If it is a head, we increment our count. If not, it's part of a ship we've already counted (or will count when we reach its head), so we ignore it. This ensures every ship is counted precisely once.

Algorithm

Initialize a battleship counter count to 0.
Get the dimensions of the board, m rows and n columns.
Iterate through each cell (i, j) of the board.
If board[i][j] is an 'X', check if it's the "head" of a battleship.
A cell (i, j) is considered a head if: a. The cell above it, (i-1, j), does not contain an 'X'. (This condition is trivially true if i is 0). b. The cell to its left, (i, j-1), does not contain an 'X'. (This condition is trivially true if j is 0).
If both conditions are met, it means we have found the top-leftmost part of a new battleship, so we increment count.
If either condition is not met, it means the current 'X' is part of a ship whose head we have already found and counted, so we do nothing.
After iterating through all cells, return the final count.

Walkthrough

1class Solution {2    public int countBattleships(char[][] board) {3        int m = board.length;4        if (m == 0) {5            return 0;6        }7        int n = board[0].length;8        9        int count = 0;10        11        for (int i = 0; i < m; i++) {12            for (int j = 0; j < n; j++) {13                // Skip empty cells14                if (board[i][j] == '.') {15                    continue;16                }17                18                // If the cell above has an 'X', it's part of a vertical ship we've already counted.19                if (i > 0 && board[i - 1][j] == 'X') {20                    continue;21                }22                23                // If the cell to the left has an 'X', it's part of a horizontal ship we've already counted.24                if (j > 0 && board[i][j - 1] == 'X') {25                    continue;26                }27                28                // If we reach here, this 'X' is the top-left corner of a new battleship.29                count++;30            }31        }32        33        return count;34    }35}

Complexity

Time

O(m * n). We iterate through every cell of the grid exactly once, performing a constant number of checks for each cell.

Space

O(1). The algorithm only uses a few variables for the count and loop indices, which does not depend on the size of the input board.

Trade-offs

Pros

Extremely efficient, with optimal time and space complexity.
Achieves the solution in a single pass over the grid.
Uses only O(1) extra space.
Does not modify the input board, which is a common requirement.
The implementation is simple and avoids recursion.

Cons

The logic is highly specific to the problem's constraints, namely that battleships are straight lines (1xK or Kx1) and are always separated by at least one empty cell. It would not work for more complex ship shapes or if ships could be adjacent.

Solutions

Solution

1class Solution {2public3  int countBattleships(char[][] board) {4    int m = board.length, n = board[0].length;5    int ans = 0;6    for (int i = 0; i < m; ++i) {7      for (int j = 0; j < n; ++j) {8        if (board[i][j] == '.') {9          continue;10        }11        if (i > 0 && board[i - 1][j] == 'X') {12          continue;13        }14        if (j > 0 && board[i][j - 1] == 'X') {15          continue;16        }17        ++ans;18      }19    }20    return ans;21  }22}

1class Solution:2    def countBattleships(self, board: List[List[str]]) -> int: m, n = len(board), len(board[0]) ans = 0 for i in range(m): for j in range(n): if board[i][j] == '.': continue if i > 0 and board[i - 1][j] == 'X': continue if j > 0 and board[i][j - 1] == 'X': continue ans += 1 return ans

1class Solution { public: int countBattleships ( vector < vector < char >>& board ) { int m = board . size (), n = board [ 0 ]. size (); 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.

← Previous

Previous problem

Next problem