Battleships in a Board - Practice Coding Problems

Battleships in a Board - Problem

Given an m x n matrix board where each cell is a battleship 'X' or empty '.', return the number of battleships on the board.

Battleships can only be placed horizontally or vertically on the board. In other words, they can only be made of the shape 1 x k (1 row, k columns) or k x 1 (k rows, 1 column), where k can be of any size.

At least one horizontal or vertical cell separates between two battleships (i.e., there are no adjacent battleships).

Input & Output

Example 1 — Mixed Battleships

$ Input: board = [["X",".",".","X"],[".",...,".","X"],[".",...,".","X"]]

› Output: 2

💡 Note: First battleship is single cell at (0,0). Second battleship is vertical at positions (0,3), (1,3), (2,3). Total count is 2.

Example 2 — Single Ship

$ Input: board = [["X"]]

› Output: 1

💡 Note: Single cell battleship at position (0,0). Total count is 1.

Example 3 — No Ships

$ Input: board = [["."]]

› Output: 0

💡 Note: No battleship cells found in the grid. Total count is 0.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Matrix with X (battleship) and . (empty) cells

Identify Ships

Find connected X cells forming battleships

Count Total

Return number of distinct battleships found

Key Takeaway

🎯 Key Insight: Count ship starting positions instead of exploring entire ships

Asked in

M Microsoft 15 A Apple 12

The key insight is that we can count battleships by finding their top-left corners instead of exploring entire ships. Best approach is the Top-Left Corner Detection with optimal Time: O(m×n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ DFS Exploration	O(m×n)	O(m×n)	Use DFS to explore each battleship completely and mark visited cells
Top-Left Corner Detection	O(m×n)	O(1)	Count battleships by detecting only their top-left corner positions

DFS Exploration — Algorithm Steps

Iterate through each cell in the matrix
When finding an unvisited 'X', start DFS exploration
Mark all connected 'X' cells as visited during DFS
Increment battleship count for each DFS start

Visualization

Tap to expand

Step-by-Step Walkthrough

Find X

Locate first unvisited X cell

DFS Explore

Explore all connected X cells

Count Ship

Mark as visited and count one battleship

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

void dfs(char** board, bool** visited, int i, int j, int m, int n) {
    if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || board[i][j] == '.') {
        return;
    }
    
    visited[i][j] = true;
    dfs(board, visited, i+1, j, m, n);
    dfs(board, visited, i-1, j, m, n);
    dfs(board, visited, i, j+1, m, n);
    dfs(board, visited, i, j-1, m, n);
}

int solution(char** board, int m, int n) {
    if (m == 0 || n == 0) return 0;
    
    bool** visited = (bool**)malloc(m * sizeof(bool*));
    for (int i = 0; i < m; i++) {
        visited[i] = (bool*)calloc(n, sizeof(bool));
    }
    
    int count = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'X' && !visited[i][j]) {
                dfs(board, visited, i, j, m, n);
                count++;
            }
        }
    }
    
    // Free memory
    for (int i = 0; i < m; i++) {
        free(visited[i]);
    }
    free(visited);
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for small test cases
    int m = 3, n = 4; // Example dimensions
    char** board = (char**)malloc(m * sizeof(char*));
    for (int i = 0; i < m; i++) {
        board[i] = (char*)malloc(n * sizeof(char));
    }
    
    // Hardcode example for simplicity
    char data[3][4] = {{'X','.','.','X'},{'.','.','.','X'},{'.','.','.','X'}};
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] = data[i][j];
        }
    }
    
    printf("%d\n", solution(board, m, n));
    
    for (int i = 0; i < m; i++) {
        free(board[i]);
    }
    free(board);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Visit each cell once, DFS explores each X cell exactly once

✓ Linear Growth

Space Complexity

O(m×n)

Visited matrix to track explored cells

⚡ Linearithmic Space

85.0K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS Exploration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler