algoadvance

Leetcode 419. Battleships in a Board

Problem Statement

You are given an m x n board 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 the board. In other words, they can only be placed in the following shapes:

Battleships should not be placed adjacent to each other, meaning no two battleships will share a side.

Example

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

    Output: 2

Clarifying Questions

  1. Is it guaranteed that there will be no invalid input (e.g., ‘X’s placed adjacently)?
    • Yes, the problem guarantees no two battleships will share a side.
  2. Can battleships be placed diagonally?
    • No, battleships can only be placed horizontally or vertically.
  3. What is the maximum size of the board?
    • The maximum size of the board will be constrained by typical problem constraints (e.g., ( m, n \le 200 )).

Code

#include <vector>

using namespace std;

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) return 0;
        int m = board.size();
        int n = board[0].size();
        int count = 0;
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'X') {
                    if (i > 0 && board[i-1][j] == 'X') continue;
                    if (j > 0 && board[i][j-1] == 'X') continue;
                    count++;
                }
            }
        }
        
        return count;
    }
};

Strategy

  1. Traversal: Iterate through each cell in the grid.
  2. Counting Condition: Increment the count of battleships only if the current cell is ‘X’ and it is not a continuation of a battleship from the top or left. This ensures that we only count the first cell in a horizontal or vertical battleship sequence.
  3. Skip Continuations: Skip counting further cells in the same battleship.

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI