LeetCode 1274: Number of Ships in a Rectangle

Explanation:

This problem can be solved using a divide and conquer approach along with binary search. The idea is to recursively divide the given rectangle into smaller sub-rectangles until the rectangle contains only one ship or no ships at all. At each step, we check if the current rectangle contains any ships. If a ship is found in a rectangle, we split the rectangle into four smaller rectangles and continue the search in each smaller rectangle until we reach a single point. This approach helps in reducing the search space efficiently.

Steps:

1. Define a recursive function that takes the top-left and bottom-right coordinates of the current rectangle, along with a list of ships within the rectangle.
2. Check if there are any ships within the current rectangle. If not, return 0.
3. If there are ships, check if the rectangle contains only one ship. If so, return 1.
4. Otherwise, split the rectangle into four smaller rectangles and recursively search for ships in each smaller rectangle.
5. Repeat the above steps until we reach a single point or no ships are found.

Time Complexity:

The time complexity of this approach is O(N log N), where N is the number of ships in the given rectangle. The divide and conquer approach helps in efficiently reducing the search space.

Space Complexity:

The space complexity of this approach is O(log N) for the recursive call stack.: :

class Solution {
    public int countShips(Sea sea, int[] topRight, int[] bottomLeft) {
        return countShipsHelper(sea, topRight, bottomLeft);
    }
    
    private int countShipsHelper(Sea sea, int[] topRight, int[] bottomLeft) {
        if (!sea.hasShips(topRight, bottomLeft)) {
            return 0;
        }
        
        if (topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1]) {
            return 1;
        }
        
        int midX = (topRight[0] + bottomLeft[0]) / 2;
        int midY = (topRight[1] + bottomLeft[1]) / 2;
        
        return countShipsHelper(sea, new int[]{midX, midY}, bottomLeft) +
               countShipsHelper(sea, new int[]{topRight[0], midY}, new int[]{midX + 1, bottomLeft[1]}) +
               countShipsHelper(sea, topRight, new int[]{midX + 1, midY + 1}) +
               countShipsHelper(sea, new int[]{midX, topRight[1]}, new int[]{bottomLeft[0], midY + 1});
    }
}