algoadvance

Leetcode 2511. Maximum Enemy Forts That Can Be Captured

Problem Statement

You are given a 0-indexed array forts of length n representing positions on a line, where:

• -1 represents an enemy fort,
• 0 represents an empty position,
• 1 represents your fort.

You want to capture enemy forts. You can only capture an enemy fort if you have your fort to the left and right side of the enemy fort and there are empty positions between your fort and the enemy fort.

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

Clarifying Questions

1. What should be returned if no enemy fort can be captured?
   • Return 0 if no enemy fort can be captured.
2. Are consecutive enemy forts allowed?
   • Yes, it is possible to have consecutive enemy forts. The task is to find valid forts that can be captured as per the described rules.
3. Can the array contain only one element or all elements of one type (-1, 0, or 1)?
   • Yes, but in such cases, the answer will be 0 since the conditions of having your fort on both sides cannot be met.

Strategy

1. Traversal: Traverse the array to locate positions with your fort (1).
2. Directional Search: Once a position with your fort is found, search to the right to find a pattern of [1, 0, …, 0, -1] or to the left to find a pattern of [-1, 0, …, 0, 1].
3. Count Empty Positions: During the search, count empty positions and if the search pattern matches, update the maximum count.
4. Update and Repeat: Continue this process for all positions with your fort.

Code

public class MaxEnemyFortsCaptured {
    public int captureForts(int[] forts) {
        int maxCaptured = 0, n = forts.length;

        for (int i = 0; i < n; i++) {
            if (forts[i] == 1) {
                // Search to the right
                int rightCount = 0;
                for (int j = i + 1; j < n; j++) {
                    if (forts[j] == 0) {
                        rightCount++;
                    } else if (forts[j] == -1) {
                        maxCaptured = Math.max(maxCaptured, rightCount);
                        break;
                    } else {
                        break;
                    }
                }

                // Search to the left
                int leftCount = 0;
                for (int j = i - 1; j >= 0; j--) {
                    if (forts[j] == 0) {
                        leftCount++;
                    } else if (forts[j] == -1) {
                        maxCaptured = Math.max(maxCaptured, leftCount);
                        break;
                    } else {
                        break;
                    }
                }
            }
        }

        return maxCaptured;
    }

    public static void main(String[] args) {
        MaxEnemyFortsCaptured solution = new MaxEnemyFortsCaptured();
        int[] forts = {1, 0, 0, -1, 0, 1, 0, -1, 0, 1};
        System.out.println(solution.captureForts(forts)); // Output should be the maximum number of enemy forts that can be captured
    }
}

Time Complexity

• Traversal of the Array: (O(n)), where (n) is the length of the forts array.
• Directional Search: For each fort 1, we search both left and right. Each search is (O(n)) in the worst case. Since we only do this for entries with your fort (1), it would typically be (O(n)) across the entire array.

In the worst-case scenario, both traversals together result in (O(n^2)).

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?