LeetCode 2511 - Maximum Enemy Forts That Can Be Captured

In this problem, we are given an array called forts, where each position represents one of three possible states: - 1 means the fort belongs to us. - 0 means there is an enemy fort. - -1 means the position is empty.

leetcodeeasyarraytwo-pointers

LeetCode Problem 2511

Difficulty: 🟢 Easy
Topics: Array, Two Pointers

Solution

Problem Understanding

In this problem, we are given an array called forts, where each position represents one of three possible states:

  • 1 means the fort belongs to us.
  • 0 means there is an enemy fort.
  • -1 means the position is empty.

We want to move our army from one of our forts to an empty position. However, the movement is only valid if every position between the starting fort and the destination is an enemy fort.

That condition is extremely important. Suppose we move from index i to index j. Then every position strictly between them must contain 0. We cannot pass through another friendly fort or another empty space.

While moving, every enemy fort passed along the way gets captured. Our goal is to compute the maximum number of enemy forts that can be captured in a single valid move.

The array length is at most 1000, which is relatively small. Even quadratic solutions are acceptable for this constraint. However, the structure of the problem allows us to design a simpler and more efficient linear-time solution.

The key observation is that a valid move always looks like this:

  • one endpoint is 1
  • the other endpoint is -1
  • every value between them is 0

Examples of valid segments:

[1,0,0,-1]
[-1,0,0,0,1]

Examples of invalid segments:

[1,0,-1,0]      # extra values after destination
[1,0,1,-1]      # another friendly fort in between
[1,-1]           # captures 0 forts

Several edge cases are important:

  • The array may contain no friendly fort at all.
  • There may be no empty space -1.
  • There may be no sequence of consecutive enemy forts between 1 and -1.
  • Adjacent 1 and -1 capture zero forts.
  • Multiple valid segments may exist, and we must return the maximum captured count.

Approaches

Brute Force Approach

A straightforward solution is to try every pair of indices (i, j) where:

  • one position contains 1
  • the other contains -1

For every such pair, we examine all positions between them to verify that they are all 0.

If the segment is valid, then the number of captured forts equals:

abs(i - j) - 1

because all positions between the endpoints are enemy forts.

This approach is correct because it explicitly checks every possible move and validates the problem constraints directly.

However, the implementation becomes inefficient because for every pair of positions we may scan the entire interval between them. In the worst case:

  • there are O(n^2) pairs
  • each validation takes O(n)

leading to O(n^3) time complexity.

Even though n <= 1000 makes this technically feasible, it is unnecessarily slow.

Optimal Approach

The better approach comes from observing the structure of valid moves.

A valid move requires:

  • one endpoint to be 1
  • the other endpoint to be -1
  • everything between them to be 0

This means we only care about consecutive non-zero positions.

Whenever we encounter a non-zero value, we compare it with the previous non-zero value we saw:

  • if they are opposite values (1 and -1)
  • then all positions between them must have been zeros
  • therefore the segment is valid

The number of captured forts is simply the distance between these two non-zero positions minus one.

This allows us to solve the problem in one pass through the array.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Checks every possible pair and validates every interval
Optimal O(n) O(1) Tracks consecutive non-zero positions in one pass

Algorithm Walkthrough

Optimal Linear Scan Algorithm

  1. Initialize two variables:
  • previous_index = -1
  • max_captured = 0

The previous_index variable stores the most recent position containing either 1 or -1. 2. Iterate through the array from left to right. 3. For each index i, skip the position if forts[i] == 0.

Enemy forts themselves are not endpoints of moves, so they do not matter directly during scanning. 4. Whenever we encounter a non-zero value, check whether we have seen another non-zero position before.

If previous_index != -1, then we compare:

  • forts[i]
  • forts[previous_index]
  1. If the two values are different, then the segment between them contains only zeros.

This works because:

  • we only update previous_index when encountering non-zero values
  • therefore there cannot be another non-zero value between them
  1. Compute the captured forts:
captured = i - previous_index - 1
  1. Update the answer:
max_captured = max(max_captured, captured)
  1. Update previous_index = i.

This prepares the algorithm for the next segment. 9. After the traversal finishes, return max_captured.

Why it works

The algorithm maintains the invariant that previous_index always points to the most recent non-zero position.

When we encounter another non-zero position:

  • all positions between the two non-zero indices must be zeros
  • otherwise we would have encountered another non-zero value earlier

Therefore, if the endpoint values are opposite (1 and -1), the segment is guaranteed to represent a valid move. Since every valid move must occur between consecutive non-zero positions, checking these pairs is sufficient to find the optimal answer.

Python Solution

from typing import List

class Solution:
    def captureForts(self, forts: List[int]) -> int:
        previous_index = -1
        max_captured = 0

        for current_index, value in enumerate(forts):
            if value == 0:
                continue

            if previous_index != -1:
                if forts[previous_index] != value:
                    captured = current_index - previous_index - 1
                    max_captured = max(max_captured, captured)

            previous_index = current_index

        return max_captured

The implementation follows the linear scan strategy exactly.

The variable previous_index stores the last seen non-zero position. During iteration, enemy forts (0) are ignored because they only matter as positions that may be captured.

