algoadvance

Leetcode 2511. Maximum Enemy Forts That Can Be Captured

Problem Statement

You are given a 0-indexed integer array forts of length n representing the positions of fortifications along a line, where:

You want to capture all enemy forts by sending your army from one of your forts to an enemy fort through empty positions. Your army can only capture enemy forts that are directly reachable from one of your forts without passing through any other fort. More formally, you can only capture an enemy fort k if you can find an integer i such that:

Return the maximum number of enemy forts that can be captured.

Clarifying Questions

  1. Can there be multiple friendly (1) or enemy (-1) forts?
    • Yes, the array can have multiple instances of both types of forts.
  2. What will be the maximum length of the array forts?
    • The maximum length is not directly provided, but for the sake of complexity analysis, assume it can be quite large ( (e.g., 10^5) ).
  3. Is there guaranteed to be any 1 or -1 in the array?
    • No, the array might not contain any 1 or -1.

Strategy

  1. Traverse the array and whenever you encounter a 1 (friendly fort), look for the nearest -1 (enemy fort) to both its left and right sides.
  2. Check if all the positions between the friendly fort and the potential enemy fort are empty (0). If they are, calculate the distance between the two and keep track of the maximum captured forts.
  3. Continue the process until the end of the array.

Time Complexity

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int captureForts(vector<int>& forts) {
        int n = forts.size();
        int maxCaptured = 0;
        
        for (int i = 0; i < n; ++i) {
            if (forts[i] == 1) {
                // Check right side
                int j = i + 1;
                while (j < n && forts[j] == 0) {
                    ++j;
                }
                if (j < n && forts[j] == -1) {
                    maxCaptured = max(maxCaptured, j - i - 1);
                }
                
                // Check left side
                j = i - 1;
                while (j >= 0 && forts[j] == 0) {
                    --j;
                }
                if (j >= 0 && forts[j] == -1) {
                    maxCaptured = max(maxCaptured, i - j - 1);
                }
            }
        }
        
        return maxCaptured;
    }
};

Explanation

  1. Initialize maxCaptured to 0 to keep track of the maximum number of enemy forts that can be captured.
  2. Iterate through the array:
    • If the current element is 1, then:
      • Look to the right (increment j), and check if all elements up to the next non-zero are 0 and if it ends in -1 (enemy fort). Update maxCaptured.
      • Look to the left (decrement j), and check similarly.
  3. Return maxCaptured as the result.

This strategy ensures that we find the maximum reachable enemy fort directly from any friendly fort by traversing only once through the array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI