Maximum Enemy Forts That Can Be Captured - Practice Coding Problems

Maximum Enemy Forts That Can Be Captured - Problem

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 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.

Input & Output

Example 1 — Basic Capture

$ Input: forts = [1,0,0,-1,0,0,0,-1]

› Output: 4

💡 Note: Move army from position 0 (fort 1) to position 7 (empty -1), capturing 4 enemy forts at positions 1,2,4,5,6. Path: 1→0→0→-1→0→0→0→-1 captures enemies at positions 4,5,6 (3 enemies) or from position 3 to end capturing 3 enemies.

Example 2 — No Valid Path

$ Input: forts = [0,0,1,0]

› Output: 0

💡 Note: No valid path exists because there's no empty position (-1) to move to from the friendly fort at position 2.

Example 3 — Multiple Options

$ Input: forts = [1,0,0,-1,1,0,-1]

› Output: 2

💡 Note: Can move from position 0 to position 3 capturing 2 enemies, or from position 4 to position 6 capturing 1 enemy. Maximum is 2.

Constraints

1 ≤ forts.length ≤ 1000
-1 ≤ forts[i] ≤ 1

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with 1 (friendly), 0 (enemy), -1 (empty) positions

Find Valid Paths

Look for paths from 1 to -1 through only 0s

Count Maximum

Return the maximum enemies captured in any valid path

Key Takeaway

🎯 Key Insight: Valid moves must go between different boundary types (1↔-1) through consecutive enemies only

Asked in

a Amazon 12 M Microsoft 8

The key insight is to find valid paths from friendly forts (1) to empty positions (-1) that pass through only enemy forts (0). We can use a single-pass two-pointer approach to scan for sequences like 1→0s→-1 or -1→0s→1, counting the enemies in between. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Paths	O(n³)	O(1)	Check every possible path from each friendly fort to every empty position
Two Pointers - Single Pass Optimization	O(n)	O(1)	Scan array once to find valid sequences between different fort types

Brute Force - Check All Paths — Algorithm Steps

Find all friendly forts (positions with value 1)
Find all empty positions (positions with value -1)
For each pair, check if path between them contains only enemy forts
Count enemy forts in valid paths and track maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Sources

Identify all friendly forts (1) as potential starting points

Find Targets

Identify all empty positions (-1) as potential destinations

Check Paths

For each source-target pair, verify path contains only enemies (0)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* forts, int n) {
    int maxCapture = 0;
    
    // Check all possible paths
    for (int i = 0; i < n; i++) {
        if (forts[i] == 1) { // Start from friendly fort
            for (int j = 0; j < n; j++) {
                if (forts[j] == -1 && i != j) { // End at empty position
                    // Check path between i and j
                    int start = (i < j) ? i : j;
                    int end = (i > j) ? i : j;
                    int valid = 1;
                    int enemyCount = 0;
                    
                    for (int k = start + 1; k < end; k++) {
                        if (forts[k] == 0) {
                            enemyCount++;
                        } else {
                            valid = 0;
                            break;
                        }
                    }
                    
                    if (valid && enemyCount > maxCapture) {
                        maxCapture = enemyCount;
                    }
                }
            }
        }
    }
    
    return maxCapture;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int forts[100];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && (token[0] == '-' || (token[0] >= '0' && token[0] <= '9'))) {
            forts[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(forts, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each of n positions, we check n other positions, and for each pair we scan up to n elements between them

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables to track positions and counts

✓ Linear Space

12.0K Views

Medium Frequency

~15 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Paths — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler