Scale Engineer

Find the Number of Ways to Place People I

Med
#2693Time: O(n^3), where `n` is the number of points. There are two nested loops to select a pair of points `(A, B)`, and a third nested loop to check for any interfering point `C`. This results in a cubic number of operations.Space: O(1) extra space. The algorithm only requires a few variables for loop counters and the result, not dependent on the input size.
Patterns
MathGeometryEnumeration
Algorithms
Sorting
Data structures
Array

Prompt

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

Count the number of pairs of points (A, B), where

  • A is on the upper left side of B, and
  • there are no other points in the rectangle (or line) they make (including the border).

Return the count.

 

Example 1:

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

Output: 0

Explanation:

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

Explanation:

  • The left one is the pair (points[1], points[0]), where points[1] is on the upper left side of points[0] and the rectangle is empty.
  • The middle one is the pair (points[2], points[1]), same as the left one it is a valid pair.
  • The right one is the pair (points[2], points[0]), where points[2] is on the upper left side of points[0], but points[1] is inside the rectangle so it's not a valid pair.

Example 3:

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

Output: 2

Explanation:

  • The left one is the pair (points[2], points[0]), where points[2] is on the upper left side of points[0] and there are no other points on the line they form. Note that it is a valid state when the two points form a line.
  • The middle one is the pair (points[1], points[2]), it is a valid pair same as the left one.
  • The right one is the pair (points[1], points[0]), it is not a valid pair as points[2] is on the border of the rectangle.

 

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code. It iterates through all possible pairs of points (A, B) and for each pair, it first checks if A is to the upper-left of B. If this condition is met, it then performs another iteration through all other points (C) to check if any of them lie inside the rectangle formed by A and B. If no such point C is found, the pair (A, B) is counted.

Algorithm

  • Initialize a counter count to 0.
  • Iterate through each point A in the points array using an index i.
  • In a nested loop, iterate through each point B in the points array using an index j.
  • If i and j are the same, skip to the next iteration to avoid comparing a point with itself.
  • Check if point A is on the upper-left side of point B. This condition is points[i][0] <= points[j][0] and points[i][1] >= points[j][1].
  • If the upper-left condition is met, we must check if the rectangle they form is empty. Initialize a boolean flag is_empty to true.
  • Start a third nested loop, iterating through every point C with index k.
  • If k is the same as i or j, skip.
  • Check if point C lies inside or on the boundary of the rectangle formed by A and B. The condition is points[k][0] >= points[i][0], points[k][0] <= points[j][0], points[k][1] >= points[j][1], and points[k][1] <= points[i][1].
  • If such a point C is found, set is_empty to false and break the innermost loop.
  • After checking all points C, if is_empty is still true, it means we found a valid pair. Increment count.
  • After all loops complete, return the final count.

Walkthrough

The brute-force algorithm systematically checks every possible ordered pair of points (A, B). For each pair, it first validates the geometric condition: A.x <= B.x and A.y >= B.y. If this condition holds, the algorithm proceeds to check for the 'empty rectangle' constraint. It does this by iterating through every other point C in the list and checking if C lies inside or on the boundary of the rectangle defined by A and B. A point C is inside if A.x <= C.x <= B.x and B.y <= C.y <= A.y. If any such point C is found, the rectangle is not empty, and the pair (A, B) is invalid. If the loop over all points C completes without finding any interfering point, the pair (A, B) is valid, and a counter is incremented. This process is repeated for all pairs to find the total count.

class Solution {    public int numberOfPairs(int[][] points) {        int n = points.length;        int count = 0;        for (int i = 0; i < n; i++) { // Point A            for (int j = 0; j < n; j++) { // Point B                if (i == j) continue;                 int x1 = points[i][0];                int y1 = points[i][1];                int x2 = points[j][0];                int y2 = points[j][1];                 // Check if A is upper-left of B                if (x1 <= x2 && y1 >= y2) {                    boolean isRectangleEmpty = true;                    // Check for any other point C inside the rectangle                    for (int k = 0; k < n; k++) {                        if (k == i || k == j) continue;                         int x3 = points[k][0];                        int y3 = points[k][1];                         if (x3 >= x1 && x3 <= x2 && y3 >= y2 && y3 <= y1) {                            isRectangleEmpty = false;                            break;                        }                    }                    if (isRectangleEmpty) {                        count++;                    }                }            }        }        return count;    }}

Complexity

Time

O(n^3), where `n` is the number of points. There are two nested loops to select a pair of points `(A, B)`, and a third nested loop to check for any interfering point `C`. This results in a cubic number of operations.

Space

O(1) extra space. The algorithm only requires a few variables for loop counters and the result, not dependent on the input size.

Trade-offs

Pros

  • It is straightforward to understand and implement as it directly follows the problem's definition.

  • It is guaranteed to be correct and works well for the given small constraints (n <= 50).

Cons

  • The O(n^3) time complexity makes it inefficient and potentially too slow if the constraints on n were larger.

Solutions

public class Solution {    public int NumberOfPairs(int[][] points) {        Array.Sort(points, (a, b) => a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);        int ans = 0;        int n = points.Length;        int inf = 1 << 30;        for (int i = 0; i < n; ++i) {            int y1 = points[i][1];            int maxY = -inf;            for (int j = i + 1; j < n; ++j) {                int y2 = points[j][1];                if (maxY < y2 && y2 <= y1) {                    maxY = y2;                    ++ans;                }            }        }        return ans;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem