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


  • 1
    V
    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
    

  • 0
    L

    Think you mean O(n^2) time


  • 0
    V

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


  • 0
    L

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


  • 0
    V

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


  • 1
    L

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


  • 0
    V

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


  • 0
    L
    This post is deleted!

  • 0
    V

    @haxet what are u even talking about


Log in to reply
 

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