class Solution(object):
def countBattleships(self, board):
"""
:type board: List[List[str]]
:rtype: int
"""
cols = len(board)
rows = len(board[0])
ct = 0
for c in xrange(cols):
for r in xrange(rows):
# We count a battleship only first time we see it. If a battleship piece 'X'
# is encountered, it is only new if neither the upper or left components are not also
# pieces of the same battleship. These prior indices are guarenteed to already be explored by
# the time we get to the current board index.
if board[c][r] != 'X':
continue
if r > 0 and board[c][r  1] == 'X':
continue
if c > 0 and board[c  1][r] == 'X':
continue
ct += 1
return ct
Simple PYTHON O(n) time O(1) space 90% inline explanation


@vikram4 I mean I guess, but n is vague and you're saying that n increases linearly with time which is not right. It increases by the (#ofrows*#ofcols)