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-

numberOfPairs.js

/**
 * Counts the number of valid point pairs (i, j) such that:
 * - x[i] ≤ x[j]
 * - y[i] ≥ y[j]
 * - No other point between i and j has the same or higher y[j]
 *
 * @param {number[][]} points - Array of [x, y] coordinates
 * @return {number} - Number of valid pairs
 */
var numberOfPairs = function(points) {
    const n = points.length;
    if (n < 2) return 0;

    // Step 1: Coordinate compression for y-values
    // This helps reduce the range of y-values for efficient comparison
    const ys = [...new Set(points.map(p => p[1]))].sort((a, b) => a - b);
    const yMap = new Map(ys.map((y, i) => [y, i + 1])); // 1-based indexing

    // Step 2: Sort points by x ascending, then y descending
    // This ensures we process left-to-right in x, and prioritize higher y first
    const compressedPoints = points.map(([x, y]) => [x, yMap.get(y), y]);
    compressedPoints.sort((a, b) => a[0] - b[0] || b[2] - a[2]);

    let count = 0;

    // Step 3: Sweep through each point and count valid pairs
    for (let i = 0; i < n; i++) {
        const y1 = compressedPoints[i][1];
        let maxY = 0; // Tracks the highest y2 ≤ y1 seen so far

        for (let j = i + 1; j < n; j++) {
            const y2 = compressedPoints[j][1];

            // Skip if y2 is greater than y1 — violates the y[i] ≥ y[j] condition
            if (y2 > y1) continue;

            // If y2 is greater than any previously seen y2 in this range,
            // it's a valid pair (i, j)
            if (maxY < y2) {
                count++;
                maxY = y2;
            }
        }
    }

    return count;
};