4.13 Battleships in a Board

4.13.1 Problem Metadata

4.13.2 Description

Given an m x n matrix board where each cell is a battleship 'X' or empty '.', return the number of battleships on the board.

Battleships can only be placed horizontally or vertically on the 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).

4.13.3 Examples

Example 1:

Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
Output: 2

Example 2:

Input: board = [["."]]
Output: 0

4.13.4 Constraints

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] is either '.' or 'X'

4.13.5 Follow-up

Could you do it in one pass, using only O(1) extra memory and without modifying the board values?

4.13.6 Solution - Top-Left Corner Counting

4.13.6.1 Walkthrough

The key insight is that we only need to count the top-left corner (or starting point) of each battleship. Since battleships are either horizontal or vertical and never adjacent, we can identify a battleship’s start by skipping cells that have a battleship piece above them or to their left.

Why this works:

For any battleship (horizontal or vertical), only its top-left cell will have: - No 'X' in the cell directly above it (if r > 0) - No 'X' in the cell directly to its left (if c > 0)

All other cells of the same battleship will have at least one 'X' neighbor in these directions and will be skipped using guard clauses.

Example Walkthrough:

Board:
X . . X
. . . X
. . . X

Cell (0,0): X, no row above, no col left → COUNT ✓ (single-cell or horizontal ship start)
Cell (0,3): X, no row above, board[0][2]='.' → COUNT ✓ (vertical ship start)
Cell (1,3): X, board[0][3]='X' above → SKIP (part of vertical ship)
Cell (2,3): X, board[1][3]='X' above → SKIP (part of vertical ship)

Result: 2 battleships

This approach satisfies the follow-up requirement: one pass, O(1) space, no board modification.

Algorithm Strategy:

Using early-exit guard clauses with continue, we skip any 'X' cell that: 1. Has an 'X' directly above it (not a ship start, part of a vertical ship), OR 2. Has an 'X' directly to its left (not a ship start, part of a horizontal ship)

Only cells that pass both guard checks are battleship starting points.

4.13.6.2 Analysis

  • Time Complexity: O(m × n) - Single pass through all cells in the board
  • Space Complexity: O(1) - Only using a counter variable, no auxiliary data structures or board modification

4.13.6.3 Implementation Steps

  1. Initialize result = 0 to count battleships
  2. Iterate through each cell (r, c) in the board using nested loops
  3. For each cell containing 'X':
    • Skip if not top-left corner: Use guard clauses with continue to skip cells that are:
      • Part of a vertical ship: If r > 0 (row exists above) AND board[r-1][c] == 'X' (cell above is occupied)
      • Part of a horizontal ship: If c > 0 (column exists to left) AND board[r][c-1] == 'X' (cell to left is occupied)
    • Count if top-left corner: If both guard clauses pass, this is a ship’s starting point, so increment result
  4. Return result

4.13.6.4 Code - Java

class Solution {
    public int countBattleships(char[][] board) {
        int rows = board.length;
        int cols = board[0].length;
        int result = 0;

        for(int r = 0; r < rows; r++) {
            for(int c = 0; c < cols; c++) {
                //count the **top-left corner** of each UNIQUE battleship
                if (board[r][c] == 'X') {                
                    // NO battleship is placed above it
                    if (r > 0 && board[r-1][c] == 'X') {
                        continue;
                    }

                    // NO battleship is placed to its left
                    if (c > 0 && board[r][c-1] == 'X') {
                        continue;
                    }
                    
                    result++;
                }
            }        
        }

        return result;
    }
}