Scale Engineer

Maximum Enemy Forts That Can Be Captured

Easy
#2291Time: O(n), where `n` is the length of the `forts` array. We iterate through the array only once.Space: O(1), as we only use a constant amount of extra space for variables like `maxForts` and `lastIndex`.
Patterns
Two Pointers
Data structures
Array

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

A much more efficient approach is to iterate through the array just once. We can keep track of the last position where we saw a non-enemy fort (1 or -1). When we encounter another non-enemy fort, we check if it forms a valid capture sequence with the last one we saw, which implies all forts in between were enemy forts.

Algorithm

  • Initialize max_forts to 0.
  • Initialize last_index to -1 to indicate we haven't seen a 1 or -1 yet.
  • Iterate through the forts array with index i from 0 to n-1.
  • If forts[i] is 0, it's a potential captured fort, so we continue to the next element.
  • If forts[i] is 1 or -1:
    • Check if last_index is valid (not -1) and if forts[i] is opposite to forts[last_index] (i.e., forts[i] == -forts[last_index]).
    • If this condition is true, it means we have found a valid capture segment between last_index and i. The elements between them must be zeros because our loop skips over 0s and would have updated last_index if it encountered another 1 or -1.
    • Calculate the number of captured forts: count = i - last_index - 1.
    • Update max_forts = max(max_forts, count).
    • In any case, when we see a 1 or -1, we update last_index to the current index i to mark the start of a new potential segment.
  • Return max_forts.

Walkthrough

The core idea is that a valid capture can only occur between a fort under our command (1) and an empty position (-1), with only enemy forts (0) in between. This forms a pattern like 1, 0, 0, ..., -1 or -1, 0, 0, ..., 1. We can find the longest stretch of zeros between a 1 and a -1 by scanning the array linearly. We use a variable, last_index, to store the index of the most recently seen 1 or -1. As we iterate, if the current element is a 1 or a -1, we check if last_index has been set and if the fort at last_index is of the opposite type (forts[i] == -forts[last_index]). If so, we've found a valid segment. The number of captured forts is the distance between the current index i and last_index, minus one. We update our maximum count. Regardless, whenever we encounter a 1 or -1, we update last_index to i, as this position now becomes the starting point for the next potential capture segment.

class Solution {    public int captureForts(int[] forts) {        int maxForts = 0;        int lastIndex = -1;        for (int i = 0; i < forts.length; i++) {            // We only care about non-zero positions            if (forts[i] != 0) {                // Check if we have a previous fort and if it's of the opposite type                if (lastIndex != -1 && forts[i] == -forts[lastIndex]) {                    // The number of zeros is the distance between indices minus 1                    maxForts = Math.max(maxForts, i - lastIndex - 1);                }                // The current position becomes the new starting point for the next segment                lastIndex = i;            }        }        return maxForts;    }}

Complexity

Time

O(n), where `n` is the length of the `forts` array. We iterate through the array only once.

Space

O(1), as we only use a constant amount of extra space for variables like `maxForts` and `lastIndex`.

Trade-offs

Pros

  • Highly efficient with a linear time complexity, making it the optimal solution.

  • Requires minimal extra space.

Cons

  • The logic is slightly more abstract than the brute-force approach, requiring careful handling of the last_index state.

Solutions

class Solution {public  int captureForts(int[] forts) {    int n = forts.length;    int ans = 0, i = 0;    while (i < n) {      int 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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem