Problem #3027 | Difficulty: 🔴 Hard
You are given a 2D array points
of size n x 2
representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi]
.
You have to place n
people, including Alice and Bob, at these points such that there is exactly one person at every point.
Alice wants to be alone with Bob, so Alice will build a rectangular fence with:
Note: The fence might not enclose any area (it can be a line)
If any person other than Alice and Bob is either inside the fence or on the fence, Alice will be sad. 😢
Return the number of pairs of points where you can place Alice and Bob such that Alice does not become sad.
Input: points = [[1,1],[2,2],[3,3]]
Output: 0
Explanation: There is no way to place Alice and Bob such that Alice can build a fence with Alice's position as the upper left corner and Bob's position as the lower right corner.
Input: points = [[6,2],[4,4],[2,6]]
Output: 2
Explanation: There are two valid ways to place Alice and Bob:
(4, 4)
and Bob at (6, 2)
(2, 6)
and Bob at (4, 4)
❌ Invalid: Alice at (2, 6)
and Bob at (6, 2)
because the person at (4, 4)
will be inside the fence.
Input: points = [[3,1],[1,3],[1,1]]
Output: 2
Explanation: Two valid placements:
(1, 1)
and Bob at (3, 1)
(1, 3)
and Bob at (1, 1)
❌ Invalid: Alice at (1, 3)
and Bob at (3, 1)
because the person at (1, 1)
will be on the fence.
💡 Note: It doesn't matter if the fence encloses any area - the fence can be a line!
2 <= n <= 1000
points[i].length == 2
-10^9 <= points[i][0], points[i][1] <= 10^9
Alice can only build a fence with Alice's position as the upper left corner, and Bob's position as the lower right corner.
For example, Alice cannot build either of the fences with four corners (1, 1)
, (1, 3)
, (3, 1)
, and (3, 3)
, because:
(3, 3)
and Bob at (1, 1)
: Alice's position is not the upper left corner and Bob's position is not the lower right corner(1, 3)
and Bob at (1, 1)
: Bob's position is not the lower right corner of the fenceFor each pair of points (Alice, Bob)
:
Topics: Array
Math
Enumeration
Geometry
https://drawtocode.vercel.app/problems/find-the-number-of-ways-to-place-people-2
Loading component...
Loading component...