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 poin

numberOfPairs.js

/**
 * @param {number[][]} points
 * @return {number}
 */
var numberOfPairs = function(points) {
    let count = 0;

    // Step 1: Sort points by x ascending, then y descending
    // This ensures that for any point[i], all point[j] with j < i have x <= x[i]
    points.sort((a, b) => {
        if (a[0] === b[0]) return b[1] - a[1]; // If x is equal, sort by y descending
        return a[0] - b[0]; // Otherwise, sort by x ascending
    });

    // Step 2: Iterate through each point[i] as potential lower-right corner
    for (let i = 1; i < points.length; i++) {
        const [curX, curY] = points[i];
        let maxY = Infinity; // Tracks the highest y we've accepted so far

        // Step 3: Check all previous points[j] as potential upper-left corners
        for (let j = i - 1; j >= 0; j--) {
            const [preX, preY] = points[j];

            // Check if point[j] is upper-left of point[i]
            if (preX <= curX && preY >= curY) {
                // Only count if it's not blocked by a previously counted point
                if (preY < maxY) {
                    count++;
                    maxY = preY; // Update maxY to prevent overlapping rectangles
                }
            }
        }
    }

    return count;
};