Whenever we encounter another non-zero position, we compare the endpoint values. If they differ, then the segment between them is valid. The number of captured forts equals the number of positions between the two endpoints.

The expression:

current_index - previous_index - 1

computes exactly how many enemy forts lie between the two endpoints.

Finally, we update the maximum result and continue scanning.

Go Solution

func captureForts(forts []int) int {
    previousIndex := -1
    maxCaptured := 0

    for currentIndex, value := range forts {
        if value == 0 {
            continue
        }

        if previousIndex != -1 {
            if forts[previousIndex] != value {
                captured := currentIndex - previousIndex - 1

                if captured > maxCaptured {
                    maxCaptured = captured
                }
            }
        }

        previousIndex = currentIndex
    }

    return maxCaptured
}

The Go implementation mirrors the Python logic closely.

Go slices are dynamically sized views over arrays, so no special handling is required. Integer overflow is not a concern because the maximum array length is only 1000.

The manual maximum comparison replaces Python's built-in max() function.

Worked Examples

Example 1

forts = [1,0,0,-1,0,0,0,0,1]

Initial state:

previous_index = -1
max_captured = 0
Index Value Action Captured max_captured
0 1 Set previous_index = 0 - 0
1 0 Skip - 0
2 0 Skip - 0
3 -1 Opposite endpoints 2 2
4 0 Skip - 2
5 0 Skip - 2
6 0 Skip - 2
7 0 Skip - 2
8 1 Opposite endpoints 4 4

Final answer:

4

Example 2

forts = [0,0,1,-1]

Initial state:

previous_index = -1
max_captured = 0
Index Value Action Captured max_captured
0 0 Skip - 0
1 0 Skip - 0
2 1 Set previous_index = 2 - 0
3 -1 Opposite endpoints 0 0

The endpoints are adjacent, so no enemy forts are captured.

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n) The array is scanned exactly once
Space O(1) Only a few variables are used

The algorithm is optimal because every element must be inspected at least once to determine whether it participates in a valid segment. No auxiliary data structures proportional to input size are required.

Test Cases

from typing import List

class Solution:
    def captureForts(self, forts: List[int]) -> int:
        previous_index = -1
        max_captured = 0

        for current_index, value in enumerate(forts):
            if value == 0:
                continue

            if previous_index != -1:
                if forts[previous_index] != value:
                    captured = current_index - previous_index - 1
                    max_captured = max(max_captured, captured)

            previous_index = current_index

        return max_captured

solution = Solution()

assert solution.captureForts([1,0,0,-1,0,0,0,0,1]) == 4
# Multiple valid moves, choose maximum

assert solution.captureForts([0,0,1,-1]) == 0
# Adjacent endpoints capture zero forts

assert solution.captureForts([1,0,-1]) == 1
# Single enemy fort captured

assert solution.captureForts([-1,0,0,1]) == 2
# Valid move in reverse direction

assert solution.captureForts([1,1,0,-1]) == 1
# Consecutive non-zero values break earlier segment

assert solution.captureForts([1,0,0,1]) == 0
# Same endpoint values are invalid

assert solution.captureForts([-1,0,0,-1]) == 0
# Same endpoint values again invalid

assert solution.captureForts([0,0,0]) == 0
# No valid endpoints

assert solution.captureForts([1]) == 0
# Single fort only

assert solution.captureForts([-1]) == 0
# Single empty position

assert solution.captureForts([1,0,0,0,-1]) == 3
# Long valid segment

assert solution.captureForts([1,-1,1,-1]) == 0
# All valid moves capture zero forts

Test Summary

Test Why
[1,0,0,-1,0,0,0,0,1] Verifies choosing the maximum among multiple valid segments
[0,0,1,-1] Verifies zero captured forts
[1,0,-1] Smallest non-zero capture
[-1,0,0,1] Ensures reverse-direction movement works
[1,1,0,-1] Confirms consecutive non-zero values reset the segment
[1,0,0,1] Same endpoints should not count
[-1,0,0,-1] Another same-endpoint invalid case
[0,0,0] No usable forts
[1] Single-element boundary case
[-1] Single empty position
[1,0,0,0,-1] Long contiguous enemy segment
[1,-1,1,-1] Adjacent endpoints produce zero captures

Edge Cases

Adjacent 1 and -1

A very common bug is incorrectly treating adjacent endpoints as capturing one fort. Consider:

[1, -1]

There are no positions between the endpoints, so the correct answer is 0.

The implementation handles this correctly because:

captured = current_index - previous_index - 1

evaluates to:

1 - 0 - 1 = 0

Consecutive Non-Zero Values

Another tricky case occurs when non-zero values appear back to back:

[1, 1, 0, -1]

The first 1 cannot connect directly to -1 because another non-zero value interrupts the segment.

The algorithm handles this by always updating previous_index whenever a non-zero value is encountered. As a result, only consecutive non-zero endpoints are checked.

Arrays Without Valid Moves

Some arrays contain no valid movement at all:

[0,0,0]
[1,1,1]
[-1,-1]

A naive implementation might accidentally produce negative counts or invalid results.

This implementation safely returns 0 because:

  • max_captured starts at 0
  • it only updates when a valid opposite-endpoint segment is found
  • invalid segments are ignored automatically