Find the Number of Ways to Place People I

Find the Number of Ways to Place People I - Problem

Array Math Geometry Sorting Enumeration Medium

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), except for the points A and B.

Return the count.

Input & Output

Example 1 — Basic Rectangle

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

› Output: 0

💡 Note: No valid pairs exist. For each pair, either one point is not upper-left of the other, or there are points on the boundary of their rectangle.

Example 2 — Valid Pair

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

› Output: 2

💡 Note: Point (2,6) is upper-left of (4,4) and (6,2). Point (4,4) is upper-left of (6,2). All rectangles are empty, so we have 2 valid pairs.

Example 3 — Blocked Rectangle

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

› Output: 1

💡 Note: Only (1,1) is upper-left of (2,0) with an empty rectangle between them.

Constraints

2 ≤ points.length ≤ 50
points[i].length == 2
0 ≤ x_i, y_i ≤ 50
All the given points are unique

Visualization

Tap to expand

Understanding the Visualization

Input Points

Given points on 2D plane: [[6,2],[4,4],[2,6]]

Find Upper-Left Relations

Check which points can be upper-left of others

Verify Empty Rectangles

Count pairs with no points inside their rectangle

Key Takeaway

🎯 Key Insight: A point A is upper-left of B when A.x ≤ B.x and A.y ≥ B.y, with empty rectangle between them

Asked in

G Google 15 M Microsoft 8

The key insight is that point A is upper-left of B when A.x ≤ B.x and A.y ≥ B.y, and their rectangle must be empty. Best approach checks all pairs systematically in O(n³) time. Time: O(n³), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Sorting	O(n³)	O(1)	Sort points by x-coordinate, then by y-coordinate to reduce comparisons
Brute Force - Check All Pairs	O(n³)	O(1)	Check every pair of points and verify no other points lie in their rectangle

Optimized with Sorting — Algorithm Steps

Step 1: Sort points by x-coordinate, then by y-coordinate descending
Step 2: For each point as potential upper-left, check points that could be lower-right
Step 3: For valid pairs, verify no other points lie in their rectangle
Step 4: Use sorting to optimize the rectangle checking process

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Points

Sort by x-coordinate, then y-coordinate descending

Systematic Check

Process pairs in order, avoiding duplicate checks

Rectangle Validation

Verify no points lie within valid pair rectangles

Code -

solution.c — C

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

int compare(const void *a, const void *b) {
    int *pointA = (int *)a;
    int *pointB = (int *)b;
    if (pointA[0] == pointB[0]) {
        return pointB[1] - pointA[1]; // y descending
    }
    return pointA[0] - pointB[0]; // x ascending
}

int solution(int points[][2], int n) {
    int count = 0;
    
    // Sort points by x-coordinate, then by y-coordinate descending
    qsort(points, n, sizeof(int[2]), compare);
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int x1 = points[i][0], y1 = points[i][1];
            int x2 = points[j][0], y2 = points[j][1];
            
            // Check if point i is upper-left of point j
            if (x1 <= x2 && y1 >= y2) {
                // Check if any other point lies in the rectangle
                int valid = 1;
                for (int k = 0; k < n; k++) {
                    if (k == i || k == j) continue;
                    
                    int x3 = points[k][0], y3 = points[k][1];
                    // Point k is in rectangle if x1 <= x3 <= x2 and y2 <= y3 <= y1
                    if (x1 <= x3 && x3 <= x2 && y2 <= y3 && y3 <= y1) {
                        valid = 0;
                        break;
                    }
                }
                
                if (valid) {
                    count++;
                }
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [[x1,y1],[x2,y2],...]
    int points[1000][2];
    int n = 0;
    char *ptr = line + 1; // Skip first '['
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            points[n][0] = strtol(ptr, &ptr, 10);
            ptr++; // Skip comma
            points[n][1] = strtol(ptr, &ptr, 10);
            n++;
            ptr++; // Skip ']'
        }
        ptr++;
    }
    
    int result = solution(points, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Sorting is O(n log n), but main checking is still O(n³) with three nested operations

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for variables, sorting can be done in-place

✓ Linear Space

8.5K Views

Medium Frequency

~25 min Avg. Time

234 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 Sorting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler