Solution

Method 1 – Brute Force Rectangle Check

Intuition

We want to count pairs (A, B) such that A is strictly upper-left of B and there are no other points inside or on the rectangle defined by A and B. By sorting points and using a 2D Fenwick Tree, we can efficiently count the number of valid pairs by processing points in order and querying for emptiness.

Approach

Sort all points by x ascending, then y ascending.
For each point B (in sorted order):
- For each point A before B, if A.x < B.x and A.y > B.y, check if there are no other points in the rectangle (A.x, B.x) x (B.y, A.y).
- Use a 2D Fenwick Tree to keep track of points already processed.
- For each B, query the number of points in the rectangle (A.x+1, B.x-1) x (B.y+1, A.y-1). If zero, count the pair.
Return the total count.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int numberOfPairs(vector<vector<int>>& points) {\n        int n = points.size();\n        sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {\n            if (a[0] != b[0]) return a[0] < b[0];\n            return a[1] > b[1];\n        });\n        int ans = 0;\n        for (int i = 0; i < n; ++i) {\n            auto& first = points[i];\n            for (int j = i + 1; j < n; ++j) {\n                auto& second = points[j];\n                if (first[0] > second[0] || first[1] < second[1]) continue;\n                bool valid = true;\n                for (int k = i + 1; k < j; ++k) {\n                    auto& third = points[k];\n                    if (first[0] <= third[0] && third[0] <= second[0] &&\n                        first[1] >= third[1] && third[1] >= second[1]) {\n                        valid = false;\n                        break;\n                    }\n                }\n                if (valid) ans++;\n            }\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> numberOfPairs</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">>></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> points</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<sp

Related Tags

Continue Practicing