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.
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.
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.
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'.
Time Complexity: O(n), as each element is considered once. Space Complexity: O(1), using a few integer variables for indices and counting.
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.
| Approach | Complexity |
|---|---|
| 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 | — |
| 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 |
Maximum Enemy Forts That Can Be Captured | 2511 LeetCode | Leetcode Biweekly Contest 94 • CodeWithSunny • 1,385 views views
Watch 7 more video solutions →Practice Maximum Enemy Forts That Can Be Captured with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor