#2511

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Maximum Enemy Forts That Can Be Captured

Find the maximum number of enemy forts that can be captured by moving your army using two-pointer scanning with invariant tracking.

array two pointers

Problem Statement

You are given an integer array forts of length n representing fort positions along a line. Each element can be -1 for enemy forts, 0 for empty positions, or 1 for your forts. Your goal is to determine the maximum number of enemy forts you can capture by moving your army from one of your forts to an empty position.

While moving your army, every consecutive enemy fort passed in the path is captured. You must consider only moves that start from your fort and end at a valid empty position without skipping any enemy forts in between. The task is to return the maximum enemy forts captured in a single valid move.

Examples

Example 1

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

Output: 4

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

Since no enemy fort can be captured, 0 is returned.

Constraints

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

Solution Approach

Two-pointer scan from left to right

Initialize two pointers at the start of the array. Move the right pointer forward until a fort is found or the end is reached, counting consecutive enemy forts between your fort and the empty position. Update the maximum captured count whenever a valid move is detected.

Reverse scan from right to left

Repeat the same process in reverse, scanning from the end of the array to the beginning. This ensures all potential capture sequences are considered, including moves that were missed in the left-to-right pass due to array boundaries.

Invariant tracking for efficient counting

Maintain an invariant that tracks the last seen fort position and the count of enemy forts in between. Only reset the count when a move is invalid or a new fort of your army is encountered. This avoids double-counting and ensures the algorithm runs in linear time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The algorithm scans the array twice with linear two-pointer passes, so time complexity is O(n). Space complexity is O(1) since only counters and pointers are used.

What Interviewers Usually Probe

Check if you can identify sequences of enemy forts between your forts and empty positions.
Use two-pointer scanning to efficiently traverse the array and count captures.
Keep track of valid moves without double-counting or skipping enemy forts.

Common Pitfalls or Variants

Common pitfalls

Forgetting to count only enemy forts between a valid start and end position.
Resetting counters incorrectly, leading to missed maximum captures.
Assuming diagonal or non-consecutive moves are allowed, which violates the problem constraints.

Follow-up variants

Find the maximum number of enemy forts captured if multiple armies can move simultaneously.
Calculate captures when forts can only move to adjacent empty positions.
Determine maximum captures when some enemy forts are immune and cannot be captured.

FAQ

What is the best way to track captured enemy forts?

Use two-pointer scanning with an invariant counter that increments for consecutive enemy forts and resets only when encountering your own fort or invalid positions.

Can I move my army over empty positions without capturing forts?

No, only sequences starting from your fort and passing through consecutive enemy forts to an empty position are valid moves.

Does the algorithm handle arrays with all empty positions or forts?

Yes, the two-pointer approach will return 0 captures when no valid enemy fort sequences exist.

Is there a difference between left-to-right and right-to-left scans?

Scanning in both directions ensures that moves at array edges or from the last fort are considered for maximum capture.

Why is this considered a two-pointer scanning pattern problem?

Because the solution relies on maintaining two pointers to efficiently traverse the array while counting consecutive enemy forts between your fort and empty positions.

terminal

Solution

Solution 1: Two Pointers

We use a pointer $i$ to traverse the array $forts$, and a pointer $j$ to start traversing from the next position of $i$ until it encounters the first non-zero position, i.e., $forts[j] \neq 0$. If $forts[i] + forts[j] = 0$, then we can move the army between $i$ and $j$, destroying $j - i - 1$ enemy forts. We use the variable $ans$ to record the maximum number of enemy forts that can be destroyed.

1

2

3

4

5

6

7

8

9

10

11

12

13

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

Continue Practicing

#2503 maximum number of points from grid queries #2491 divide players into teams of equal skill #2540 minimum common value