Find the Number of Ways to Place People II

Find the Number of Ways to Place People II - Problem

Array Math Geometry Sorting Enumeration 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].

We define the right direction as positive x-axis (increasing x-coordinate) and the left direction as negative x-axis (decreasing x-coordinate). Similarly, we define the up direction as positive y-axis (increasing y-coordinate) and the down direction as negative y-axis (decreasing y-coordinate).

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 and Bob's position as the lower right corner of the fence.

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 on building the fence.

Note that Alice can only build a fence with Alice's position as the upper left corner, and Bob's position as the lower right corner.

Input & Output

Example 1 — Basic Case

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

› Output: 0

💡 Note: No valid Alice-Bob pairs exist. For any pair where Alice could be upper-left and Bob lower-right, the third point would always fall inside or on their rectangle boundary.

Example 2 — Valid Pairs

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

› Output: 2

💡 Note: Two valid pairs: Alice at (2,6) with Bob at (6,2) creates empty rectangle, and Alice at (2,6) with Bob at (4,4) also creates empty rectangle.

Example 3 — Edge Case

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

› Output: 1

💡 Note: Only Alice at (1,3) and Bob at (3,1) form a valid pair with no other people inside their rectangle.

Constraints

2 ≤ points.length ≤ 50
-50 ≤ points[i][0], points[i][1] ≤ 50
All points[i] are distinct

Visualization

Tap to expand

Understanding the Visualization

Input Points

Given coordinates on 2D plane

Form Rectangles

Alice upper-left, Bob lower-right

Count Empty

Rectangles with no other people inside

Key Takeaway

🎯 Key Insight: Count rectangles where Alice is upper-left, Bob is lower-right, and no other people are inside

Asked in

G Google 15 M Microsoft 12

The key insight is that Alice must be at upper-left corner and Bob at lower-right corner, so Alice.x ≤ Bob.x and Alice.y ≥ Bob.y. Best approach uses sorting to reduce pair checks, but still requires O(n³) time to verify no people inside rectangles. Time: O(n³), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Early Pruning	O(n³)	O(1)	Sort points and use geometric constraints to minimize rectangle checks
Brute Force - Check All Pairs	O(n³)	O(1)	Try every possible Alice-Bob pair and count people inside their rectangle
Sort and Sweep	O(n³)	O(1)	Sort points by x-coordinate and use sweep line to optimize rectangle checking

Optimized with Early Pruning — Algorithm Steps

Step 1: Sort points by x-coordinate for efficient scanning
Step 2: For Alice at position i, only consider Bob at j where points[j].x ≥ points[i].x
Step 3: Skip if points[i].y < points[j].y (Alice not upper-left)
Step 4: For valid Alice-Bob pairs, check rectangle contains no other points

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Points

Order by x-coordinate

Apply Constraints

Alice.y ≥ Bob.y for valid rectangles

Check Rectangle

Only for geometrically valid pairs

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int x, y, index;
} Point;

int comparePoints(const void *a, const void *b) {
    Point *pa = (Point*)a;
    Point *pb = (Point*)b;
    return pa->x - pb->x;
}

int solution(int points[][2], int n) {
    int count = 0;
    
    // Create indexed points for sorting
    Point indexedPoints[1000];
    for (int i = 0; i < n; i++) {
        indexedPoints[i].x = points[i][0];
        indexedPoints[i].y = points[i][1];
        indexedPoints[i].index = i;
    }
    qsort(indexedPoints, n, sizeof(Point), comparePoints);
    
    for (int i = 0; i < n; i++) {
        Point alice = indexedPoints[i];
        
        for (int j = i + 1; j < n; j++) {
            Point bob = indexedPoints[j];
            
            // Alice must be upper-left, Bob must be lower-right
            if (alice.y < bob.y) continue;
            
            // Check if any other person is inside or on the fence
            int valid = 1;
            for (int k = 0; k < n; k++) {
                if (k == i || k == j) continue;
                
                Point other = indexedPoints[k];
                // Check if point is inside or on rectangle boundary
                if (alice.x <= other.x && other.x <= bob.x && 
                    bob.y <= other.y && other.y <= alice.y) {
                    valid = 0;
                    break;
                }
            }
            
            if (valid) count++;
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int points[1000][2];
    int n = 0;
    
    char *ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            points[n][0] = strtol(ptr, &ptr, 10);
            ptr++;
            points[n][1] = strtol(ptr, &ptr, 10);
            n++;
            ptr++;
        }
        ptr++;
    }
    
    int result = solution(points, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n log n) sorting + O(n²) valid pairs × O(n) rectangle check in worst case

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses constant extra space for variables

✓ Linear Space

12.0K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized with Early Pruning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler