Battleships in a Board

Medium
1560.

Battleships in a Board

Battleships in a Board is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon, Microsoft and Meta interviews.

board is an m x n grid given as m strings, where 'X' is part of a battleship and '.' is open water.

Every battleship is a straight line of cells: 1 x k (horizontal) or k x 1 (vertical) for some k >= 1. Two battleships never touch along an edge — at least one water cell separates them horizontally and vertically (they may meet diagonally).

Return the number of battleships on the board.

Example 1

Input
board = ["X..X","...X","XX.X"]
Output
3
Explanation
A single-cell ship at the top-left, a vertical ship in the last column and a horizontal ship of length 2 at the bottom-left.

Example 2

Input
board = ["."]
Output
0

Example 3

Input
board = ["X.X",".X."]
Output
3
Explanation
Ships that meet only at corners are separate ships.

Constraints

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] is 'X' or '.'
  • the board is a valid arrangement of battleships

Follow-up: Can you count them in one pass with O(1) extra memory and without modifying the board?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} board
 * @return {number}
 */
var countBattleships = function(board) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Battleships in a Board — Solution in Python, Java & C++

Battleships in a Board solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Battleships in a Board is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon, Microsoft and Meta interviews.

Problem statement

board is an m x n grid given as m strings, where 'X' is part of a battleship and '.' is open water.

Every battleship is a straight line of cells: 1 x k (horizontal) or k x 1 (vertical) for some k >= 1. Two battleships never touch along an edge — at least one water cell separates them horizontally and vertically (they may meet diagonally).

Return the number of battleships on the board.

Example 1

Input: board = ["X..X","...X","XX.X"]
Output: 3
Explanation: A single-cell ship at the top-left, a vertical ship in the last column and a horizontal ship of length 2 at the bottom-left.

Example 2

Input: board = ["."]
Output: 0

Example 3

Input: board = ["X.X",".X."]
Output: 3
Explanation: Ships that meet only at corners are separate ships.

Constraints

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] is 'X' or '.'
  • the board is a valid arrangement of battleships

Follow-up: Can you count them in one pass with O(1) extra memory and without modifying the board?

Hints for Battleships in a Board

  1. Hint 1

    Flood-filling each group of 'X' cells works, but the shapes are so restricted that you do not need to.

  2. Hint 2

    Every ship has exactly one top-left cell — its first cell in reading order.

  3. Hint 3

    Count the 'X' cells whose upper neighbour and left neighbour are both not 'X'.

How to solve Battleships in a Board

Count each ship once at its head — the cell with no 'X' directly above it or directly to its left.

Approach

  1. Scan every cell (i, j).
  2. Skip it unless it is 'X'.
  3. Skip it if (i-1, j) is 'X' or (i, j-1) is 'X' — it continues a ship already counted.
  4. Otherwise add one.

Why it works

A horizontal ship's cells, other than the first, all have an 'X' to their left; a vertical ship's have one above. The first cell of a ship has neither, because ships are straight and no other ship touches it along an edge. So exactly one cell per ship passes the test.

Complexity

  • Time — O(m · n)
  • Space — O(1)

Pitfalls

  • Diagonal neighbours do not join ships — check only above and to the left.
  • Guard the first row and the first column before looking up or left.
  • This trick relies on the board being valid; on arbitrary shapes you would need a flood fill.

Reference solution

Python

from typing import List

def countBattleships(board: List[str]) -> int:
    ships = 0
    for i in range(len(board)):
        for j in range(len(board[i])):
            if board[i][j] != 'X':
                continue
            if i > 0 and board[i - 1][j] == 'X':
                continue
            if j > 0 and board[i][j - 1] == 'X':
                continue
            ships += 1
    return ships

Java

public static int countBattleships(String[] board) {
    int ships = 0;
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length(); j++) {
            if (board[i].charAt(j) != 'X') continue;
            if (i > 0 && board[i - 1].charAt(j) == 'X') continue;
            if (j > 0 && board[i].charAt(j - 1) == 'X') continue;
            ships++;
        }
    }
    return ships;
}

C++

int countBattleships(vector<string>& board) {
    int ships = 0;
    for (int i = 0; i < (int)board.size(); i++) {
        for (int j = 0; j < (int)board[i].size(); j++) {
            if (board[i][j] != 'X') continue;
            if (i > 0 && board[i - 1][j] == 'X') continue;
            if (j > 0 && board[i][j - 1] == 'X') continue;
            ships++;
        }
    }
    return ships;
}

JavaScript

var countBattleships = function(board) {
    var ships = 0;
    for (var i = 0; i < board.length; i++) {
        for (var j = 0; j < board[i].length; j++) {
            if (board[i][j] !== 'X') continue;
            if (i > 0 && board[i - 1][j] === 'X') continue;
            if (j > 0 && board[i][j - 1] === 'X') continue;
            ships++;
        }
    }
    return ships;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Depth-First Search (DFS)