Problem Description

You are given an m x n matrix called board that represents a game board. Each cell in this matrix contains either:

• 'X' which represents part of a battleship
• '.' which represents an empty cell

Your task is to count how many battleships are on the board.

The battleships follow these rules:

1. Shape: Each battleship can only be placed either horizontally or vertically. This means a battleship has the shape:

   • 1 x k (1 row and k columns) - horizontal battleship
   • k x 1 (k rows and 1 column) - vertical battleship
   • where k can be any positive size

2. Separation: Battleships cannot be adjacent to each other. There must be at least one empty cell (horizontally or vertically) separating any two battleships.

The solution leverages a key insight: instead of tracking entire battleships, we can count only the "starting points" of each battleship. For any battleship, we define its starting point as its top-left cell. A cell at position (i, j) containing 'X' is a starting point if:

• It's an 'X' cell
• There's no 'X' directly above it (at position (i-1, j))
• There's no 'X' directly to its left (at position (i, j-1))

By counting these starting points, we effectively count the number of battleships since each battleship has exactly one starting point.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: We can model this problem as a graph where each cell containing 'X' is a node, and adjacent 'X' cells (horizontally or vertically) form edges between nodes. Each battleship forms a connected component in this graph.

Is it a tree?

• No: The battleships are not structured as trees. They form linear connected components (either horizontal or vertical lines), but multiple battleships exist independently on the board, and there's no hierarchical parent-child relationship.

Is the problem related to directed acyclic graphs?

• No: The problem doesn't involve directed edges or acyclic properties. The battleships are undirected connected components.

Is the problem related to shortest paths?

• No: We're not finding shortest paths between cells. We need to count distinct connected components (battleships).

Does the problem involve connectivity?

• Yes: The core of the problem is identifying connected components of 'X' cells. Each battleship is essentially a connected component of cells.

Does the problem have small constraints?

• Yes: The matrix size is typically manageable (m x n board), and we can explore each cell and its connections efficiently.

DFS/backtracking?

• Yes: DFS is perfect for exploring connected components. We can use DFS to traverse each battleship (connected component) and mark visited cells to avoid counting the same battleship multiple times.

Conclusion: The flowchart suggests using DFS to explore connected components. For each unvisited 'X' cell, we initiate a DFS to explore the entire battleship, mark all its cells as visited, and increment our battleship count. This ensures each battleship is counted exactly once.

Intuition

When we first look at this problem, the natural instinct is to use DFS to explore each battleship as a connected component. We'd start from an unvisited 'X' cell, traverse all connected 'X' cells to mark the entire battleship as visited, then increment our count. This is the standard connected components approach.

However, there's a clever observation that makes this problem much simpler: we don't actually need to traverse the entire battleship.

Think about it - if battleships can only be straight lines (horizontal or vertical) and they can't touch each other, then each battleship has a unique "starting point". For consistency, let's define this starting point as the top-left corner of each battleship:

• For a horizontal battleship, it's the leftmost cell
• For a vertical battleship, it's the topmost cell
• For a single cell battleship, it's that cell itself

The key insight is: a cell is a starting point if and only if it contains 'X' AND has no 'X' above it AND has no 'X' to its left.

Why does this work? Because:

1. Every battleship has exactly one starting point (its top-left cell)
2. No non-starting cell can satisfy our condition (it would have an 'X' either above or to its left)
3. The separation rule guarantees battleships don't touch, so we don't need to worry about distinguishing between different battleships

This transforms our problem from "explore all connected components using DFS" to "count all starting points with a simple scan". We iterate through the matrix once, and for each 'X' cell at position (i, j), we check:

• Is board[i-1][j] (cell above) an 'X'? If yes, skip - this is not a starting point
• Is board[i][j-1] (cell to the left) an 'X'? If yes, skip - this is not a starting point
• Otherwise, we found a starting point - increment the counter

