Maximum Enemy Forts That Can Be Captured - Video Solutions
Maximum Enemy Forts That Can Be Captured | 2511 LeetCode | Leetcode Biweekly Contest 94
Maximum Enemy Forts That Can Be Captured - Video Solution
Watch 6 video solutions for Maximum Enemy Forts That Can Be Captured, a easy level problem involving Array, Two Pointers. This walkthrough by CodeWithSunny has 1,425 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
-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.
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 |