LeetCode 3025 - Find the Number of Ways to Place People I

The problem gives us a list of distinct points on a 2D plane. Each point is represented as [x, y], where x is the horizontal coordinate and y is the vertical coordinate. We must count how many ordered pairs (A, B) satisfy two conditions: 1.

leetcodemediumarraymathgeometrysortingenumeration

LeetCode Problem 3025

Difficulty: 🟡 Medium
Topics: Array, Math, Geometry, Sorting, Enumeration

Solution

Problem Understanding

The problem gives us a list of distinct points on a 2D plane. Each point is represented as [x, y], where x is the horizontal coordinate and y is the vertical coordinate.

We must count how many ordered pairs (A, B) satisfy two conditions:

  1. Point A is on the upper-left side of point B
  2. The rectangle formed by A and B, including its border, contains no other points except A and B

To understand the geometry precisely, suppose:

  • A = (x1, y1)
  • B = (x2, y2)

For A to be on the upper-left side of B:

  • x1 <= x2
  • y1 >= y2

This means A lies leftward and upward relative to B.

The rectangle formed by these two points includes all coordinates:

  • x1 <= x <= x2
  • y2 <= y <= y1

The pair is valid only if no third point lies anywhere inside or on the boundary of this rectangle.

An important detail is that degenerate rectangles are allowed. If the two points lie on the same horizontal or vertical line, the "rectangle" becomes a line segment, and the same emptiness rule still applies.

The constraints are very small:

  • 2 <= n <= 50
  • Coordinates are between 0 and 50
  • All points are distinct

Because n is at most 50, even cubic solutions are acceptable. This strongly influences the algorithm choice. We do not need advanced geometry structures or sweep-line optimizations.

Several edge cases are important:

  • Multiple points may lie on the same vertical or horizontal line
  • A point exactly on the rectangle border invalidates the pair
  • Degenerate rectangles still count as valid regions that must be empty
  • Since pairs are ordered, (A, B) and (B, A) are different geometrically, but only one direction can satisfy the upper-left condition

Approaches

Brute Force Approach

The most direct solution is to examine every ordered pair of points (A, B).

For each pair:

  1. Check whether A is upper-left of B
  2. If it is, scan all other points
  3. Determine whether any point lies inside or on the boundary of the rectangle formed by A and B
  4. If no such point exists, increment the answer

This works because the constraints are small enough to allow checking every possible rectangle explicitly.

Suppose there are n points:

  • There are O(n²) candidate pairs
  • For each pair, we may scan all n points

This produces an O(n³) solution.

Even though cubic time is usually large, here n <= 50, so:

  • 50³ = 125,000

which is completely manageable.

Key Insight for the Better Solution

The main observation is that the constraints are intentionally small. There is no need for complicated data structures or spatial indexing.

However, we can still organize the logic cleanly by:

  1. Iterating through all candidate pairs
  2. Immediately rejecting invalid geometric orientations
  3. Using simple rectangle boundary checks for obstruction detection

The "optimal" solution for this problem is still O(n³), but it is carefully structured and efficient enough for the given limits.

The important improvement is conceptual clarity rather than asymptotic reduction. We minimize unnecessary work by only checking rectangles for geometrically valid pairs.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Checks every pair and scans all points
Optimal O(n³) O(1) Same asymptotic complexity, but cleaner geometric filtering and efficient validation

Algorithm Walkthrough

Step 1: Iterate Through Every Ordered Pair

We consider every ordered pair of points (A, B).

For each pair:

  • A = (x1, y1)
  • B = (x2, y2)

We skip pairs where A and B are the same point.

This guarantees that every possible candidate relationship is examined.

Step 2: Check the Upper-Left Condition

A valid pair must satisfy:

  • x1 <= x2
  • y1 >= y2

If either condition fails, then A is not positioned upper-left relative to B, so the pair cannot contribute to the answer.

This immediately prunes many invalid pairs.

Step 3: Define the Rectangle Boundaries

For a valid geometric pair, the rectangle boundaries are:

  • Left boundary: x1
  • Right boundary: x2
  • Bottom boundary: y2
  • Top boundary: y1

Every point inside or on the border of this rectangle must be checked.

Step 4: Scan All Other Points

We iterate through all points again.

For each third point (x, y):

  • Ignore A
  • Ignore B

Then check whether:

  • x1 <= x <= x2
  • y2 <= y <= y1

If both are true, the point lies inside or on the border of the rectangle.

In that case, the pair is invalid.

Step 5: Count Valid Pairs

If the scan finishes without finding any blocking point, then the rectangle is empty except for A and B.

We increment the answer.

Step 6: Return the Final Count

After examining all ordered pairs, return the total number of valid pairs.

Why it works

The algorithm directly implements the exact problem definition.

For every ordered pair, it verifies:

  1. The required geometric orientation
  2. The absence of all other points within the rectangle boundary

Since every candidate pair is checked exhaustively and every obstructing point is tested explicitly, no valid pair is missed and no invalid pair is counted.

Python Solution

from typing import List

class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        n = len(points)
        answer = 0

        for i in range(n):
            x1, y1 = points[i]

            for j in range(n):
                if i == j:
                    continue

                x2, y2 = points[j]

                # A must be upper-left of B
                if x1 > x2 or y1 < y2:
                    continue

                valid = True

                for k in range(n):
                    if k == i or k == j:
                        continue

                    x, y = points[k]

                    # Point lies inside or on border
                    if x1 <= x <= x2 and y2 <= y <= y1:
                        valid = False
                        break

                if valid:
                    answer += 1

        return answer

The implementation follows the algorithm exactly.

The outer two loops enumerate every ordered pair of points. For each pair, the code first checks whether the geometric upper-left condition is satisfied. If not, the pair is skipped immediately.

Once a geometrically valid pair is found, the third loop scans all remaining points. The rectangle inclusion test:

x1 <= x <= x2 and y2 <= y <= y1

determines whether a point lies inside or on the rectangle boundary.

If any such point exists, the pair becomes invalid. Otherwise, the pair contributes to the answer.

Because the constraints are small, this direct geometric implementation is both simple and efficient.

Go Solution

func numberOfPairs(points [][]int) int {
	n := len(points)
	answer := 0

	for i := 0; i < n; i++ {
		x1, y1 := points[i][0], points[i][1]

		for j := 0; j < n; j++ {
			if i == j {
				continue
			}

			x2, y2 := points[j][0], points[j][1]

			// A must be upper-left of B
			if x1 > x2 || y1 < y2 {
				continue
			}

			valid := true

			for k := 0; k < n; k++ {
				if k == i || k == j {
					continue
				}

				x, y := points[k][0], points[k][1]

				// Point lies inside or on border
				if x1 <= x && x <= x2 &&
					y2 <= y && y <= y1 {
					valid = false
					break
				}
			}

			if valid {
				answer++
			}
		}
	}

	return answer
}

The Go implementation mirrors the Python logic closely.

Since coordinate values are tiny, standard int arithmetic is fully safe and there is no overflow concern.

Go slices are used naturally for the input points. No additional memory allocation is required beyond a few local variables, so the solution remains constant-space.

Worked Examples

Example 1

Input:

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

Candidate Pairs

A B Upper-left valid?
(1,1) (2,2) No
(1,1) (3,3) No
(2,2) (1,1) No
(2,2) (3,3) No
(3,3) (1,1) No
(3,3) (2,2) No

No pair satisfies:

  • x1 <= x2
  • y1 >= y2

Therefore:

Answer = 0

Example 2

Input:

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

Label the points:

Index Point
0 (6,2)
1 (4,4)
2 (2,6)

Pair: (4,4) → (6,2)

Rectangle:

  • 4 <= x <= 6
  • 2 <= y <= 4

Check third point (2,6):

  • x = 2 is outside

No obstruction exists.

Valid pair count becomes 1.

Pair: (2,6) → (4,4)

Rectangle:

  • 2 <= x <= 4
  • 4 <= y <= 6

Check third point (6,2):

  • Outside rectangle

Valid pair count becomes 2.

Pair: (2,6) → (6,2)

Rectangle:

  • 2 <= x <= 6
  • 2 <= y <= 6

Point (4,4) lies inside.

This pair is invalid.

Final answer:

2

Example 3

Input:

points = [[3,1],[1,3],[1,1]]

Label the points:

Index Point
0 (3,1)
1 (1,3)
2 (1,1)

Pair: (1,1) → (3,1)

Rectangle becomes a horizontal line:

  • 1 <= x <= 3
  • y = 1

No other point lies on this segment.

Valid.

Pair: (1,3) → (1,1)

Rectangle becomes a vertical line:

  • x = 1
  • 1 <= y <= 3

No other point lies on this segment.

Valid.

Pair: (1,3) → (3,1)

