3027: Find-the-Number-of-Ways-to-Place-People-II
Hard

table of contents

Fortunately, running today’s problem just seems to be a copy of yesterday’s problem except with larger constraints (maximum number of 1000 points instead of 50).

The only addition that I added was an early break in the double for loop:

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];
            if (points[i][1] == points[j][1]) break; // this early break
        }
    }
}

This is because it is impossible to form a valid rectangle with points[i] in the bottom-right corner, as points[j] will always lie inside, meaning we can afford to early break.

code

class Solution {
public:
    int numberOfPairs(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), [](const auto& p1, const auto& 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];
                    if (points[i][1] == points[j][1]) break;
                }
            }
        }
        return ans;
    }
};

complexity

time taken