3025: Find-the-Number-of-Ways-to-Place-People-I
Medium

A key observation to note is that, if we choose any point as the bottom-right corner of the rectangle, then if we iterate through points that lie to the left of it, we can guarantee the formulation of a valid rectangle if it has:

• a greater y value than the original point
• a lower y value than any previous valid points

We start off by sorting the array with a custom lambda function. This ensures that points with larger x values come first, and in case of a tie, the point with the smaller y value is placed earlier.

sort(points.begin(), points.end(), [](const vector<int>& p1, const vector<int>& p2) {
    return p1[0] == p2[0] ? p1[1] < p2[1] : p1[0] > p2[0];
});

Then, we keep track of how many valid rectangles we can form:

int ans = 0;

Before running a double for loop, iterating through all pairs (this is feasible as there is a maximum of 50 elements):

for (int i = 0; i < points.size()-1; ++i) {
    int y = INT32_MAX;
    for (int j = i+1; j < points.size(); ++j) {
        if (points[j][1] >= points[i][1] && y > points[j][1]) {
            ++ans;
            y = points[j][1];
        }
    }
}

The function basically takes every point as a potential bottom-right corner of the rectangle, and iterates through all the points that lie to the left of it. Every time it sees a potential candidate, one that has

• a greater y value than the original point
• a lower y value than any previous valid points

it updates the y value and increments ans.

Finally, we can return ans to get our answer.

code

class Solution {
public:
    int numberOfPairs(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), [](const vector<int>& p1, const vector<int>& p2) {
            return p1[0] == p2[0] ? p1[1] < p2[1] : p1[0] > p2[0];
        });
        
        int ans = 0;
        for (int i = 0; i < points.size()-1; ++i) {
            int y = INT32_MAX;
            for (int j = i+1; j < points.size(); ++j) {
                if (points[j][1] >= points[i][1] && y > points[j][1]) {
                    ++ans;
                    y = points[j][1];
                }
            }
        }

        return ans;
    }
};

complexity

learnings

time taken