MediumNo. 0419

Battleships in a Board — LeetCode 419 Python Solution

Topics
Depth-First Search, Array, Matrix
Reading time
3 min

The problem

Given an m x n matrix board where each cell is a battleship 'X' or empty '.', return the number of the battleships on board. Battleships can only be placed horizontally or vertically on board.

Example

Input
board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
Output
2

Python solution

PythonSolution
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

Complexity

Time
O(m × n)where m and n are the number of rows and columns of the matrix, respectively
Space · auxiliary
O(1)

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 419. Battleships in a Board is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0417Pacific Atlantic Water FlowMedium
0130Surrounded RegionsMedium
0200Number of IslandsMedium
0463Island PerimeterEasy
0529MinesweeperMedium
0695Max Area of IslandMedium

Frequently asked questions

How hard is LeetCode 419. Battleships in a Board?

LeetCode 419. Battleships in a Board is rated Medium on LeetCode.

What is the time complexity of LeetCode 419. Battleships in a Board?

The Python solution on this page runs in O(m × n), where m and n are the number of rows and columns of the matrix, respectively.

What is the space complexity of LeetCode 419. Battleships in a Board?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 419. Battleships in a Board cover?

LeetCode 419. Battleships in a Board is tagged Depth-First Search, Array and Matrix on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.