Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

419. Battleships in a Board - Leetcode Solution

Code Implementation

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        if not board or not board[0]:
            return 0
        rows, cols = len(board), len(board[0])
        count = 0
        for i in range(rows):
            for j in range(cols):
                if board[i][j] == 'X':
                    if (i == 0 or board[i-1][j] != 'X') and (j == 0 or board[i][j-1] != 'X'):
                        count += 1
        return count
      
class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int rows = board.size(), cols = board[0].size();
        int count = 0;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (board[i][j] == 'X') {
                    if ((i == 0 || board[i-1][j] != 'X') && (j == 0 || board[i][j-1] != 'X')) {
                        ++count;
                    }
                }
            }
        }
        return count;
    }
};
      
class Solution {
    public int countBattleships(char[][] board) {
        int rows = board.length, cols = board[0].length;
        int count = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'X') {
                    if ((i == 0 || board[i-1][j] != 'X') && (j == 0 || board[i][j-1] != 'X')) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}
      
var countBattleships = function(board) {
    let rows = board.length, cols = board[0].length;
    let count = 0;
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (board[i][j] === 'X') {
                if ((i === 0 || board[i-1][j] !== 'X') && (j === 0 || board[i][j-1] !== 'X')) {
                    count++;
                }
            }
        }
    }
    return count;
};

Problem Description

You are given a 2D board, represented as a grid of characters, where each cell contains either 'X' (part of a battleship) or '.' (empty water). Each battleship occupies consecutive cells either horizontally or vertically, and there are no adjacent battleships (i.e., there are never two battleships touching each other horizontally or vertically). Your task is to count how many distinct battleships are present on the board. Key constraints:
  • Each battleship is made up of one or more contiguous 'X' cells, aligned either horizontally or vertically.
  • Battleships are separated by at least one cell of '.' (water) in all directions.
  • The board has only one valid configuration; you do not need to modify the board or find all possible arrangements.
  • You should not reuse or double-count any part of a battleship.

Thought Process

At first glance, one might consider a brute-force approach: for every 'X' cell, perform a depth-first or breadth-first search to mark all connected 'X' cells as part of the same battleship, and count each time a new, unvisited 'X' is found. However, this requires extra space to track visited cells or modifies the board, which isn't optimal. On further thought, since the problem guarantees that battleships are not adjacent, we can optimize. Instead of marking and visiting, we can recognize that the start of every battleship is the top-leftmost cell in its segment: it will not have another 'X' directly above or to its left. Thus, we only need to count these unique starting points to get the total number of battleships.

Solution Approach

We can efficiently count battleships by scanning the board once and applying a simple check at each cell.
  1. Iterate through every cell in the grid.
  2. For each cell containing 'X', check if it is the top-leftmost part of a battleship:
    • If there is an 'X' directly above (i-1, j), then this cell is part of a vertical battleship already counted.
    • If there is an 'X' directly to the left (i, j-1), then this cell is part of a horizontal battleship already counted.
    • If neither is true, this cell is the start of a new battleship, so increment the count.
  3. Continue until all cells are checked.
This approach avoids revisiting or marking cells, and does not require extra memory.

Example Walkthrough

Consider the board: 
  X . . X
  . . . X
  . . . X
Let's walk through each cell:
  • (0,0): 'X' - No 'X' above or to the left. Count = 1
  • (0,3): 'X' - No 'X' above or to the left. Count = 2
  • (1,3): 'X' - There is an 'X' above at (0,3), so it's part of the same battleship. No count.
  • (2,3): 'X' - There is an 'X' above at (1,3), so it's part of the same battleship. No count.
All other cells are '.', so they are skipped. Final count: 2 battleships.

Time and Space Complexity

  • Brute-force approach: Using DFS or BFS, each cell is visited, and possibly revisited, leading to O(M*N) time and O(M*N) space for marking visited cells.
  • Optimized approach (as above): Each cell is visited once with O(1) work per cell, for a total of O(M*N) time. No extra space is required beyond a few variables, so space complexity is O(1).

Summary

The key insight is to recognize that, due to the constraints, every battleship's start can be uniquely identified as an 'X' cell with no 'X' above or to the left. By counting only these, we efficiently solve the problem in one pass, with no extra memory or modification to the board. This makes the solution both elegant and optimal.