# Maximum Enemy Forts That Can Be Captured
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-enemy-forts-that-can-be-captured)
Canonical: https://scaleengineer.com/dsa/problems/maximum-enemy-forts-that-can-be-captured
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array
---
## Problem
You are given a **0-indexed** integer array `forts` of length `n` representing the positions of several forts. `forts[i]` can be `-1`, `0`, or `1` where:

* `-1` represents there is **no fort** at the `ith` position.
* `0` indicates there is an **enemy** fort at the `ith` position.
* `1` indicates the fort at the `ith` the position is under your command.

Now you have decided to move your army from one of your forts at position `i` to an empty position `j` such that:

* `0 <= i, j <= n - 1`
* The army travels over enemy forts **only**. Formally, for all `k` where `min(i,j) < k < max(i,j)`, `forts[k] == 0.`

While moving the army, all the enemy forts that come in the way are **captured**.

Return _the **maximum** number of enemy forts that can be captured_. In case it is **impossible** to move your army, or you do not have any fort under your command, return `0`_._

**Example 1:**

**Input:** forts = [1,0,0,-1,0,0,0,0,1]
**Output:** 4
**Explanation:**
- Moving the army from position 0 to position 3 captures 2 enemy forts, at 1 and 2.
- Moving the army from position 8 to position 3 captures 4 enemy forts.
Since 4 is the maximum number of enemy forts that can be captured, we return 4.

**Example 2:**

**Input:** forts = [0,0,1,-1]
**Output:** 0
**Explanation:** Since no enemy fort can be captured, 0 is returned.

**Constraints:**

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

# Approaches
## Brute Force with Triple Nested Loops
This approach systematically checks every possible pair of indices `(i, j)` in the `forts` array to see if they can form a valid move. A move is valid if one position holds one of our forts (value `1`) and the other is an empty position (value `-1`), and all positions strictly between them contain enemy forts (value `0`).
**Time:** O(n^3), where `n` is the length of the `forts` array. The two outer loops run in `O(n^2)` and the inner loop for path validation can run up to `O(n)` times in the worst case. · **Space:** O(1), as we only use a constant amount of extra space for variables.
**Pros:** Simple to understand and implement as it directly translates the problem's conditions into code.
**Cons:** Highly inefficient due to its `O(n^3)` time complexity.; Will likely result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.
### Explanation
We use three nested loops. The outer two loops iterate through all pairs of indices `(i, j)`. For each pair, we first check if `forts[i]` and `forts[j]` correspond to a valid start and end for a capture. This means one must be `1` and the other `-1`. If they form a valid pair, we use a third loop to verify that all forts between index `i` and `j` are enemy forts (value `0`). If the path is valid, we calculate the number of captured forts, which is the distance between the indices minus one (`abs(i - j) - 1`). We keep track of the maximum number of captured forts found so far and update it whenever we find a longer valid path. After checking all pairs, the maximum value found is the answer.

```java
class Solution {
    public int captureForts(int[] forts) {
        int n = forts.length;
        int maxForts = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if ((forts[i] == 1 && forts[j] == -1) || (forts[i] == -1 && forts[j] == 1)) {
                    int start = Math.min(i, j);
                    int end = Math.max(i, j);
                    boolean pathIsClear = true;
                    // This inner loop makes the complexity O(n^3)
                    for (int k = start + 1; k < end; k++) {
                        if (forts[k] != 0) {
                            pathIsClear = false;
                            break;
                        }
                    }
                    if (pathIsClear) {
                        maxForts = Math.max(maxForts, end - start - 1);
                    }
                }
            }
        }
        return maxForts;
    }
}
```
### Algorithm
- Initialize a variable `max_forts` to 0.
- Iterate through the array with an outer loop for the starting position `i` from `0` to `n-1`.
- Inside this loop, iterate with an inner loop for the ending position `j` from `0` to `n-1`.
- If `i` and `j` are the same, skip.
- Check if `forts[i]` and `forts[j]` form a valid pair for a move, i.e., one is `1` and the other is `-1`.
- If they do, start a third loop to verify the path between them. Let `start = min(i, j)` and `end = max(i, j)`.
- Iterate `k` from `start + 1` to `end - 1`. If any `forts[k]` is not `0`, the path is invalid.
- If the path is valid (all intermediate forts are `0`), calculate the number of captured forts as `end - start - 1`.
- Update `max_forts` with the maximum value found so far.
- After all loops complete, return `max_forts`.

