We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Enemy Forts That Can Be Captured

Number: 2602

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an array where each element represents the state of a fort (1 for your fort, 0 for an enemy fort, and -1 for an empty position), you must determine the maximum number of enemy forts that can be captured. You capture enemy forts by moving your army from one of your forts to an empty position, ensuring that every position between the starting fort and the destination contains an enemy fort. If no valid move exists (or you have no fort under your command), return 0.

Key Insights

  • The army can only move if the endpoints are of opposite types: one must be your fort (1) and the other an empty position (-1), with only enemy forts (0) in between.
  • By iterating through the array and keeping track of the last encountered non-enemy position, we can check if a valid capturing sequence exists whenever another non-zero is found.
  • The number of enemy forts captured in a valid move equals the distance between these positions minus one.
  • A single pass solution with constant extra space (two pointers or index tracking) is both efficient and simple.

Space and Time Complexity

Time Complexity: O(n) because we scan the array once. Space Complexity: O(1) as we use only a few additional variables.

Solution

We solve the problem using a single pass iteration. We maintain a variable to remember the index and type (either 1 or -1) of the last encountered non-zero element. As we traverse the array:

  • When a non-zero element is encountered (either 1 or -1), we check if the previously stored element exists and whether its type is the opposite of the current one.
  • If it is opposite, then the segment in between (which must be all enemy forts) can be captured, and the count is the difference in indices minus one.
  • We update the maximum capture count accordingly and update the last non-zero index. This approach leverages a two-pointer idea within a single loop.

Code Solutions

def captureForts(forts):
    # Initialize the last seen index of a fort that is not an enemy (i.e., either 1 or -1)
    last_non_enemy_index = -1
    max_captured = 0
    
    # Iterate over each position in forts
    for i, fort in enumerate(forts):
        # Only consider when there is a fort present (1 or -1)
        if fort != 0:
            # If there is a previous non-enemy fort 
            if last_non_enemy_index != -1:
                # Check if current fort and previous fort are opposites (one is 1, the other is -1)
                if forts[last_non_enemy_index] * fort == -1:
                    # The enemy forts captured are the positions between them
                    captured = i - last_non_enemy_index - 1
                    max_captured = max(max_captured, captured)
            # Update the last encountered non-enemy fort's index
            last_non_enemy_index = i
    return max_captured

# Example usage:
print(captureForts([1,0,0,-1,0,0,0,0,1]))  # Output should be 4
print(captureForts([0,0,1,-1]))             # Output should be 0
← Back to All Questions