Simple PYTHON O(n) time O(1) space 90% inline explanation

• ``````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
``````

• Think you mean O(n^2) time

• @haxet na bro. n is the number of grid spots. so o(n).

• Is it not still making n^2 calls or does the continue change that? (I've actually never used continue before)

• @haxet my point is that u could say it was running at o(r * c) time or... if u set n = r * c, then you can say it's running at o(n) time. the continue statements don't impact that. they're just a slight optimization.

• @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)

• @haxet but it is linear to the number of grid spaces for a given situation, which is right. n is vague in this question, i will agree on that. but i don't see any reason to pick one interpretation over another.

• This post is deleted!

• @haxet what are u even talking about

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.