🧩 Find the Number of Ways to Place People II

Problem #3027 | Difficulty: 🔴 Hard

---

📝 Problem Description

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].

🧭 Direction Definition

• Right direction: positive x-axis (increasing x-coordinate)
• Left direction: negative x-axis (decreasing x-coordinate)
• Up direction: positive y-axis (increasing y-coordinate)
• Down direction: negative y-axis (decreasing y-coordinate)

🎯 Problem Statement

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:

• Alice's position as the upper left corner
• Bob's position as the lower right corner

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.

---

💡 Examples

Example 1

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.

Example 2

Input: points = [[6,2],[4,4],[2,6]]

Output: 2

Explanation: There are two valid ways to place Alice and Bob:

• 🟢 Alice at (4, 4) and Bob at (6, 2)
• 🟢 Alice at (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.

Example 3

Input: points = [[3,1],[1,3],[1,1]]

Output: 2

Explanation: Two valid placements:

• 🟢 Alice at (1, 1) and Bob at (3, 1)
• 🟢 Alice at (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!

---

🔒 Constraints

• 2 <= n <= 1000
• points[i].length == 2
• -10^9 <= points[i][0], points[i][1] <= 10^9
• All points are distinct

---

⚠️ Important Notes

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:

• With Alice at (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
• With Alice at (1, 3) and Bob at (1, 1): Bob's position is not the lower right corner of the fence

---

🎨 Key Insights

1. Alice must be at the upper-left corner
2. Bob must be at the lower-right corner
3. No other person should be inside or on the fence boundary
4. For Alice to be upper-left and Bob to be lower-right:
   • Alice's x-coordinate ≤ Bob's x-coordinate
   • Alice's y-coordinate ≥ Bob's y-coordinate

---

💭 Approach Strategy

For each pair of points (Alice, Bob):

1. Check if Alice can be upper-left and Bob can be lower-right
2. Verify no other points fall within or on the fence boundary
3. Count all valid pairs

Topics: Array Math Enumeration Geometry

— Written by Saurabh Patil • B.Tech CSE • Software Developer