HardNo. 1274LeetCode Premium
Number of Ships in a Rectangle — LeetCode 1274 Python Solution
- Topics
- Array, Divide and Conquer, Interactive
- 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
# """
# 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
- Time
- O(C × log max(m, n))
- Space · auxiliary
- O(log max(m, n))
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1982 | Find Array Given Subset Sums | Hard |
| 0057 | Insert Interval | Medium |
| 0228 | Summary Ranges | Easy |
| 0485 | Max Consecutive Ones | Easy |
| 0665 | Non-decreasing Array | Medium |
| 0674 | Longest Continuous Increasing Subsequence | Easy |
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 × 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.