Watch 8 video solutions for Maximum Enemy Forts That Can Be Captured, a easy level problem involving Array, Two Pointers. This walkthrough by CodeWithSunny has 1,385 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 - 1k 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] <= 1Problem 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 | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Linear Scan | O(n) | O(1) | Best general solution; single pass when tracking the previous non-zero fort |
| Sliding Window Method | O(n) | O(1) | Useful when modeling the problem as contiguous zero segments between forts |