Problem statement

https://leetcode.com/problems/battleships-in-a-board/

Solution

We can do it with any graph traversal approach, like dfs or bfs in O(mn) time complexity: we need to find number of connected components. However in this case we either modify our data or use additional O(mn) memory.

We can do it without extra memory, if we use the fact that all ships are 1 x N or N x 1. Traverse our board. If we meet X, check all its 4 neighbors. If all 4 are empty, add 1 to number of found ships. If 3 out of four are empty, it means we found end of ship, so we add 0.5 to number of ships.

Complexity

Time complexity is O(mn), space is O(1). There is an 2 times improvement, if we check only left and up neighbors.

Code

class Solution:
    def countBattleships(self, board):
        m, n, ans = len(board), len(board[0]), 0
        for x in range(m):
            for y in range(n):
                if board[x][y] == ".": continue
                neibs = 0
                for dx, dy in (1, 0), (-1, 0), (0, 1), (0, -1):
                    neibs += (0 <= x + dx < m) and (0 <= y + dy < n) and (board[x+dx][y+dy] == "X")
                if neibs == 0: ans += 2
                if neibs == 1: ans += 1
                    
        return ans//2