Rectangle:

  • 1 <= x <= 3
  • 1 <= y <= 3

Point (1,1) lies on the border.

Invalid.

Final answer:

2

Complexity Analysis

Measure Complexity Explanation
Time O(n³) Three nested loops over all points
Space O(1) Only a few variables are used

The algorithm examines every ordered pair of points, which requires O(n²) work. For each pair, it scans all points again to detect obstructions, adding another factor of n.

Because no auxiliary data structures proportional to input size are used, the extra space complexity remains constant.

Test Cases

from typing import List

class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        n = len(points)
        answer = 0

        for i in range(n):
            x1, y1 = points[i]

            for j in range(n):
                if i == j:
                    continue

                x2, y2 = points[j]

                if x1 > x2 or y1 < y2:
                    continue

                valid = True

                for k in range(n):
                    if k == i or k == j:
                        continue

                    x, y = points[k]

                    if x1 <= x <= x2 and y2 <= y <= y1:
                        valid = False
                        break

                if valid:
                    answer += 1

        return answer

sol = Solution()

assert sol.numberOfPairs([[1,1],[2,2],[3,3]]) == 0  # strictly increasing diagonal
assert sol.numberOfPairs([[6,2],[4,4],[2,6]]) == 2  # example with blocking point
assert sol.numberOfPairs([[3,1],[1,3],[1,1]]) == 2  # border and line cases

assert sol.numberOfPairs([[1,5],[5,1]]) == 1  # simple valid rectangle
assert sol.numberOfPairs([[1,5],[3,3],[5,1]]) == 0  # middle point blocks

assert sol.numberOfPairs([[1,1],[1,2]]) == 0  # vertical but wrong orientation
assert sol.numberOfPairs([[1,2],[1,1]]) == 1  # vertical valid line

assert sol.numberOfPairs([[1,1],[2,1]]) == 1  # horizontal valid line
assert sol.numberOfPairs([[1,1],[2,1],[3,1]]) == 2  # multiple horizontal segments

assert sol.numberOfPairs([[0,50],[50,0]]) == 1  # extreme coordinate values

assert sol.numberOfPairs([[1,4],[2,3],[3,2],[4,1]]) == 3  # chained valid pairs

assert sol.numberOfPairs([[1,5],[2,4],[3,3],[4,2],[5,1]]) == 4  # nested blocking rectangles

Test Summary

Test Why
[[1,1],[2,2],[3,3]] No upper-left relationships exist
[[6,2],[4,4],[2,6]] Interior blocking point
[[3,1],[1,3],[1,1]] Border points invalidate rectangles
[[1,5],[5,1]] Simplest valid rectangle
[[1,5],[3,3],[5,1]] Point inside rectangle invalidates pair
[[1,1],[1,2]] Wrong vertical orientation
[[1,2],[1,1]] Degenerate vertical line
[[1,1],[2,1]] Degenerate horizontal line
[[1,1],[2,1],[3,1]] Multiple line-segment checks
[[0,50],[50,0]] Coordinate extremes
[[1,4],[2,3],[3,2],[4,1]] Multiple independent valid pairs
[[1,5],[2,4],[3,3],[4,2],[5,1]] Nested rectangles and blockers

Edge Cases

One important edge case is when two points form a line rather than a proper rectangle. This happens when the points share the same x coordinate or the same y coordinate. A naive implementation might accidentally ignore these cases because the rectangle has zero width or zero height. However, the problem explicitly allows these degenerate rectangles. The implementation handles this correctly because the boundary checks use inclusive inequalities, so line segments are treated naturally.

Another critical edge case occurs when a third point lies exactly on the border of the rectangle. Many geometry problems distinguish between interior and boundary points, but this problem explicitly states that the border also counts. A pair becomes invalid even if another point touches the rectangle edge. The implementation correctly handles this using inclusive comparisons:

x1 <= x <= x2 and y2 <= y <= y1

This ensures border points invalidate the pair.

A third important case is when multiple points appear in descending diagonal order, such as:

[(1,5), (2,4), (3,3), (4,2)]

Many pairs satisfy the upper-left condition geometrically, but larger rectangles contain intermediate points. A naive solution might count all geometric pairs without verifying emptiness carefully. The implementation avoids this bug by scanning every third point before accepting a pair.

Finally, it is important that points are distinct. The problem guarantees uniqueness, which simplifies the implementation because we never need to handle duplicate coordinates or distinguish between multiple identical points.