Problem Description

You have an array forts representing positions with different types of forts. Each position can have one of three values:

• -1: Empty position (no fort)
• 0: Enemy fort
• 1: Your fort (under your command)

You want to move your army from one of your forts (position with value 1) to an empty position (position with value -1). The movement must follow these rules:

1. The army can only travel through enemy forts (positions with value 0)
2. All positions between the starting fort and destination must contain enemy forts
3. When the army moves, it captures all enemy forts along the path

The goal is to find the maximum number of enemy forts you can capture in a single move.

For example, if you have [1, 0, 0, -1, 0, 0, 0, 1], you could move from position 0 (your fort) to position 3 (empty), capturing 2 enemy forts in between. Or you could move from position 7 (your fort) to position 3 (empty), capturing 3 enemy forts. The maximum would be 3.

Return 0 if:

• You have no forts under your command
• No valid moves are possible (no path exists between your fort and an empty position through only enemy forts)

The solution uses two pointers to find all valid movement paths. For each position i that contains either your fort or an empty position, it finds the next non-enemy position j. If forts[i] + forts[j] = 0 (meaning one is 1 and the other is -1), then a valid move exists between them, capturing j - i - 1 enemy forts.

Intuition

The key insight is recognizing that a valid army movement requires exactly three components in sequence: a starting point (your fort or empty position), a path of enemy forts, and an ending point (empty position or your fort). The crucial observation is that the start and end points must be of opposite types - one must be your fort (1) and the other must be empty (-1).

Why does forts[i] + forts[j] = 0 work as our validation check? Because if one position has value 1 and the other has value -1, their sum equals zero. This elegantly captures the requirement that we need opposite endpoints for a valid move.

The two-pointer approach naturally emerges from this pattern. We can scan through the array looking for non-zero positions (potential start/end points). When we find one at position i, we look for the next non-zero position at j. Everything between them must be enemy forts by definition - if there were any non-enemy positions in between, our pointer j would have stopped earlier.

The algorithm essentially identifies all possible "segments" in the array where:

1. The segment starts and ends with non-zero values
2. Everything in between is zeros (enemy forts)
3. The start and end values are opposites (sum to zero)

By checking all such segments and tracking the maximum length minus 2 (excluding the endpoints), we find the maximum number of enemy forts that can be captured. The pointer i jumps directly to j after each check because we've already examined everything up to position j, making the algorithm efficient with O(n) time complexity.

Learn more about Two Pointers patterns.

Solution Approach

The solution uses a two-pointer technique to efficiently find all valid army movements and determine the maximum number of enemy forts that can be captured.

Algorithm Steps:

1. Initialize variables: Set pointer i = 0 to traverse the array, and ans = 0 to track the maximum enemy forts captured.

2. Outer loop: While i < n, process each position:

   • Start with j = i + 1 as the second pointer
   • Check if forts[i] is non-zero (potential starting point)

3. Inner traversal: If forts[i] != 0:

   • Move pointer j forward while forts[j] == 0 (enemy forts)
   • This finds the next non-zero position after i

4. Validate movement: Once j stops at a non-zero position:

   • Check if j < n (within bounds) and forts[i] + forts[j] == 0
   • This condition ensures one position is 1 (your fort) and the other is -1 (empty)
   • If valid, the number of captured enemy forts is j - i - 1

5. Update maximum: Compare with current ans and keep the maximum value

6. Advance pointer: Set i = j to skip already processed positions

Why this works:

• The algorithm identifies segments of consecutive zeros (enemy forts) bounded by non-zero values
• By checking forts[i] + forts[j] == 0, we ensure valid movement between a fort and empty position
• Setting i = j after each iteration avoids redundant checks and maintains O(n) time complexity
• Each position is visited at most twice (once by i, once by j), ensuring linear time

Example walkthrough with forts = [1, 0, 0, -1, 0, 1]:

• i=0, forts[0]=1, j moves to 3 where forts[3]=-1
• 1 + (-1) = 0 ✓, captured forts: 3 - 0 - 1 = 2
• i=3, forts[3]=-1, j moves to 5 where forts[5]=1
• (-1) + 1 = 0 ✓, captured forts: 5 - 3 - 1 = 1
• Maximum captured: 2

