<p>You are given a 2D array <code>points</code> of size <code>n x 2</code> representing integer coordinates of some points on a 2D-plane, where <code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code>.</p>

<p>We define the <strong>right</strong> direction as positive x-axis (<strong>increasing x-coordinate</strong>) and the <strong>left</strong> direction as negative x-axis (<strong>decreasing x-coordinate</strong>). Similarly, we define the <strong>up</strong> direction as positive y-axis (<strong>increasing y-coordinate</strong>) and the <strong>down</strong> direction as negative y-axis (<strong>decreasing y-coordinate</strong>)</p>

<p>You have to place <code>n</code> people, including Alice and Bob, at these points such that there is <strong>exactly one</strong> person at every point. Alice wants to be alone with Bob, so Alice will build a rectangular fence with Alice&#39;s position as the <strong>upper left corner</strong> and Bob&#39;s position as the <strong>lower right corner</strong> of the fence (<strong>Note</strong> that the fence <strong>might not</strong> enclose any area, i.e. it can be a line). If any person other than Alice and Bob is either <strong>inside</strong> the fence or <strong>on</strong> the fence, Alice will be sad.</p>

<p>Return <em>the number of <strong>pairs of points</strong> where you can place Alice and Bob, such that Alice <strong>does not</strong> become sad on building the fence</em>.</p>

<p><strong>Note</strong> that Alice can only build a fence with Alice&#39;s position as the upper left corner, and Bob&#39;s position as the lower right corner. For example, Alice cannot build either of the fences in the picture below with four corners <code>(1, 1)</code>, <code>(1, 3)</code>, <code>(3, 1)</code>, and <code>(3, 3)</code>, because:</p>

<ul>
	<li>With Alice at <code>(3, 3)</code> and Bob at <code>(1, 1)</code>, Alice&#39;s position is not the upper left corner and Bob&#39;s position is not the lower right corner of the fence.</li>
	<li>With Alice at <code>(1, 3)</code> and Bob at <code>(1, 1)</code>, Bob&#39;s position is not the lower right corner of the fence.</li>
</ul>
<img alt="" src="https://assets.leetcode.com/uploads/2024/01/04/example0alicebob-1.png" style="width: 750px; height: 308px;padding: 10px; background: #fff; border-radius: .5rem;" />
<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2024/01/04/example1alicebob.png" style="width: 376px; height: 308px; padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem;" />
<pre>
<strong>Input:</strong> points = [[1,1],[2,2],[3,3]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> There is no way to place Alice and Bob such that Alice can build a fence with Alice&#39;s position as the upper left corner and Bob&#39;s position as the lower right corner. Hence we return 0. 
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2024/02/04/example2alicebob.png" style="width: 1321px; height: 363px; padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem;" />
<pre>
<strong>Input:</strong> points = [[6,2],[4,4],[2,6]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> There are two ways to place Alice and Bob such that Alice will not be sad:
- Place Alice at (4, 4) and Bob at (6, 2).
- Place Alice at (2, 6) and Bob at (4, 4).
You cannot place Alice at (2, 6) and Bob at (6, 2) because the person at (4, 4) will be inside the fence.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2024/02/04/example4alicebob.png" style="width: 1123px; height: 308px; padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem;" />
<pre>
<strong>Input:</strong> points = [[3,1],[1,3],[1,1]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> There are two ways to place Alice and Bob such that Alice will not be sad:
- Place Alice at (1, 1) and Bob at (3, 1).
- Place Alice at (1, 3) and Bob at (1, 1).
You cannot place Alice at (1, 3) and Bob at (3, 1) because the person at (1, 1) will be on the fence.
Note that it does not matter if the fence encloses any area, the first and second fences in the image are valid.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 1000</code></li>
	<li><code>points[i].length == 2</code></li>
	<li><code>-10<sup>9</sup> &lt;= points[i][0], points[i][1] &lt;= 10<sup>9</sup></code></li>
	<li>All <code>points[i]</code> are distinct.</li>
</ul>

class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        # Coordinate compression
        # Extract unique x and y coordinates and sort them
        x_coords = sorted(set(x for x, _ in points))
        y_coords = sorted(set(y for _, y in points))

        # Create mapping from original coordinates to compressed indices
        x_map = {x: i for i, x in enumerate(x_coords)}
        y_map = {y: i for i, y in enumerate(y_coords)}

        # Compress the original points using the mappings
        compressed_points = [(x_map[x], y_map[y]) for x, y in points]

        # Create 2D prefix sum array
        # Initialize grid with one extra row and column for easier calculations
        grid = [[0] * (len(y_coords) + 1) for _ in range(len(x_coords) + 1)]

        # Mark the positions of points in the grid
        for x, y in compressed_points:
            grid[x + 1][y + 1] += 1

        # Calculate prefix sums
        for i in range(1, len(x_coords) + 1):
            for j in range(1, len(y_coords) + 1):
                grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1]

        count = 0
        # Iterate through all pairs of points
        for i, (x1, y1) in enumerate(compressed_points):
            for j, (x2, y2) in enumerate(compressed_points[i + 1 :], i + 1):
                # Determine which point is Alice's and which is Bob's
                if x1 <= x2 and y1 >= y2:
                    alice_x, alice_y = x1, y1
                    bob_x, bob_y = x2, y2
                elif x2 <= x1 and y2 >= y1:
                    alice_x, alice_y = x2, y2
                    bob_x, bob_y = x1, y1
                else:
                    continue  # Skip if points don't form a valid rectangle

                # Calculate number of points in the rectangle using prefix sum
                points_in_rect = (
                    grid[bob_x + 1][alice_y + 1]
                    - grid[alice_x][alice_y + 1]
                    - grid[bob_x + 1][bob_y]
                    + grid[alice_x][bob_y]
                )

                # Increment count if only Alice and Bob are in the rectangle
                if points_in_rect == 2:
                    count += 1

        return count


# Time Complexity: O(n^2), where n is the number of points
# - Sorting and coordinate compression: O(n log n)
# - Creating prefix sum array: O(n^2) in the worst case
# - Iterating through all pairs of points: O(n^2)
# The dominant term is O(n^2) from the nested loops.

# Space Complexity: O(n^2)
# - Coordinate mappings and compressed points: O(n)
# - Prefix sum grid: O(n^2) in the worst case when all coordinates are unique
# The dominant term is O(n^2) from the prefix sum grid.

4361