Maximum Enemy Forts That Can Be Captured solution and explanation
5 more videos on this problem
Maximum Enemy Forts That Can Be Captured | 2511 LeetCode | Leetcode Biweekly Contest 94CodeWithSunny · 8:42 · 1K views
Leetcode BiWeekly contest 94 - Easy - Maximum Enemy Forts That Can Be CapturedPrakhar Agrawal · 7:19 · 787 views
2511. Maximum Enemy Forts That Can Be Captured (Leetcode Easy)Programming Live with Larry · 6:26 · 564 views
LeetCode | 2511. Maximum Enemy Forts That Can Be Captured | Two PointerCompl3x · 14:42 · 552 views
LeetCode 2511. Maximum Enemy Forts That Can Be Captured | Simple Explanation with CodeDeep Tech · 4:41 · 517 views
Leecode Biweekly Contest 94 | 2511.Max Enemy Forts That Can Be Captured| 2512.Reward Top K StudentsCodingVerse · 14:18 · 79 views
The problem
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:
-1represents there is no fort at theithposition.0indicates there is an enemy fort at theithposition.1indicates the fort at theiththe 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
kwheremin(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.
def max_captured_forts(forts):
max_forts = 0
count = 0
last_fort_index = -1
for i in range(len(forts)):
if forts[i] == 1:
last_fort_index = i
count = 0
elif forts[i] == 0:
if last_fort_index != -1:
count += 1
if (i < len(forts) - 1 and forts[i + 1] == 1) or (i == len(forts) - 1 and forts[i] == 0):
max_forts = max(max_forts, count)
last_fort_index = -1
else:
last_fort_index = -1
count = 0
return max_forts
forts = [1, 0, 0, -1, 0, 0, 0, 0, 1]
print(max_captured_forts(forts))public class MaxCapturedForts {
public static int maxCapturedForts(int[] forts) {
int maxForts = 0, count = 0;
int lastFortIndex = -1;
for (int i = 0; i < forts.length; i++) {
if (forts[i] == 1) {
lastFortIndex = i;
count = 0;
} else if (forts[i] == 0) {
if (lastFortIndex != -1) {
count++;
if ((i < forts.length - 1 && forts[i + 1] == 1) || (i == forts.length - 1 && forts[i] == 0)) {
maxForts = Math.max(maxForts, count);
lastFortIndex = -1;
}
}
} else {
lastFortIndex = -1;
count = 0;
}
}
return maxForts;
}
public static void main(String[] args) {
int[] forts = {1, 0, 0, -1, 0, 0, 0, 0, 1};
System.out.println(maxCapturedForts(forts));
}
}#include <vector>
#include <iostream>
using namespace std;
int maxCapturedForts(vector<int>& forts) {
int maxForts = 0, count = 0;
int lastFortIndex = -1;
for (int i = 0; i < forts.size(); ++i) {
if (forts[i] == 1) {
lastFortIndex = i;
count = 0;
} else if (forts[i] == 0) {
if (lastFortIndex != -1) {
++count;
if ((i < forts.size() - 1 && forts[i + 1] == 1) || (i == forts.size() - 1 && forts[i] == 0)) {
maxForts = max(maxForts, count);
lastFortIndex = -1;
}
}
} else {
lastFortIndex = -1;
count = 0;
}
}
return maxForts;
}
int main() {
vector<int> forts = {1, 0, 0, -1, 0, 0, 0, 0, 1};
cout << maxCapturedForts(forts) << endl;
return 0;
}function maxCapturedForts(forts) {
let maxForts = 0;
let count = 0;
let lastFortIndex = -1;
for (let i = 0; i < forts.length; i++) {
if (forts[i] === 1) {
lastFortIndex = i;
count = 0;
} else if (forts[i] === 0) {
if (lastFortIndex !== -1) {
count++;
if ((i < forts.length - 1 && forts[i + 1] === 1) || (i === forts.length - 1 && forts[i] === 0)) {
maxForts = Math.max(maxForts, count);
lastFortIndex = -1;
}
}
} else {
lastFortIndex = -1;
count = 0;
}
}
return maxForts;
}
const forts = [1, 0, 0, -1, 0, 0, 0, 0, 1];
console.log(maxCapturedForts(forts));#include <stdio.h>
int findMaxCapturedForts(int* forts, int n) {
int maxForts = 0, count = 0;
int lastFortIndex = -1;
for (int i = 0; i < n; i++) {
if (forts[i] == 1) {
lastFortIndex = i;
count = 0;
} else if (forts[i] == 0) {
if (lastFortIndex != -1) {
count++;
if ((i < n - 1 && forts[i + 1] == 1) || (i == n - 1 && forts[i] == 0)) {
if (count > maxForts) {
maxForts = count;
}
lastFortIndex = -1; // Reset on finding a sequence end
}
}
} else { // Encounter -1
lastFortIndex = -1;
count = 0;
}
}
return maxForts;
}
int main() {
int forts[] = {1, 0, 0, -1, 0, 0, 0, 0, 1};
int size = sizeof(forts) / sizeof(forts[0]);
int result = findMaxCapturedForts(forts, size);
printf("%d\n", result);
return 0;
}using System;
class MaxCapturedForts {
public static int MaxCapturedForts(int[] forts) {
int maxForts = 0, count = 0;
int lastFortIndex = -1;
for (int i = 0; i < forts.Length; i++) {
if (forts[i] == 1) {
lastFortIndex = i;
count = 0;
} else if (forts[i] == 0) {
if (lastFortIndex != -1) {
count++;
if ((i < forts.Length - 1 && forts[i + 1] == 1) || (i == forts.Length - 1 && forts[i] == 0)) {
maxForts = Math.Max(maxForts, count);
lastFortIndex = -1;
}
}
} else {
lastFortIndex = -1;
count = 0;
}
}
return maxForts;
}
static void Main(string[] args) {
int[] forts = { 1, 0, 0, -1, 0, 0, 0, 0, 1 };
Console.WriteLine(MaxCapturedForts(forts));
}
}The Python solution leverages Python's syntax simplicity to iterate over the array, maintaining the logic from previous solutions. It counts the zeros surrounded by 1s and updates the maximum count as necessary.
Time Complexity: O(n), for a single pass through the input list. Space Complexity: O(1), just using a few integers.
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.
def sliding_max_captured_forts(forts):
max_forts = 0
current_window_count = 0
start = -1
for i in range(len(forts)):
if forts[i] == 1:
if start != -1:
max_forts = max(max_forts, current_window_count)
current_window_count = 0
start = i
elif forts[i] == 0 and start != -1:
current_window_count += 1
else:
current_window_count = 0
start = -1
return max_forts
forts = [1, 0, 0, -1, 0, 0, 0, 0, 1]
print(sliding_max_captured_forts(forts))public class SlidingMaxCapturedForts {
public static int slidingMaxCapturedForts(int[] forts) {
int maxForts = 0, currentWindowCount = 0;
int start = -1;
for (int i = 0; i < forts.length; i++) {
if (forts[i] == 1) {
if (start != -1) {
maxForts = Math.max(maxForts, currentWindowCount);
currentWindowCount = 0;
}
start = i;
} else if (forts[i] == 0 && start != -1) {
currentWindowCount++;
} else {
currentWindowCount = 0;
start = -1;
}
}
return maxForts;
}
public static void main(String[] args) {
int[] forts = {1, 0, 0, -1, 0, 0, 0, 0, 1};
System.out.println(slidingMaxCapturedForts(forts));
}
}#include <vector>
#include <iostream>
using namespace std;
int slidingMaxCapturedForts(vector<int>& forts) {
int maxForts = 0, currentWindowCount = 0;
int start = -1;
for (int i = 0; i < forts.size(); ++i) {
if (forts[i] == 1) {
if (start != -1) {
maxForts = max(maxForts, currentWindowCount);
currentWindowCount = 0;
}
start = i;
} else if (forts[i] == 0 && start != -1) {
++currentWindowCount;
} else {
currentWindowCount = 0;
start = -1;
}
}
return maxForts;
}
int main() {
vector<int> forts = {1, 0, 0, -1, 0, 0, 0, 0, 1};
cout << slidingMaxCapturedForts(forts) << endl;
return 0;
}function slidingMaxCapturedForts(forts) {
let maxForts = 0;
let currentWindowCount = 0;
let start = -1;
for (let i = 0; i < forts.length; i++) {
if (forts[i] === 1) {
if (start !== -1) {
maxForts = Math.max(maxForts, currentWindowCount);
currentWindowCount = 0;
}
start = i;
} else if (forts[i] === 0 && start !== -1) {
currentWindowCount++;
} else {
currentWindowCount = 0;
start = -1;
}
}
return maxForts;
}
const forts = [1, 0, 0, -1, 0, 0, 0, 0, 1];
console.log(slidingMaxCapturedForts(forts));#include <stdio.h>
int slidingMaxCapturedForts(int* forts, int n) {
int maxForts = 0, currentWindowCount = 0;
int start = -1; // Represents the start of a valid window
for (int i = 0; i < n; i++) {
if (forts[i] == 1) {
if (start != -1) {
maxForts = currentWindowCount > maxForts ? currentWindowCount : maxForts;
currentWindowCount = 0;
}
start = i;
} else if (forts[i] == 0 && start != -1) {
currentWindowCount++;
} else {
currentWindowCount = 0;
start = -1;
}
}
return maxForts;
}
int main() {
int forts[] = {1, 0, 0, -1, 0, 0, 0, 0, 1};
int size = sizeof(forts) / sizeof(forts[0]);
int result = slidingMaxCapturedForts(forts, size);
printf("%d\n", result);
return 0;
}using System;
class SlidingMaxCapturedForts {
public static int SlidingMaxCapturedForts(int[] forts) {
int maxForts = 0, currentWindowCount = 0;
int start = -1;
for (int i = 0; i < forts.Length; i++) {
if (forts[i] == 1) {
if (start != -1) {
maxForts = Math.Max(maxForts, currentWindowCount);
currentWindowCount = 0;
}
start = i;
} else if (forts[i] == 0 && start != -1) {
currentWindowCount++;
} else {
currentWindowCount = 0;
start = -1;
}
}
return maxForts;
}
static void Main(string[] args) {
int[] forts = { 1, 0, 0, -1, 0, 0, 0, 0, 1 };
Console.WriteLine(SlidingMaxCapturedForts(forts));
}
}This Python code presents an example of employing a sliding window to assess capturable forts. The solution shifts whenever a '-1' is met or proper conditions dictate it to update.
Time Complexity: O(n), on account of looping through the list once. Space Complexity: O(1), for no additional space requirement beyond integer variables.
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.
function captureForts(forts: number[]): number {
const n = forts.length;
let ans = 0;
let i = 0;
while (i < n) {
let j = i + 1;
if (forts[i] !== 0) {
while (j < n && forts[j] === 0) {
j++;
}
if (j < n && forts[i] + forts[j] === 0) {
ans = Math.max(ans, j - i - 1);
}
}
i = j;
}
return ans;
}func captureForts(forts []int) (ans int) {
n := len(forts)
i := 0
for i < n {
j := i + 1
if forts[i] != 0 {
for j < n && forts[j] == 0 {
j++
}
if j < n && forts[i]+forts[j] == 0 {
ans = max(ans, j-i-1)
}
}
i = j
}
return
}impl Solution {
pub fn capture_forts(forts: Vec<i32>) -> i32 {
let n = forts.len();
let mut ans = 0;
let mut i = 0;
while i < n {
let mut j = i + 1;
if forts[i] != 0 {
while j < n && forts[j] == 0 {
j += 1;
}
if j < n && forts[i] + forts[j] == 0 {
ans = ans.max(j - i - 1);
}
}
i = j;
}
ans as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-Pointer Linear Scan | Time Complexity: O(n), for a single pass through the input list. Space Complexity: O(1), just using a few integers. |
| Sliding Window Method | Time Complexity: O(n), on account of looping through the list once. Space Complexity: O(1), for no additional space requirement beyond integer variables. |
| Two Pointers | – |
Complexity analysis
| 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 |
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.