Example Walkthrough

Let's walk through the solution with forts = [1, 0, 0, -1, 0, 0, 0, 1]

Initial state:

• i = 0, ans = 0
• Array: [1, 0, 0, -1, 0, 0, 0, 1] ^i

First iteration:

• forts[i] = 1 (non-zero, potential start point)
• Set j = i + 1 = 1
• Move j through enemy forts: j=1 (0), j=2 (0), j=3 (-1, stop!)
• Check validity: forts[0] + forts[3] = 1 + (-1) = 0 ✓
• Enemy forts captured: 3 - 0 - 1 = 2
• Update ans = 2, set i = 3

Second iteration:

• i = 3, forts[i] = -1 (non-zero)
• Set j = 4
• Move j through enemy forts: j=4 (0), j=5 (0), j=6 (0), j=7 (1, stop!)
• Check validity: forts[3] + forts[7] = -1 + 1 = 0 ✓
• Enemy forts captured: 7 - 3 - 1 = 3
• Update ans = 3, set i = 7

Third iteration:

• i = 7, forts[i] = 1 (non-zero)
• Set j = 8, but j >= n, so increment i++
• i = 8 >= n, loop ends

Result: Maximum enemy forts captured = 3

The algorithm found two valid moves:

• Fort at position 0 → Empty at position 3 (captures 2 enemy forts)
• Empty at position 3 → Fort at position 7 (captures 3 enemy forts)

The maximum is 3, achieved by moving from position 7 to position 3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm uses a two-pointer approach where pointer i traverses through the array. In each iteration:

• When forts[i] is non-zero (either 1 or -1), the inner while loop moves pointer j forward to find the next non-zero element
• After the inner loop completes, pointer i is set to j, ensuring each element is visited at most once

Even though there's a nested loop structure, each element in the array is examined exactly once. The outer loop moves i through the array, and the inner loop moves j, but i jumps to j after each iteration, preventing revisiting elements. Therefore, the total number of operations is proportional to n.

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

• Variables i, j, ans, and n are integer variables
• No additional data structures are created
• The space usage doesn't scale with the input size

The algorithm operates in-place without requiring additional memory that grows with the input size, resulting in constant space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Problem Statement

A critical pitfall is misinterpreting what values represent what in the array:

• -1 represents an empty position (NOT an enemy fort)
• 0 represents an enemy fort
• 1 represents your fort

Many developers mistakenly think -1 represents enemy forts since it's negative, leading to completely incorrect logic. The solution captures enemy forts (0s) between your fort (1) and an empty position (-1).

Solution: Carefully read the problem statement and add clear comments documenting what each value represents.

2. Incorrect Movement Validation

A common mistake is checking for valid movement using conditions like:

# WRONG: This doesn't ensure opposite fort types
if forts[i] != 0 and forts[j] != 0:
    captured = j - i - 1

This would incorrectly count movements between two of your own forts [1, 0, 0, 1] or two empty positions [-1, 0, 0, -1] as valid.

Solution: Use forts[i] + forts[j] == 0 to ensure one position is 1 and the other is -1.

3. Off-by-One Error in Counting

Developers often make mistakes when counting captured forts:

# WRONG: Includes the endpoints
captured = j - i

# WRONG: Only subtracts one endpoint
captured = j - i

Solution: The correct formula is j - i - 1 to exclude both endpoints and count only the enemy forts in between.

4. Inefficient Pointer Movement

Setting i = i + 1 instead of i = j after processing leads to O(n²) complexity:

# INEFFICIENT: Revisits positions unnecessarily
while i < n:
    # ... process ...
    i += 1  # WRONG: Should be i = j

Solution: Always set i = j after processing to skip already examined positions and maintain O(n) complexity.

5. Missing Edge Cases

Forgetting to handle arrays with:

• No friendly forts: [0, 0, -1, 0]
• No empty positions: [1, 0, 0, 0]
• No enemy forts between valid endpoints: [1, -1, 0, 0]

Solution: The algorithm naturally handles these by returning 0 when no valid moves exist, but ensure your implementation doesn't assume these elements exist.