This approach is elegant because it leverages the problem's constraints (battleships are straight lines and don't touch) to avoid the complexity of DFS traversal entirely. We're essentially counting "heads" of battleships rather than exploring their entire "bodies".

Solution Approach

Following our intuition of counting battleship "starting points", let's implement the solution step by step:

1. Initialize variables:

m, n = len(board), len(board[0])  # Get board dimensions
ans = 0  # Counter for battleships

2. Iterate through each cell: We scan the entire board from top to bottom, left to right:

for i in range(m):
    for j in range(n):

3. Apply the starting point detection logic:

For each cell at position (i, j), we check three conditions:

Condition 1: Skip empty cells

if board[i][j] == '.':
    continue

If the current cell is empty, it can't be part of a battleship, so we move to the next cell.

Condition 2: Check if there's an 'X' above

if i > 0 and board[i - 1][j] == 'X':
    continue

If we're not in the first row (i > 0) and the cell directly above is 'X', then the current cell is part of a vertical battleship but not its starting point. The starting point would be somewhere above.

Condition 3: Check if there's an 'X' to the left

if j > 0 and board[i][j - 1] == 'X':
    continue

If we're not in the first column (j > 0) and the cell directly to the left is 'X', then the current cell is part of a horizontal battleship but not its starting point. The starting point would be somewhere to the left.

4. Count the starting point: If the current cell passes all checks (it's an 'X' with no 'X' above or to the left), it must be a battleship's starting point:

ans += 1

Time Complexity: O(m × n) where m and n are the dimensions of the board. We visit each cell exactly once.

Space Complexity: O(1) as we only use a constant amount of extra space for our counter and loop variables. We don't need any additional data structures like visited arrays or recursion stacks.

The beauty of this solution lies in its simplicity - by recognizing that we only need to count starting points rather than explore entire battleships, we avoid the overhead of DFS traversal while still accurately counting all battleships on the board.

Example Walkthrough

Let's walk through a small example to illustrate how the solution counts battleships by identifying their starting points.

Consider this 4x5 board:

. X . . X
X X X . .
. . . X .
X . X X X

We'll scan through each cell from top-left to bottom-right, checking if each 'X' cell is a battleship's starting point.

Row 0:

• (0,0): '.' - skip empty cell
• (0,1): 'X' - No 'X' above (first row), no 'X' to left. This is a starting point! Count = 1
• (0,2): '.' - skip empty cell
• (0,3): '.' - skip empty cell
• (0,4): 'X' - No 'X' above (first row), no 'X' to left. This is a starting point! Count = 2

Row 1:

• (1,0): 'X' - No 'X' above, no 'X' to left (first column). This is a starting point! Count = 3
• (1,1): 'X' - Has 'X' above at (0,1), so not a starting point - skip
• (1,2): 'X' - No 'X' above, but has 'X' to left at (1,1), so not a starting point - skip
• (1,3): '.' - skip empty cell
• (1,4): '.' - skip empty cell

Row 2:

• (2,0): '.' - skip empty cell
• (2,1): '.' - skip empty cell
• (2,2): '.' - skip empty cell
• (2,3): 'X' - No 'X' above, no 'X' to left. This is a starting point! Count = 4
• (2,4): '.' - skip empty cell

Row 3:

• (3,0): 'X' - No 'X' above, no 'X' to left (first column). This is a starting point! Count = 5
• (3,1): '.' - skip empty cell
• (3,2): 'X' - No 'X' above, no 'X' to left. This is a starting point! Count = 6
• (3,3): 'X' - Has 'X' above at (2,3), so not a starting point - skip
• (3,4): 'X' - No 'X' above, but has 'X' to left at (3,3), so not a starting point - skip

Final count: 6 battleships

Let's verify by identifying each battleship:

1. Vertical battleship at column 1, rows 0-1: Starting point (0,1) ✓
2. Single cell battleship at (0,4): Starting point (0,4) ✓
3. Horizontal battleship at row 1, columns 0-2: Starting point (1,0) ✓
4. Vertical battleship at column 3, rows 2-3: Starting point (2,3) ✓
5. Single cell battleship at (3,0): Starting point (3,0) ✓
6. Horizontal battleship at row 3, columns 2-4: Starting point (3,2) ✓

Each battleship has exactly one starting point (its top-left cell), and our algorithm correctly identifies all of them by checking for the absence of 'X' cells above and to the left.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n), where m is the number of rows and n is the number of columns in the board. The algorithm uses two nested loops to iterate through every cell in the board exactly once. For each cell, it performs constant-time operations (checking the cell value and potentially checking two adjacent cells), resulting in a total time complexity of O(m × n).

