2511. Maximum Enemy Forts That Can Be Captured

EasyArrayTwo Pointers
Leetcode Link

Problem Description

You are given an array forts which consists of integers representing the positions of forts. The integer values can be -1, 0, or 1. Here's what they represent:

  • A -1 means no fort is present at that position.
  • A 0 indicates an enemy fort is present at that position.
  • A 1 indicates a fort under your command is present at that position.

Your objective is to move your army from one of your forts to an empty position. The conditions for the movement are:

  • Your army must travel over positions containing only enemy forts (denoted by 0).
  • You cannot pass over an empty position or a position with your fort during this move.

The question asks you to calculate the maximum number of enemy forts you can capture during such a move. If it is not possible to move your army or you don't have any forts under your command, then the maximum number is 0.

Intuition

To solve this problem, we can perform a linear scan over the array forts with the following approach:

  • Start from the first element, iterate through the array and search for a fort under your command (a 1 in the array).
  • Once a fort under your command is found, search for the next closest enemy fort (a 0), and keep counting the number of enemy forts in between.
  • If another fort under your command is found (another 1), then the number of enemy forts captured during this move would be the count of 0s found in between minus one (since we lose one position when we land on the second 1).
  • Keep track of the maximum count found throughout the entire iteration.
  • Continue this process until the end of the array is reached.

This algorithm efficiently computes the maximum number of enemy forts that can be captured because it accounts for all possible movements from each of your forts to any other eligible position in a single pass. By always choosing the move that captures the most forts, we ensure that we find the maximum possible value.

Learn more about Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following problems can be solved with backtracking (select multiple)

Solution Approach

The provided solution uses a simple one-pass algorithm to iterate over the array of forts. We make use of a while loop that runs until the end of the array. There are two pointers used in the process: i and j. Pointer i is used to locate forts under our command, and j is used to find the next fort under our command after capturing enemy forts.

Here's a step-by-step approach to the solution:

  1. Initialize two variables, i and ans, to 0. The variable i serves as a pointer to the current position in forts, and ans stores the maximum number of enemy forts captured so far.

  2. Use a while loop to traverse the forts array from the current position identified by i until the end of the array (n is the length of forts).

  3. Inside the loop, initiate a nested while loop that starts with j = i + 1. The variable j scans forward to count enemy forts:

    • If forts[i] is 1 (your fort), traverse through the array starting from i + 1 to find a subsequent 0 (enemy fort). During traversal, increment j until a 0 is not encountered (either reach another 1 or -1).

    • If the loop ends at a position j where forts[j] is 1, it means an enemy fort was captured. Thus, calculate the number of captured forts as j - i - 1. The -1 subtracts the position of the ending 1, which is not an enemy fort.

    • Update the maximum number of enemy forts captured, ans, if the current count (j - i - 1) is greater than the previous value of ans.

  4. After processing from position i to j, move the pointer i to position j and continue the algorithm until all positions are scanned. This ensures no potential fort positions are skipped and that we consider all possibilities.

  5. Finally, return the value of ans, which holds the maximum number of enemy forts captured in any possible move.

This simple algorithm is optimal because it ensures that:

  • Only forts under your command (1) are considered as the starting point for an invasion.
  • Only sequences consisting solely of enemy forts (0) are considered for capturing.
  • The number of checks is the lowest possible, as we only care about streaks of enemy forts between your forts, achieving O(n) time complexity.
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What data structure does Breadth-first search typically uses to store intermediate states?

Example Walkthrough

Let's use a small example to illustrate the solution approach given the following array forts:

1forts = [1, 0, 0, -1, 1, 0, 1]

With this array, follow the solution approach step by step:

  1. Initialize Variables: Start with i = 0 and ans = 0.

  2. Outer While Loop (Traverse forts): Begin loop from the first position.

  3. Inner While Loop (Locate Next Fort):

    • Position i = 0 has value 1, indicating a fort under your command.
    • Move to i + 1, looking for consecutive enemy forts (0).

  4. Capture Enemy Forts:

    • Moving ahead from position i = 0: We have forts[1] = 0, forts[2] = 0, and the next position forts[3] is -1, so we stop here since we cannot move over an empty position. Therefore, no enemy forts were captured in this sequence.
    • Move the pointer i to position 3. Repeat for the next portion of the array.

  5. Repeat the Process:

    • Since forts[3] = -1, we move to i = 4.
    • At i = 4 (forts[4] = 1), we have a fort under our control once again.
    • Start the inner loop from j = i + 1 = 5.
    • Move ahead: forts[5] = 0 is an enemy fort.
    • However, at j = 5 + 1 = 6, we reach forts[6] = 1, another fort under our control, and we stop.

  6. Update Maximum Captured Enemy Forts:

    • In this sequence, we have captured j - i - 1 = 6 - 4 - 1 = 1 enemy fort.
    • Update ans to the maximum of itself and the current count: ans = max(ans, 1).
    • Now, ans = 1.

  7. Continue Until the End:

    • Move i to j = 6 and continue, but we're already at the end of the array.

  8. Conclude with Results:

    • Having traversed the entire array, ans = 1 is the maximum number of enemy forts we can capture during a move.

This example shows that with the given solution approach, we can calculate the maximum number of enemy forts that the army can capture in one move, which is 1 for this particular array.

Solution Implementation

1class Solution:
2    def captureForts(self, forts: List[int]) -> int:
3        n = len(forts)  # Get the length of the forts list.
4        i = ans = 0  # Initialize pointer i to 0 and answer 'ans' to 0.
5      
6        # Iterate through the list of forts.
7        while i < n:
8            j = i + 1  # Set the pointer j to the next position after i.
9
10            # If the current fort at position i is a friendly fort (non-zero).
11            if forts[i]:
12                # Find the next friendly fort (non-zero) starting from position j.
13                while j < n and forts[j] == 0:
14                    j += 1
15              
16                # If such a fort is found and the sum of the values at i and j is 0,
17                # which means they cancel each other out.
18                if j < n and forts[i] + forts[j] == 0:
19                    # Calculate the distance between the forts, excluding the start and end points,
20                    # and update the answer 'ans' if this distance is greater.
21                    ans = max(ans, j - i - 1)
22          
23            # Move the starting pointer i to the position of j for the next iteration.
24            i = j
25      
26        # Return the maximum number of captured forts.
27        return ans
28
1class Solution {
2  
3    // Method to find the maximum number of zeroes between two non-zero numbers in an array,
4    // where the non-zero numbers sum up to zero.
5    public int captureForts(int[] forts) {
6        // Length of the array representing forts.
7        int n = forts.length;
8      
9        // This will hold the final answer: the maximum number of zeroes between capturing forts.
10        int maxZeroes = 0;
11      
12        // Index to iterate through forts array.
13        int i = 0;
14      
15        // Iterate over the array.
16        while (i < n) {
17            // Potential second fort index.
18            int nextFortIndex = i + 1;
19          
20            // Check if current fort at index i is not a zero.
21            if (forts[i] != 0) {
22                // Find the next non-zero fort.
23                while (nextFortIndex < n && forts[nextFortIndex] == 0) {
24                    ++nextFortIndex;
25                }
26              
27                // Check if the end of the array hasn't been reached and if the sum of the
28                // two non-zero forts is zero, implying opposite teams.
29                if (nextFortIndex < n && forts[i] + forts[nextFortIndex] == 0) {
30                    // Calculate the current number of zeroes.
31                    int zeroCount = nextFortIndex - i - 1;
32                  
33                    // Update maximum zeroes if the current count exceeds it.
34                    maxZeroes = Math.max(maxZeroes, zeroCount);
35                }
36            }
37          
38            // Move to the next potential fort.
39            i = nextFortIndex;
40        }
41      
42        // Return the maximum number of zeroes between two capturing forts.
43        return maxZeroes;
44    }
45}
46
1class Solution {
2public:
3    // This function calculates the maximum number of consecutive fortresses captured.
4    int captureForts(vector<int>& forts) {
5        // Get the number of fortresses
6        int fortCount = forts.size();
7        // Initialize the answer to 0
8        int maxCaptures = 0;
9        // Start iterating through the fortresses
10        int currentIndex = 0;
11
12        // Loop through all the fortresses
13        while (currentIndex < fortCount) {
14            // Next index starts just after the current one
15            int nextIndex = currentIndex + 1;
16
17            // Only check fortresses that have not been captured (non-zero values)
18            if (forts[currentIndex] != 0) {
19                // Skip all the captured fortresses (zeros) until a non-captured fortress is found
20                while (nextIndex < fortCount && forts[nextIndex] == 0) {
21                    ++nextIndex;
22                }
23                // Check if we found a fortress and the sum of the current and next fortresses is zero
24                if (nextIndex < fortCount && forts[currentIndex] + forts[nextIndex] == 0) {
25                    // Calculate the number of fortresses between current and next (exclusive)
26                    int captures = nextIndex - currentIndex - 1;
27                    // Update max captures if this is the largest so far
28                    maxCaptures = max(maxCaptures, captures);
29                }
30            }
31            // Move to the next index (could be the next non-captured fortress or the end of vector)
32            currentIndex = nextIndex;
33        }
34
35        // Return the maximum number of fortresses that can be captured consecutively
36        return maxCaptures;
37    }
38};
39
1function captureForts(forts: number[]): number {
2    const fortCount = forts.length; // Total number of forts
3    let maxDistance = 0; // This will hold the maximum distance between two forts
4    let currentIndex = 0; // Index to traverse the forts array
5
6    // Loop through the array of forts
7    while (currentIndex < fortCount) {
8        let nextIndex = currentIndex + 1; // Index for the next fort
9
10        // Ensure the current fort is not zero (zero implies the fort has already been captured)
11        if (forts[currentIndex] !== 0) {
12
13            // Find the next non-zero fort
14            while (nextIndex < fortCount && forts[nextIndex] === 0) {
15                nextIndex++;
16            }
17          
18            // Check if the current and next non-zero forts sum up to zero and if true, calculate the distance between them
19            if (nextIndex < fortCount && forts[currentIndex] + forts[nextIndex] === 0) {
20                // Update the maximum distance if the current distance is greater
21                maxDistance = Math.max(maxDistance, nextIndex - currentIndex - 1);
22            }
23        }
24      
25        // Move to the next segment of forts
26        currentIndex = nextIndex;
27    }
28
29    // Return the maximum distance found
30    return maxDistance;
31}
32
Not Sure What to Study? Take the 2-min Quiz：

Which type of traversal does breadth first search do?

Time and Space Complexity

The provided Python function captureForts calculates the maximum distance between pairs of forts, with the condition that the sum of the strengths of a pair of forts is zero, and there are only zeroes between them.

Time Complexity:

The time complexity of the function is O(n), where n is the length of the forts list. This is because the function iterates through the list only once with a single while-loop. Within the while-loop, the inner while-loop also iterates through portions of the list, but overall each element is visited at most once by either the outer or the inner loop. There are no nested loops that depend on the size of the input, hence the linear time complexity.

Space Complexity:

The space complexity is O(1) since there are only a constant number of variables used (n, i, j, ans) that do not depend on the size of the input list. No additional space that grows with the input size is allocated during the execution of the function.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