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

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

✓ Optimized

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

Brute Force - Check All Pairs

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

For each pair of points, determine if one is upper-left of the other, then check if any other point lies within or on the boundary of their rectangle.

Optimized with Sorting

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

Sort points to process them in a more systematic order, allowing early termination and reducing unnecessary checks when looking for valid upper-left relationships.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

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

int solution(int points[][2], int n) {
    int count = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            
            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 parsePoints(const char* str, int points[][2]) {
    int n = 0;
    const char* p = str;
    
    // Skip to first [
    while (*p && *p != '[') p++;
    if (*p) p++; // skip [
    
    while (*p && *p != '\0') {
        // Find next [
        while (*p && *p != '[') p++;
        if (!*p || *p == '\0') break;
        p++; // skip [
        
        // Parse x
        char* endptr;
        int x = (int)strtol(p, &endptr, 10);
        p = endptr;
        
        // Skip comma
        while (*p && *p != ',') p++;
        if (*p) p++;
        
        // Parse y
        int y = (int)strtol(p, &endptr, 10);
        p = endptr;
        
        // Skip to ]
        while (*p && *p != ']') p++;
        if (*p) p++;
        
        points[n][0] = x;
        points[n][1] = y;
        n++;
        
        // Check if we reached the end
        while (*p && (*p == ',' || *p == ' ')) p++;
        if (*p == ']') break;
    }
    
    return n;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int points[1000][2];
    int n = parsePoints(line, points);
    
    int result = solution(points, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

⚠ Quadratic Growth

Space Complexity

✓ 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