[Medium] 419. Battleships in a Board

Difficulty: Medium
Category: Array, Matrix, DFS
Companies: Amazon, Google, Microsoft

Given an m x n matrix board where each cell is either 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).

Examples

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'

Solution Approaches

Approach 1: Count Top-Left Corners (Optimal)

Key Insight: Only count the top-left corner of each battleship. A cell is the top-left corner if:

1. It contains 'X'
2. The cell above it (if exists) is not 'X'
3. The cell to the left (if exists) is not 'X'

Time Complexity: O(m × n)
Space Complexity: O(1)

class Solution:
    def countBattleships(self, board: list[list[str]]) -> int:
        count = 0

        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == 'X':

                    # skip if part of vertical ship
                    if i > 0 and board[i - 1][j] == 'X':
                        continue

                    # skip if part of horizontal ship
                    if j > 0 and board[i][j - 1] == 'X':
                        continue

                    count += 1

        return count

Solution Explanation

Approach: Recursive DFS (this problem)

Key idea: 1. Battleship Structure: Each battleship is a connected component of 'X' cells

How the code works:

1. Battleship Structure: Each battleship is a connected component of 'X' cells
   • DFS explores one branch fully before backtracking.
   • Mark visited nodes to avoid cycles on graphs.
   • Return aggregated results from children to the parent.

Walkthrough — input board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]], expected output 2:

1. Initialize variables from the problem setup.
2. Apply the main loop / recursion until the condition is met.
3. Confirm the result matches the expected output.

   Edge Cases

4. Empty Board: Return 0
5. Single Cell: [["X"]] → 1 battleship
6. No Battleships: [["."]] → 0 battleships
7. Large Battleships: Vertical or horizontal ships of any length

Follow-up Questions

• What if battleships could be L-shaped or T-shaped?
• How would you find the size of each battleship?
• What if the board could be modified (mark visited ships)?

Related Problems

• LC 200: Number of Islands
• LC 695: Max Area of Island
• LC 130: Surrounded Regions

Implementation Notes

1. Boundary Checks: Always check array bounds before accessing
2. Type Casting: Cast board.size() to int to avoid comparison warnings
3. Early Continue: Use continue to skip non-top-left corners
4. Single Pass: No need to modify the original board

Common Mistakes

• Skipping edge cases (empty input, single element, boundaries).
• Off-by-one errors in loops and index ranges.
• Forgetting to handle the case when no valid answer exists.

Key Takeaways

1. Battleship Structure: Each battleship is a connected component of 'X' cells
2. No Adjacent Ships: Ships are separated by at least one empty cell
3. Top-Left Corner: Each battleship has exactly one top-left corner
4. Single Pass: Can count ships in one pass without modification

References

• LC 419: Battleships in a Board on LeetCode
• LeetCode Discuss — LC 419: Battleships in a Board
• LeetCode Editorial (may require premium)

Template Reference

• Array & Matrix

Thinking Process

1. Battleship Structure: Each battleship is a connected component of 'X' cells

• DFS explores one branch fully before backtracking.
• Mark visited nodes to avoid cycles on graphs.
• Return aggregated results from children to the parent.

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Recursive DFS (this problem)	O(n)	O(h) stack	Natural for trees and graphs
Iterative DFS (stack)	O(n)	O(n)	Avoid recursion depth limits
DFS with memoization	O(n)	O(n)	Overlapping subproblems on graphs
Backtracking DFS	O(2^n) typical	O(n)	Enumerate choices with pruning