## Single Pass Linear Scan
A much more efficient approach is to iterate through the array just once. We can keep track of the last position where we saw a non-enemy fort (`1` or `-1`). When we encounter another non-enemy fort, we check if it forms a valid capture sequence with the last one we saw, which implies all forts in between were enemy forts.
**Time:** O(n), where `n` is the length of the `forts` array. We iterate through the array only once. · **Space:** O(1), as we only use a constant amount of extra space for variables like `maxForts` and `lastIndex`.
**Pros:** Highly efficient with a linear time complexity, making it the optimal solution.; Requires minimal extra space.
**Cons:** The logic is slightly more abstract than the brute-force approach, requiring careful handling of the `last_index` state.
### Explanation
The core idea is that a valid capture can only occur between a fort under our command (`1`) and an empty position (`-1`), with only enemy forts (`0`) in between. This forms a pattern like `1, 0, 0, ..., -1` or `-1, 0, 0, ..., 1`. We can find the longest stretch of zeros between a `1` and a `-1` by scanning the array linearly. We use a variable, `last_index`, to store the index of the most recently seen `1` or `-1`. As we iterate, if the current element is a `1` or a `-1`, we check if `last_index` has been set and if the fort at `last_index` is of the opposite type (`forts[i] == -forts[last_index]`). If so, we've found a valid segment. The number of captured forts is the distance between the current index `i` and `last_index`, minus one. We update our maximum count. Regardless, whenever we encounter a `1` or `-1`, we update `last_index` to `i`, as this position now becomes the starting point for the next potential capture segment.

```java
class Solution {
    public int captureForts(int[] forts) {
        int maxForts = 0;
        int lastIndex = -1;
        for (int i = 0; i < forts.length; i++) {
            // We only care about non-zero positions
            if (forts[i] != 0) {
                // Check if we have a previous fort and if it's of the opposite type
                if (lastIndex != -1 && forts[i] == -forts[lastIndex]) {
                    // The number of zeros is the distance between indices minus 1
                    maxForts = Math.max(maxForts, i - lastIndex - 1);
                }
                // The current position becomes the new starting point for the next segment
                lastIndex = i;
            }
        }
        return maxForts;
    }
}
```
### Algorithm
- Initialize `max_forts` to 0.
- Initialize `last_index` to -1 to indicate we haven't seen a `1` or `-1` yet.
- Iterate through the `forts` array with index `i` from 0 to `n-1`.
- If `forts[i]` is `0`, it's a potential captured fort, so we continue to the next element.
- If `forts[i]` is `1` or `-1`:
  - Check if `last_index` is valid (not -1) and if `forts[i]` is opposite to `forts[last_index]` (i.e., `forts[i] == -forts[last_index]`).
  - If this condition is true, it means we have found a valid capture segment between `last_index` and `i`. The elements between them must be zeros because our loop skips over `0`s and would have updated `last_index` if it encountered another `1` or `-1`.
  - Calculate the number of captured forts: `count = i - last_index - 1`.
  - Update `max_forts = max(max_forts, count)`.
  - In any case, when we see a `1` or `-1`, we update `last_index` to the current index `i` to mark the start of a new potential segment.
- Return `max_forts`.

# Solutions
### Java

```java
class Solution {
public
  int captureForts(int[] forts) {
    int n = forts.length;
    int ans = 0, i = 0;
    while (i < n) {
      int j = i + 1;
      if (forts[i] != 0) {
        while (j < n && forts[j] == 0) {
          ++j;
        }
        if (j < n && forts[i] + forts[j] == 0) {
          ans = Math.max(ans, j - i - 1);
        }
      }
      i = j;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int captureForts(vector<int> &forts) {
    int n = forts.size();
    int ans = 0, i = 0;
    while (i < n) {
      int j = i + 1;
      if (forts[i] != 0) {
        while (j < n && forts[j] == 0) {
          ++j;
        }
        if (j < n && forts[i] + forts[j] == 0) {
          ans = max(ans, j - i - 1);
        }
      }
      i = j;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def captureForts(self, forts: List[int]) -> int: n = len(forts) i = ans = 0 while i < n: j = i + 1 if forts[i]: while j < n and forts[j] == 0: j += 1 if j < n and forts[i] + forts[j] == 0: ans = max(ans, j - i - 1) i = j return ans

```