#3025

Medium

LeetCode Problem Workspace

Find the Number of Ways to Place People I

Calculate how many valid pairs of points can be formed on a 2D plane using array and math enumeration techniques efficiently.

array math geometry sorting enumeration

Problem Statement

Given a 2D array points of size n x 2 representing integer coordinates on a 2D plane, count the number of pairs of points (A, B) where point A is strictly above and to the left of point B.

Return the total number of such valid pairs. Each point is unique, and coordinates are integers within the given constraints.

Examples

Example 1

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

Output: 0

There is no way to choose A and B so A is on the upper left side of B .

Example 2

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

Output: 2

Example 3

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

Output: 2

Constraints

2 <= n <= 50
points[i].length == 2
0 <= points[i][0], points[i][1] <= 50
All points[i] are distinct.

Solution Approach

Enumerate Upper-Left Points

Sort the points or iterate through each point as a potential upper-left corner A. For each A, check all other points to see if they can serve as lower-right point B.

Count Valid Lower-Right Points

For each candidate A, count points B that satisfy B.x > A.x and B.y < A.y. Use simple iteration or array filtering to accumulate the total count.

Aggregate Results Efficiently

Sum all valid pairs found for each upper-left point. Optional optimizations include pre-sorting by x and y to reduce comparisons, exploiting the small n <= 50 constraint.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) in the worst case due to double iteration over points, but acceptable for n <= 50. Space complexity is O(1) extra beyond input storage, unless using auxiliary arrays for sorting or counting.

What Interviewers Usually Probe

Pay attention to correct inequality directions for upper-left vs lower-right pairs.
Consider how small constraints allow brute-force enumeration without performance penalty.
Sorting points by x or y may simplify counting but is optional for correctness.

Common Pitfalls or Variants

Common pitfalls

Confusing upper-left with lower-left or upper-right positions when comparing coordinates.
Counting the same pair twice due to symmetric iteration over points.
Ignoring the strict inequality requirement in either x or y coordinates.

Follow-up variants

Count pairs with relaxed inequality, allowing A.x <= B.x and A.y >= B.y.
Find all triples of points forming a specific geometric shape using similar enumeration.
Extend to 3D coordinates, counting pairs where one point is strictly less in x and y but greater in z.

FAQ

What is the easiest approach to Find the Number of Ways to Place People I?

Iterate each point as an upper-left candidate and count all valid lower-right points using array filtering and inequality checks.

Can this problem be solved without sorting?

Yes, brute-force iteration works for n <= 50, but sorting can simplify comparisons and reduce mental errors.

What array plus math patterns are used here?

The key pattern is enumerating positions and applying coordinate inequalities to count valid geometric relationships.

How do I avoid counting duplicate pairs?

Ensure you always treat the first selected point as the upper-left and the second as lower-right, respecting strict inequalities.

Is there a faster approach for large n?

For larger n, segment trees or coordinate compression could reduce counting time, but for n <= 50, direct enumeration is efficient.

terminal

Solution

Solution 1: Sorting and Classification

First, we sort the array. Then, we can classify the results based on the properties of a triangle.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x: (x[0], -x[1]))
        ans = 0
        for i, (_, y1) in enumerate(points):
            max_y = -inf
            for _, y2 in points[i + 1 :]:
                if max_y < y2 <= y1:
                    max_y = y2
                    ans += 1
        return ans

Continue Practicing

#3027 find the number of ways to place people ii #3380 maximum area rectangle with point constraints i #3102 minimize manhattan distances