How do you solve Battleships in a Board on LeetCode?

Battleships in a Board (LeetCode #419) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(m * n) time complexity and O(1) space complexity. Key insight: Battleships are separated by at least one cell, which allows us to only count the starting cells.

What is the brute force solution for Battleships in a Board?

The brute force approach for Battleships in a Board is Brute Force, with O(m * n) time complexity and O(1) space complexity. The brute force approach involves scanning each cell in the board and counting the battleships by checking if a cell is the starting point of a battleship. This means we will look for 'X' cells and ensure they are not preceded by another 'X' in the same row or column. The optimal Optimal Solution approach improves this to O(m * n).

What algorithm or data structure is used to solve Battleships in a Board?

Battleships in a Board uses the following concepts: Array, Depth-First Search, Matrix. The recommended patterns to study are: Array, Matrix.

What are the interview tips for Battleships in a Board?

Clarify the problem statement and constraints before jumping into coding. Think about edge cases, like empty boards or boards with no battleships. Explain your thought process and approach clearly as you code.

What are common mistakes when solving Battleships in a Board?

Not checking the boundaries of the board, which can lead to index errors. Counting all 'X' cells instead of only the starting points of battleships.

#419

Battleships in a Board

Medium

ArrayDepth-First SearchMatrixArrayMatrix

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(m * n)	O(m * n)
Space	O(1)	O(1)

💡

Intuition

Time O(m * n)Space O(1)

The optimal solution also involves scanning the board, but it counts battleships in a single pass while ensuring that we only count the starting cell of each battleship. This is efficient because we avoid unnecessary checks after finding a battleship's starting point.

⚙️

Algorithm

5 steps

1Step 1: Initialize a counter to zero.
2Step 2: Loop through each cell in the board.
3Step 3: When an 'X' is found, check if it's the first 'X' in its row or column. If so, increment the counter.
4Step 4: Continue until all cells are processed.
5Step 5: Return the counter as the number of battleships.

solution.py9 lines

1def countBattleships(board):
2    if not board:
3        return 0
4    count = 0
5    for i in range(len(board)):
6        for j in range(len(board[0])):
7            if board[i][j] == 'X' and (i == 0 or board[i-1][j] == '.') and (j == 0 or board[i][j-1] == '.'):
8                count += 1
9    return count

ℹ

Complexity note: The time complexity remains O(m * n) as we still need to check each cell. The space complexity is O(1) since we are only using a few variables for counting.

1Battleships are separated by at least one cell, which allows us to only count the starting cells.
2We can efficiently count battleships by checking only the first 'X' in each row and column.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.