LeetCode 419: Battleships in a Board Solution in Python – A Step-by-Step Guide

What Is LeetCode 419: Battleships in a Board?

In LeetCode 419: Battleships in a Board, you’re given an m × n grid board where each cell is either 'X' (part of a battleship) or '.' (empty water). Battleships are placed horizontally or vertically, with at least one cell separating them (no adjacent or diagonal touching). Your task is to return the number of battleships present. For example, in [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]], there are 2 ships: a horizontal one at [0,0] and a vertical one at [0,3] to [2,3]. You can assume the board is valid per the rules.

Problem Statement

• Input: An m × n character matrix board.
• Output: An integer—the number of battleships.
• Rules:
• 'X' represents battleship parts, '.' is empty.
• Ships are horizontal or vertical, no diagonal parts.
• No adjacent ships (horizontally, vertically, or diagonally).

Constraints

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

Examples

• Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
• Output: 2 (one horizontal, one vertical).
• Input: board = [["."]]
• Output: 0 (no ships).
• Input: board = [["X","X","X"]]
• Output: 1 (one horizontal ship).

Understanding the Problem: Counting the Fleet

To solve LeetCode 419: Battleships in a Board in Python, we need to count distinct battleships in a grid, where each ship is a contiguous row or column of 'X's, separated from others. A naive idea might be to scan every cell and trace each ship—but we can do better by leveraging the placement rules! We’ll use:

• Best Solution (Single-Pass Counting): O(mn) time, O(1) space—counts heads efficiently.
• Alternative Solution (DFS Marking): O(mn) time, O(mn) space—explores each ship fully.

Let’s dive into the single-pass solution with a clear, step-by-step explanation.

Best Solution: Single-Pass Counting

Why This Is the Best Solution

The single-pass counting method is the top pick because it’s fast—O(mn) time, O(1) space—and brilliantly simple. It scans the grid once, counting only the “head” of each battleship (topmost for vertical, leftmost for horizontal) by checking if an 'X' has no 'X' above or to its left. This avoids double-counting and uses the no-adjacency rule to skip marking. It’s like spotting the captain of each ship without charting the whole crew!

How It Works

Think of the grid as a naval map you’re scanning:

• Step 1: Scan Row by Row:
• Iterate through each cell from top-left to bottom-right.
• Step 2: Count Heads:
• For each 'X':
• Check above (r-1, c) and left (r, c-1).
• If both are '.' or out of bounds, it’s a ship’s head—count it.
• Step 3: Why This Works:
• No-adjacency rule ensures each ship has a unique head (top or left 'X').
• Single pass avoids revisiting or extra storage.
• It’s like counting ship bows without mapping their full lengths!

Step-by-Step Example

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

• Grid:

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

• Scan:
• (0,0) = 'X': Above (-1,0) out, left (0,-1) out, count = 1 (horizontal ship head).
• (0,1) = '.', skip.
• (0,2) = '.', skip.
• (0,3) = 'X': Above (-1,3) out, left (0,2) = '.', count = 2 (vertical ship head).
• (1,3) = 'X': Above (0,3) = 'X', skip (part of vertical ship).
• (2,3) = 'X': Above (1,3) = 'X', skip.
• Result: count = 2.

Example: board = [["X","X","X"]]

• Scan:
• (0,0) = 'X': Above out, left out, count = 1.
• (0,1) = 'X': Left (0,0) = 'X', skip.
• (0,2) = 'X': Left (0,1) = 'X', skip.
• Result: 1.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        if not board or not board[0]:
            return 0

        # Step 1: Get dimensions
        m, n = len(board), len(board[0])

        # Step 2: Count heads in single pass
        count = 0
        for r in range(m):
            for c in range(n):
                if board[r][c] == 'X':
                    # Check above and left
                    if (r == 0 or board[r-1][c] == '.') and \
                       (c == 0 or board[r][c-1] == '.'):
                        count += 1

        return count

• Line 4-5: Handle empty board, return 0.
• Line 8: Get grid size (m rows, n cols).
• Line 11-16: Scan grid:
• Line 12-13: Loop through each cell.
• Line 14: If 'X':
• Line 15-16: Check if head:
• Above: r == 0 (top edge) or board[r-1][c] == '.'.
• Left: c == 0 (left edge) or board[r][c-1] == '.'.
• If both true, increment count.
• Line 18: Return total battleships.
• Time Complexity: O(mn)—one pass through grid.
• Space Complexity: O(1)—just a counter.

This is like spotting ship captains with a single radar sweep!

Alternative Solution: DFS Marking

Why an Alternative Approach?

The DFS marking method uses depth-first search to explore and mark each battleship fully, counting as it finds new ones. It’s O(mn) time and O(mn) space—more thorough but uses extra memory. It’s like sending scouts to map out each ship’s full shape!

How It Works

Picture it as charting the fleet:

• Step 1: Use a visited set or modify grid.
• Step 2: DFS from each unvisited 'X', mark ship cells.
• Step 3: Count each new ship start.

Step-by-Step Example

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

• DFS:
• (0,0): 'X', DFS right/down, mark [0,0], count = 1.
• (0,3): 'X', DFS down, mark [0,3], [1,3], [2,3], count = 2.
• Result: 2.

Code for DFS Approach

Copy codeclass Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        if not board:
            return 0

        m, n = len(board), len(board[0])
        visited = set()
        count = 0

        def dfs(r, c):
            if (r < 0 or r >= m or c < 0 or c >= n or 
                (r, c) in visited or board[r][c] == '.'):
                return
            visited.add((r, c))
            # Check right and down (horizontal or vertical)
            dfs(r, c + 1)
            dfs(r + 1, c)

        for r in range(m):
            for c in range(n):
                if board[r][c] == 'X' and (r, c) not in visited:
                    dfs(r, c)
                    count += 1

        return count

• Time Complexity: O(mn)—each cell visited once.
• Space Complexity: O(mn)—visited set.

It’s a full ship explorer!

Comparing the Two Solutions

• Single-Pass Counting (Best):
• Pros: O(mn), O(1), fast and lean.
• Cons: Relies on rules.
• DFS Marking (Alternative):
• Pros: O(mn), O(mn), explicit mapping.
• Cons: More space.

Single-pass wins for efficiency.

Additional Examples and Edge Cases

• [["."]]: 0.
• [["X"]]: 1.
• [["X",".","X"]]: 2.

Single-pass handles all.

Complexity Breakdown

• Single-Pass: Time O(mn), Space O(1).
• DFS: Time O(mn), Space O(mn).

Single-pass is the champ.

Key Takeaways

• Single-Pass: Count heads!
• DFS: Map it out!
• Battleships: Rules steer.
• Python Tip: Loops rock—see [Python Basics](/python/basics).

Final Thoughts: Spot That Fleet

LeetCode 419: Battleships in a Board in Python is a naval counting quest. Single-pass counting zips through it, while DFS maps it fully. Want more grid fun? Try LeetCode 200: Number of Islands or LeetCode 694: Number of Distinct Islands. Ready to scan? Head to Solve LeetCode 419 on LeetCode and count those ships today!