Battleships in a Board – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

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. 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).

Example 1:

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

Example 2:

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

Constraints:

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

C++ Battleships in a Board LeetCode Solution

int countBattleships(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) { return 0; }
        int m = board.size(), n = board[0].size(), cnt = 0;
        
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)
                cnt += board[r][c] == 'X' && (r == 0 || board[r - 1][c] != 'X') && (c == 0 || board[r][c - 1] != 'X');
        
        return cnt;
}

Java Battleships in a Board LeetCode Solution

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

Python 3 Battleships in a Board LeetCode Solution

class Solution(object):
    def countBattleships(self, board):
        if len(board) == 0: return 0
        m, n = len(board), len(board[0])
        count = 0
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'X' and (i == 0 or board[i-1][j] == '.') and (j == 0 or board[i][j-1] == '.'):
                    count += 1
        return count

Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264

Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195

Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140

Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96

Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66

Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40

Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31

Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21

Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16

Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9

Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7

Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4

Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3

Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1

Leave a comment below

Related posts:

Queens on Board – HackerRank Solution Search Insert Position – LeetCode Solution Sort Colors – LeetCode Solution Find Peak Element – LeetCode Solution Peeking Iterator – LeetCode Solution Find K Pairs with Smallest Sums – LeetCode Solution