Skip to main content
Talentd

Maximum Enemy Forts That Can Be Captured - Solution & Explanation

EasyArrayTwo Pointers20 min read
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You receive an integer array forts where 1 represents your fort, -1 represents an enemy fort, and 0 represents an empty position. You can move from one of your forts toward an enemy fort and capture every empty position in between, but only if the path contains only zeros. The task is to compute the maximum number of enemy forts you can capture in a single move.

Approach 1: Two-Pointer Linear Scan (O(n) time, O(1) space)

The key observation: a valid capture happens only when two non‑zero forts appear with opposite values (1 and -1) and all elements between them are 0. Scan the array once while remembering the index of the last non‑zero fort. When another non‑zero value appears, check if its sign differs from the previous one. If so, the number of capturable forts equals the distance between them minus one (i - lastIndex - 1). Update the maximum result and move the pointer forward. This linear scan works because any valid segment must start and end at the closest pair of opposite forts with only zeros between them.

This approach uses constant extra memory and processes each element once. It naturally fits problems involving contiguous segments in an array. The pointer tracking technique is a simplified variant of classic two pointers where one pointer marks the last fort and the other scans forward.

Approach 2: Sliding Window Method (O(n) time, O(1) space)

The problem can also be framed as a constrained window over the array. Maintain a window between two indices containing only zeros, while tracking the nearest non‑zero boundaries. Expand the right boundary while counting zeros. When a non‑zero value appears, check whether the left boundary contains the opposite fort type. If the pair is valid (1 and -1), update the maximum captured count with the number of zeros inside the window. Then reset the window starting from the current fort.

This technique resembles a classic sliding window pattern where you maintain a contiguous region satisfying a condition. While slightly more conceptual than the direct scan, it generalizes well to problems where you track segments of valid values inside arrays.

Recommended for interviews: The Two-Pointer Linear Scan is the expected solution. It shows you recognized the core constraint: only the nearest opposite forts matter, and everything in between must be zeros. Brute-force scanning of every pair would be O(n^2), which is unnecessary. A single pass with pointer tracking demonstrates strong pattern recognition and leads to the optimal O(n) time and O(1) space solution.

Approach 1: Two-Pointer Linear Scan

This approach involves iterating over the 'forts' array using a single loop while keeping track of segments of enemy forts enclosed between two of your forts. Anytime you encounter one of your forts, check how many enemy forts have been encountered since the last of your forts was found, and update the maximum if this is a new maximum. Reset the enemy count whenever you encounter a '-1', which interrupts a sequence of capturable forts.

The solution iterates through the array and counts a segment of zeros after a '1', resetting the count when encountering '-1'. If a segment ends with another '1', the count of zeros in between is checked against the maximum recorded count and updated if it's higher.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the array, as we are traversing the array once. Space Complexity: O(1), as there are no data structures being used that scale with the input size.

Try this approach in the editor →

Approach 2: Sliding Window Method

This approach leverages the sliding window concept to look for segments of zeros between two '1's, shifting the window when necessary. As you iterate through the array, if you encounter a -1, reset your window or pause the counting until you find another '1'. This method provides an alternative perspective through the sliding window mechanism to solve the same problem more intuitively.

In this C implementation of the sliding window approach, we maintain a running count of zeros when starting from a '1'. This count is continuously checked against a maximum, and invalid windows are reset when encountering '-1'.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), as each element is considered once. Space Complexity: O(1), using a few integer variables for indices and counting.

Try this approach in the editor →

Approach 3: 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.

The time complexity is O(n), and the space complexity is O(1). Where n is the length of the array forts.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two-Pointer Linear Scan

Time Complexity: O(n), where n is the length of the array, as we are traversing the array once. Space Complexity: O(1), as there are no data structures being used that scale with the input size.

Sliding Window Method

Time Complexity: O(n), as each element is considered once. Space Complexity: O(1), using a few integer variables for indices and counting.

Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-Pointer Linear ScanO(n)O(1)Best general solution; single pass when tracking the previous non-zero fort
Sliding Window MethodO(n)O(1)Useful when modeling the problem as contiguous zero segments between forts

Video Solution

Maximum Enemy Forts That Can Be Captured | 2511 LeetCode | Leetcode Biweekly Contest 94 • CodeWithSunny • 1,425 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Maximum Enemy Forts That Can Be Captured easy or hard?
Maximum Enemy Forts That Can Be Captured is categorized as an Easy problem. The main challenge is recognizing that only adjacent non-zero forts with opposite values can form a valid capture segment. Once that observation is made, the implementation becomes a straightforward O(n) scan.
Maximum Enemy Forts That Can Be Captured Python/Java solution
Most solutions implement a single loop through the array while tracking the last non-zero index. Python, Java, C++, and JavaScript implementations follow the same logic: update the maximum distance when two opposite forts appear with only zeros between them. The algorithm runs in O(n) time with constant space.
How to solve Maximum Enemy Forts That Can Be Captured in O(n)?
Iterate through the array and store the index of the last non-zero element. Whenever you encounter another non-zero fort, check if its value is different from the previous one. If the pair forms a valid 1 and -1 combination, compute the distance between them minus one to count the zeros. Track the maximum value during the scan.
What is the best approach for Maximum Enemy Forts That Can Be Captured?
The best approach is a linear scan using a two-pointer style technique. Track the index of the previous non-zero fort and compare it with the current fort while iterating through the array. When the two forts are opposite (1 and -1), the number of capturable forts equals the zeros between them. This runs in O(n) time and O(1) space.
Is Maximum Enemy Forts That Can Be Captured asked at Google/Amazon/Meta?
This problem follows a common array pattern frequently used in technical interviews at companies like Amazon, Google, and Meta. While the exact question may vary, similar problems involving two pointers, array scanning, and counting segments often appear in coding interviews.
What data structure is used in Maximum Enemy Forts That Can Be Captured?
The problem primarily uses a simple array traversal with pointer tracking. No additional data structures such as hash maps or stacks are required. The logic relies on comparing adjacent non-zero elements and counting zeros between them.
What is the time complexity of Maximum Enemy Forts That Can Be Captured?
The optimal solution runs in O(n) time because the array is scanned once from left to right. Each element is processed exactly once while maintaining the last seen fort index. The space complexity is O(1) since only a few variables are stored.

Ready to solve this problem?

Practice Maximum Enemy Forts That Can Be Captured with our built-in code editor and test cases.

Practice on FleetCode
Previous

Max Consecutive Ones

Next

Max Consecutive Ones III