Maximum Enemy Forts That Can Be Captured

EASY

Description

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 i^th position.
0 indicates there is an enemy fort at the i^th position.
1 indicates the fort at the i^th 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

Checkout 2 different approaches to solve Maximum Enemy Forts That Can Be Captured. Click on different approaches to view the approach and algorithm in detail.

Single Pass Linear Scan

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.

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 Analysis

Time Complexity: O(n), where `n` is the length of the `forts` array. We iterate through the array only once.Space Complexity: O(1), as we only use a constant amount of extra space for variables like `maxForts` and `lastIndex`.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Maximum Enemy Forts That Can Be Captured. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Maximum Enemy Forts That Can Be Captured

Patterns:

Two Pointers

Data Structures:

Array