How hard is LeetCode 1274. Number of Ships in a Rectangle?

LeetCode 1274. Number of Ships in a Rectangle is rated Hard on LeetCode.

What is the time complexity of LeetCode 1274. Number of Ships in a Rectangle?

The Python solution on this page runs in O(C \times \log \max(m, n)).

What is the space complexity of LeetCode 1274. Number of Ships in a Rectangle?

The Python solution on this page uses O(\log \max(m, n)) auxiliary space.

What topics does LeetCode 1274. Number of Ships in a Rectangle cover?

LeetCode 1274. Number of Ships in a Rectangle is tagged Array, Divide and Conquer and Interactive on LeetCode.

Is LeetCode 1274. Number of Ships in a Rectangle a premium problem?

Yes. LeetCode 1274. Number of Ships in a Rectangle is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Number of Ships in a Rectangle — LeetCode 1274 Python Solution

HardLeetCode PremiumArrayDivide and ConquerInteractive

Problem: #1274
Reading time: 6 min
Source: leetcode.com

The problem

(This problem is an interactive problem.) Each ship is located at an integer point on the sea represented by a cartesian plane, and each integer point may contain at most 1 ship. You have a function Sea.hasShips(topRight, bottomLeft) which takes two points as arguments and returns true If there is at least one ship in the rectangle represented by the two points, including on the boundary.

Example

Input: ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3
Explanation: From [0,0] to [4,4] we can count 3 ships within the range.

Python solution

Python

# """
# This is Sea's API interface.
# You should not implement it, or speculate about its implementation
# """
# class Sea:
#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:
#
# class Point:
# 	def __init__(self, x: int, y: int):
# 		self.x = x
# 		self.y = y


class Solution:
    def countShips(self, sea: "Sea", topRight: "Point", bottomLeft: "Point") -> int:
        def dfs(topRight, bottomLeft):
            x1, y1 = bottomLeft.x, bottomLeft.y
            x2, y2 = topRight.x, topRight.y
            if x1 > x2 or y1 > y2:
                return 0
            if not sea.hasShips(topRight, bottomLeft):
                return 0
            if x1 == x2 and y1 == y2:
                return 1
            midx = (x1 + x2) >> 1
            midy = (y1 + y2) >> 1
            a = dfs(topRight, Point(midx + 1, midy + 1))
            b = dfs(Point(midx, y2), Point(x1, midy + 1))
            c = dfs(Point(midx, midy), bottomLeft)
            d = dfs(Point(x2, midy), Point(midx + 1, y1))
            return a + b + c + d

        return dfs(topRight, bottomLeft)

Complexity

Measure	Complexity
Time	O(C \times \log \max(m, n))
Space	O(\log \max(m, n)) auxiliary

Frequently asked questions

How hard is LeetCode 1274. Number of Ships in a Rectangle?: LeetCode 1274. Number of Ships in a Rectangle is rated Hard on LeetCode.
What is the time complexity of LeetCode 1274. Number of Ships in a Rectangle?: The Python solution on this page runs in O(C \times \log \max(m, n)).
What is the space complexity of LeetCode 1274. Number of Ships in a Rectangle?: The Python solution on this page uses O(\log \max(m, n)) auxiliary space.
What topics does LeetCode 1274. Number of Ships in a Rectangle cover?: LeetCode 1274. Number of Ships in a Rectangle is tagged Array, Divide and Conquer and Interactive on LeetCode.
Is LeetCode 1274. Number of Ships in a Rectangle a premium problem?: Yes. LeetCode 1274. Number of Ships in a Rectangle is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.