Problem Statement in English

You’re given an integer array forts of size n where each element is either 0, 1, or -1.

  • 0 represents an empty cell.
  • 1 represents a fort you own.
  • -1 represents an enemy fort.

You’re only allowed to travel through cells that contain enemies.

Your task is to return the maximum number of forts you can capture.

Approach

This is more about implementation than anything else. So I’ll let the code do the explaining.

Solution in Python


class Solution:
    def captureForts(self, forts: List[int]) -> int:
        best = 0
        currentCount = 0

        countActive = False

        # forward pass
        for i in range(len(forts)):
            if forts[i] == 1:
                # we've found a camp we own
                # we may start conquering from here
                countActive = True
                # reset currentCount to 0
                currentCount = 0
                pass
            elif forts[i] == 0 and countActive:
                # we've got our army with us and
                # we've captured a new spot
                currentCount += 1
                pass
            else:
                # it's -1
                # then it's a valid place to stop the army at
                best = max(currentCount, best)
                # but since this was not an enemy camp, 
                # we cannot move any further from here
                countActive = False
                currentCount = 0
                pass
            pass

        # backward pass
        for i in range(len(forts) - 1, -1, -1):
            if forts[i] == 1:
                # we've found a camp we own
                # we may start conquering from here
                countActive = True
                # reset currentCount to 0
                currentCount = 0
                pass
            elif forts[i] == 0 and countActive:
                # we've got our army with us and
                # we've captured a new spot
                currentCount += 1
                pass
            else:
                # it's -1
                # then it's a valid place to stop the army at
                best = max(currentCount, best)
                # but since this was not an enemy camp, 
                # we cannot move any further from here
                countActive = False
                currentCount = 0
                pass
            pass

        return best

Complexity

  • Time: $O(n)$
    Since we iterate over $n$ elements at most.

  • Space: $O(1)$
    Since we only use a few integer variables.

And we are done.