#419

Medium

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Battleships in a Board

Count the number of non-overlapping battleships on a 2D board using array traversal and depth-first search patterns efficiently.

array depth first search matrix

Problem Statement

You are given an m x n matrix representing a game board where each cell is either a battleship 'X' or empty '.'. Battleships occupy consecutive cells horizontally or vertically and are separated by at least one empty cell from any other battleship. Your task is to return the total number of battleships on the board.

For example, given board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]], the correct output is 2 because there are two distinct battleships, one horizontal at the top-right and one vertical on the last column. Single-cell and multi-cell battleships are both valid as long as they follow the separation rule.

Examples

Example 1

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

Output: 2

Example details omitted.

Example 2

Input: board = [["."]]

Output: 0

Example details omitted.

Constraints

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

Solution Approach

Scan and Count

Iterate through each cell in the 2D board. When encountering an 'X' that is not preceded by another 'X' horizontally or vertically, increment the battleship count. This approach leverages the array traversal pattern and guarantees no double counting.

Depth-First Search Marking

For each unvisited 'X', perform DFS to mark all contiguous 'X' cells as visited. Recursion ensures all parts of a battleship are counted once. This directly applies the DFS pattern to handle variable-length ships along rows or columns.

Optimization with Early Skipping

Skip cells that are already part of a counted battleship by checking the previous row and column. This reduces unnecessary DFS calls and aligns with the problem's failure mode of overcounting adjacent ships.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m n) because each cell is visited once during scanning and DFS. Space complexity can be O(1) if modifying the board in place, or O(m n) for a separate visited matrix.

What Interviewers Usually Probe

Look for efficient in-place traversal without extra memory.
Expect handling of edge cases like single-row or single-column boards.
Clarify that ships never touch diagonally or directly adjacent.

Common Pitfalls or Variants

Common pitfalls

Counting the same battleship multiple times by not checking previous cells.
Ignoring the separation rule and merging distinct ships.
Recursion stack overflow on very large boards without proper base cases.

Follow-up variants

Boards with wrap-around edges where ships can connect across boundaries.
Counting ships that can touch diagonally but not orthogonally.
Return the coordinates of each battleship instead of just the count.

FAQ

What is the main strategy for Battleships in a Board?

Use array traversal combined with depth-first search to count each battleship exactly once without revisiting cells.

Can ships touch each other diagonally in this problem?

No, battleships are separated by at least one cell horizontally or vertically; diagonal adjacency does not form a single ship.

How does DFS help in counting battleships?

DFS explores all connected 'X' cells for a single battleship, marking them visited to prevent double counting.

Is it possible to solve without extra space?

Yes, by marking visited cells in place on the board, you can achieve O(1) additional space complexity.

What common mistake should I avoid for this array plus DFS problem?

Failing to check previous row and column before counting an 'X', which can lead to overcounting ships.

terminal

Solution

Solution 1: Direct Iteration

We can iterate through the matrix, find the top-left corner of each battleship, i.e., the position where the current position is `X` and both the top and left are not `X`, and increment the answer by one.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    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

Continue Practicing

#417 pacific atlantic water flow #463 island perimeter #329 longest increasing path in a matrix