Space Complexity: O(1). The algorithm only uses a constant amount of extra space for variables m, n, ans, i, and j, regardless of the input size. No additional data structures that scale with the input are created, making the space complexity constant.

Common Pitfalls

Pitfall 1: Attempting to Mark or Modify the Board

The Mistake: Many developers instinctively try to mark visited cells or modify the board to track which cells have been processed:

# WRONG APPROACH - Modifying the board
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':
                count += 1
                # Trying to mark the entire battleship as visited
                # This destroys the board and makes subsequent checks fail
                board[i][j] = '.'
                # Mark rest of battleship...

Why It Fails:

• The problem likely expects the board to remain unchanged (follow-up constraint)
• Modifying the board breaks the logic for checking adjacent cells
• Creates unnecessary complexity when the simple "starting point" approach suffices

The Fix: Stick to the read-only approach - just check if a cell is a starting point without modifying anything.

Pitfall 2: Over-Complicating with DFS/BFS

The Mistake: Implementing unnecessary traversal algorithms when the problem has a simpler solution:

# OVERLY COMPLEX - Using DFS
def countBattleships(self, board: List[List[str]]) -> int:
    visited = set()
    count = 0
  
    def dfs(i, j):
        if (i, j) in visited or i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
            return
        if board[i][j] == '.':
            return
        visited.add((i, j))
        dfs(i+1, j)
        dfs(i, j+1)
        # ... more DFS logic
  
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] == 'X' and (i, j) not in visited:
                dfs(i, j)
                count += 1

Why It's Problematic:

• Uses O(m×n) extra space for the visited set
• Much more complex code that's harder to debug
• Slower due to function call overhead
• Overkill for a problem that can be solved with simple iteration

The Fix: Recognize that counting starting points is sufficient - no need to explore the entire battleship.

Pitfall 3: Incorrect Boundary Checking Order

The Mistake: Checking board values before verifying boundaries:

# WRONG - Can cause IndexError
if board[i-1][j] == 'X' and i > 0:  # Checks board BEFORE boundary
    continue

# WRONG - Another variation
if i >= 1 and board[i-1][j] == 'X':  # Using >= 1 instead of > 0 is fine,
    continue                          # but be consistent throughout

Why It Fails:

• When i = 0, accessing board[i-1][j] attempts to access board[-1][j], which in Python gives the last row (unexpected behavior)
• In other languages, this could cause an array out-of-bounds exception

The Fix: Always check boundaries first using short-circuit evaluation:

# CORRECT - Boundary check comes first
if i > 0 and board[i-1][j] == 'X':
    continue

Pitfall 4: Misunderstanding the Starting Point Logic

The Mistake: Counting end points or middle points instead of consistently using top-left corners:

# WRONG - Inconsistent counting logic
if board[i][j] == 'X':
    # Checking if it's an end point (bottom-right)
    if (i == len(board)-1 or board[i+1][j] == '.') and \
       (j == len(board[0])-1 or board[i][j+1] == '.'):
        count += 1

Why It Fails:

• Makes the logic unnecessarily complex
• Easy to miss edge cases
• Harder to verify correctness

The Fix: Consistently use the top-left corner as the starting point. This ensures each battleship is counted exactly once and the logic remains simple and verifiable.