Domain 2MediumCORE

Battleships in a Board

We are given an m x n grid representing a board where 'X' denotes a battleship and '.' represents empty water. We need to return the total count of distinct battleships present on this board.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#FAANG asked: 1

419. Battleships in a Board

Model: qwen3.5:9b
Topics:
FAANG asked: 1
Acceptance rate: 71.2%


Problem Breakdown

We are given an m x n grid representing a board where 'X' denotes a battleship and '.' represents empty water. We need to return the total count of distinct battleships present on this board.

Key Constraints & Rules:

  1. Shape: Battleships consist of contiguous cells in either one row (horizontal) or one column (vertical). They cannot be L-shaped, diagonal, or scattered.
  2. Separation: There is at least one empty cell separating any two battleships horizontally and vertically. This means no two ships share an edge.
  3. Input Validity: We can assume the input board adheres to these rules (no invalid configurations like touching ships).

Implicit Edge Cases:

  • Empty board (m=0 or n=0).
  • Board with only empty cells.
  • Ships located at boundaries of the grid (where neighbors don’t exist).
  • Large boards causing potential integer overflow? No, count fits in standard int.

Intuition

A brute-force approach would be to traverse every cell and perform a Depth-First Search (DFS) or Breadth-First Search (BFS) whenever we encounter an 'X' to find the entire connected component representing one ship.

Why Brute Force is Insufficient: While DFS/BFS correctly identifies ships, it requires O(m * n) space for a recursion stack or queue in the worst case. The follow-up challenge specifically asks us to solve this using one-pass, no modification of board values, and O(1) extra memory.

Key Insight: Since battleships are straight lines (horizontal OR vertical) and separated by gaps, every single ship has exactly one unique “head” or starting cell. If we scan the grid from top-left to bottom-right:

  • For any 'X' at (i, j), if there is an 'X' immediately above it ((i-1, j)), this current cell belongs to a vertical ship that started earlier in column j. We ignore it.
  • If there is an 'X' immediately to its left ((i, j-1)), this current cell belongs to a horizontal ship starting earlier in row i. We ignore it.
  • Therefore, we only count the battleship if both neighbors (top and left) are NOT 'X'. This identifies the top-leftmost corner of every distinct battleship exactly once per pass.

Approach

  1. Initialize a counter to zero.
  2. Iterate through each cell (i, j) in the board using nested loops (one-pass).
  3. Check if board[i][j] == 'X'.
  4. If it is an 'X', check its neighbors:
    • Is there a ship part above? (i > 0 and board[i-1][j] == 'X')
    • Is there a ship part to the left? (j > 0 and board[i][j-1] == 'X')
  5. If neither neighbor is an 'X', increment our counter. This cell represents the start of a new battleship relative to our scan order.
  6. Return the final count.

Complexity Analysis

  • Time Complexity: O(m * n). We visit every single cell in the grid exactly once during the iteration. All operations inside the loop are constant time checks.
  • Space Complexity: O(1). We use only a few integer variables for counting and boundary checking, regardless of board size. No recursion stack or auxiliary data structures are used.

Solution

def countBattleships(board: List[List[str]]) -> int:
    if not board or not board[0]:
        return 0
    
    rows = len(board)
    cols = len(board[0])
    
    battleship_count = 0
    
    # Iterate through every cell in the grid (One-Pass)
    for i in range(rows):
        for j in range(cols):
            if board[i][j] == 'X':
                # Check neighbors to identify the "head" of a ship.
                # A new battleship is counted only if it doesn't have 
                # an adjacent part above or to its left.
                
                has_top = (i > 0 and board[i - 1][j] == 'X')
                has_left = (j > 0 and board[i][j - 1] == 'X')
                
                if not has_top and not has_left:
                    battleship_count += 1
                    
    return battleship_count

Edge Cases Handled

  • Empty Board: The initial check if not board or not board[0]: handles cases where rows are empty.
  • Boundary Ships: When checking neighbors (i-1, j-1), we explicitly guard against index out of bounds using (i > 0) and (j > 0). This correctly counts ships starting at row 0 or column 0 without crashing.
  • Single Cell Ship: If the board is just one 'X', both neighbor checks fail (indices invalid), count increments to 1, which is correct.
  • Full Grid of Ships: The logic ensures we don’t double-count contiguous segments by ignoring any cell that has a predecessor in its row or column direction.