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

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

✓ Frequency Count

⏱️ Time: N/A Space: N/A

Brute Force - Check All Pairs

⏱️ Time: O(n³) Space: O(1)

For each pair of points, check if one can be Alice (upper-left) and other can be Bob (lower-right). Then verify no other people are inside or on the rectangle boundary.

Optimized with Early Pruning

⏱️ Time: O(n³) Space: O(1)

Sort points by x-coordinate, then for each Alice position, only check valid Bob candidates. Use the constraint that Alice must be upper-left and Bob lower-right to skip impossible combinations early.

Sort and Sweep

⏱️ Time: O(n³) Space: O(1)

Sort points by x-coordinate first, then for each potential Alice position, only consider Bob candidates to the right. Use coordinate constraints to eliminate impossible pairs early.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

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

typedef struct {
    int x, y;
} Point;

static Point points[1000];
static int pointCount = 0;

// Parse 2D array from string like "[[1,1],[2,2],[3,3]]"
void parsePoints(const char* str) {
    pointCount = 0;
    const char* p = str;
    
    // Skip to first '['
    while (*p && *p != '[') p++;
    if (*p) p++; // Skip first '['
    
    while (*p && *p != ']') {
        // Look for inner array start
        while (*p && *p != '[') p++;
        if (*p != '[') break;
        p++; // Skip '['
        
        // Parse x coordinate
        while (*p && (*p == ' ' || *p == ',')) p++;
        if (!*p || *p == ']') break;
        
        points[pointCount].x = (int)strtol(p, (char**)&p, 10);
        
        // Skip comma
        while (*p && *p != ',') p++;
        if (*p == ',') p++;
        
        // Parse y coordinate
        while (*p && *p == ' ') p++;
        points[pointCount].y = (int)strtol(p, (char**)&p, 10);
        
        pointCount++;
        
        // Skip to end of inner array
        while (*p && *p != ']') p++;
        if (*p == ']') p++;
        
        // Skip comma between arrays
        while (*p && (*p == ',' || *p == ' ')) p++;
    }
}

int numberOfPairs() {
    int count = 0;
    
    // Try all pairs (i, j) where i is Alice, j is Bob
    for (int i = 0; i < pointCount; i++) {
        for (int j = 0; j < pointCount; j++) {
            if (i == j) continue;
            
            int aliceX = points[i].x;
            int aliceY = points[i].y;
            int bobX = points[j].x;
            int bobY = points[j].y;
            
            // Alice must be upper-left, Bob must be lower-right
            // This means: Alice.x <= Bob.x AND Alice.y >= Bob.y
            if (aliceX > bobX || aliceY < bobY) continue;
            
            // Check if any other point is inside or on the rectangle
            int valid = 1;
            for (int k = 0; k < pointCount; k++) {
                if (k == i || k == j) continue;
                
                int x = points[k].x;
                int y = points[k].y;
                
                // Point is inside or on rectangle if:
                // aliceX <= x <= bobX AND bobY <= y <= aliceY
                if (x >= aliceX && x <= bobX && y >= bobY && y <= aliceY) {
                    valid = 0;
                    break;
                }
            }
            
            if (valid) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    
    if (fgets(line, sizeof(line), stdin) == NULL) {
        return 1;
    }
    
    // Remove newline
    line[strcspn(line, "\n")] = 0;
    
    parsePoints(line);
    
    int result = numberOfPairs();
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

⚠ Quadratic Growth

Space Complexity

✓ 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

Find the Number of Ways to Place People II - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Algorithm Steps — Algorithm Steps

Code -

Time & Space Complexity

Select Compiler