Maximum Enemy Forts That Can Be Captured
Abstract Representation of the Problem
You are given an ordered list of integers, where each integer is either 1, 0, or 1. The 1s represent empty spaces, the 0s represent a particular type of resource, and the 1s represent a different type of resource.
You are allowed to make one operation: choose two resources of type 1 such that every element between them is a resource of type 0 or an empty space (1). This operation “captures” all the type 0 resources between the chosen pair of type 1 resources.
The objective is to determine the maximum number of type 0 resources that can be captured with a single operation. If no such operation is possible, return 0.
This abstract representation maintains the structure and essence of the problem without the realworld details of forts, armies, and enemy forces. Instead, it uses a more neutral language of resources and operations.
Key Insight
Let’s go through the problem using the abstract representation. Here we’re dealing with an ordered list of integers which are 1, 0, or 1.
A “move” or operation is valid when you choose two nonzero elements (either 1, 1 or 1, 1) such that all elements between them are 0 or 1, and this operation “captures” all the 0s.
When we are looking for the maximum number of 0s that can be captured, it means we are essentially interested in the largest segment of the list that starts and ends with nonzero elements (either 1, 1 or 1, 1) and contains only 0s in between.
In other words, we are interested in counting the number of zeros between two opposite nonzero numbers (1 and 1, or 1 or 1).
This is because every zero within this segment represents a captured resource, and we are trying to maximize the number of such resources.
This insight becomes apparent when you focus on the underlying structure and rules of the problem, rather than the specific contextual details.
Solution


The for loop iterates through the ‘forts’ list. If the current element is not zero, it checks whether the fort at the previous starting index ‘j’ is the negative of the current fort. If so, it calculates the distance between the two indices (subtracting one since the forts are 0indexed), and updates ‘res’ if this distance is greater than the current ‘res’. Finally, ‘j’ is updated to the current index ‘i’.
Q&A
We just need to find the maximum contiguous zeroes between 1 and 1 or between 1 and 1. We can use a variation of Kadane’s algorithm.
Yes, you’re correct! We can use a modified version of Kadane’s algorithm to solve this problem.
In the classical Kadane’s algorithm, we maintain a running sum and update the maximum sum whenever the running sum is greater than the current maximum. Here, we’re not adding numbers, but we’re counting zeros between 1 and 1 or between 1 and 1. The logic is somewhat similar.
In this case, we can have a pointer that goes through the list. Whenever it encounters a 1 or 1, it checks whether the last nonzero number was the opposite sign. If it was, it compares the count of zeros encountered to the current maximum. If the count is larger, it updates the maximum. Here is the translated Python code:


This version of Kadane’s algorithm iterates through the list only once, so the time complexity is O(n). The space complexity is O(1) since we’re only keeping track of a few variables.
We just need to find the maximum contiguous zeroes between 1 & 1 … or … 1 & 1.
Yes, that’s correct. The problem requires finding the maximum number of contiguous zeros that occur between positions marked by 1 and 1, or 1 and 1.
This observation is crucial because the problem setup states that the army can travel and capture forts only when moving from a fort under your command (marked as 1) to an empty fort (marked as 1), or vice versa. Therefore, we can only count zeros that are between these two positions.
The algorithm iterates over the input list, and each time it encounters a nonzero number (a fort under your command or an empty fort), it checks if the last nonzero number was of the opposite sign. If it was, it means we’ve found a segment of zeros that’s surrounded by 1 and 1, or 1 and 1. Then, it calculates the count of zeros in this segment and updates the maximum count if necessary.
Remember that the zeros count is calculated as the difference between the current nonzero position and the last nonzero position minus 1. This operation excludes the positions of the forts under your command or the empty forts from the zeros count. After checking and possibly updating the maximum zeros count, the algorithm updates the position of the last nonzero number.
By iterating through the entire list this way, the algorithm finds the maximum number of enemy forts that can be captured.