Maximum Enemy Forts That Can Be Captured

Difficulty: Easy | Acceptance: 41.30% | Paid: No Topics: Array, Two Pointers

You are given a 0-indexed integer array forts of length n. forts[i] is -1 if it is an enemy fort, 0 if it is empty, and 1 if it is your fort.

You can move from your fort (1) to an empty fort (0), then to another empty fort, and so on, until you reach an enemy fort (-1). You cannot jump over forts.

You want to capture the maximum number of enemy forts by moving from one of your forts to an enemy fort.

Return the maximum number of enemy forts you can capture.

• Examples
• Constraints
• Brute Force
• Two Pointers

Examples

Input: forts = [1,0,0,-1,0,0,0,0,1]
Output: 4
Explanation:
- Moving from index 0 to index 3 captures 1 enemy fort. The number of empty forts moved through is 2.
- Moving from index 8 to index 3 captures 1 enemy fort. The number of empty forts moved through is 4.
The maximum is 4.

Input: forts = [0,0,1,-1,1,0,0,-1]
Output: 2
Explanation:
- Moving from index 4 to index 7 captures 1 enemy fort. The number of empty forts moved through is 2.
The maximum is 2.

Constraints

1 <= forts.length <= 1000
-1 <= forts[i] <= 1

Brute Force

Intuition For every fort that belongs to you (1), we can scan to the left and to the right to find the nearest enemy fort (-1). The distance between them (minus 1) represents the number of empty forts traversed. We keep track of the maximum such distance found.

Steps

• Initialize max_captured to 0.
• Iterate through each index i in the array.
• If forts[i] is 1 (your fort):
  • Scan Left: Initialize j = i - 1. While j is within bounds and forts[j] is 0, decrement j. If j is within bounds and forts[j] is -1, update max_captured with i - j - 1.
  • Scan Right: Initialize j = i + 1. While j is within bounds and forts[j] is 0, increment j. If j is within bounds and forts[j] is -1, update max_captured with j - i - 1.
• Return max_captured.

class Solution:
    def captureForts(self, forts: list[int]) -> int:
        n = len(forts)
        ans = 0
        for i in range(n):
            if forts[i] == 1:
                # Check left
                j = i - 1
                while j >= 0 and forts[j] == 0:
                    j -= 1
                if j >= 0 and forts[j] == -1:
                    ans = max(ans, i - j - 1)
                # Check right
                j = i + 1
                while j < n and forts[j] == 0:
                    j += 1
                if j < n and forts[j] == -1:
                    ans = max(ans, j - i - 1)
        return ans

Complexity

• Time: O(n²) - In the worst case, for every fort, we might traverse the entire array.
• Space: O(1) - We only use a few variables for storage.
• Notes: Simple to implement but inefficient for large inputs.

Two Pointers

Intuition We only care about pairs of forts where one is yours (1) and the other is the enemy’s (-1). The empty forts (0) between them determine the distance. We can iterate through the array once, keeping track of the last non-zero fort we saw. If the current non-zero fort is of the opposite type to the last one, we calculate the distance between them.

Steps

• Initialize last to -1 (to store the index of the last non-zero fort) and ans to 0.
• Iterate through the array with index i.
• If forts[i] is not 0:
  • If last is not -1 and forts[last] is not equal to forts[i] (meaning one is 1 and the other is -1):
    • Update ans with max(ans, i - last - 1).
  • Update last to i.
• Return ans.

class Solution:
    def captureForts(self, forts: list[int]) -> int:
        ans = 0
        last = -1
        for i, f in enumerate(forts):
            if f != 0:
                if last != -1 and forts[last] != f:
                    ans = max(ans, i - last - 1)
                last = i
        return ans

Complexity

• Time: O(n) - We traverse the array exactly once.
• Space: O(1) - We only use a constant amount of extra space.
• Notes: This is the optimal solution for this problem.