Find the Number of Ways to Place People I

Problem

Qn - Find the Number of Ways to Place People I

Approach

Was initially pretty hesitant to just enumerate and find all the possible pairs, but since n is at most 50, $O(n^2)$ would not be expensive. So currently the idea is that we first enumerate and create a mapping for every point we store a list of points that can be its pair. Then for every of these possible pairs, we check if it exists in that line or square. To do this efficiently, we need to create 2 sorted arrays (one for sorted by x and y axis), then we ensure that a point do not exist in between the pairs in both the sorted arrays.

This would give us $O(2n^2)+O(2nlogn)$. Now that I think about it, we can use the 2 sorted arrays to also find the map for a point to its pair, which would have marginal improvements to runtime, worst case is still the same.

Well, I realised that the process of creating the mapping will not give us $O(n^2)$, and would instead be $O(n^3)$. To find the possible pairs, we already require $O(n^2)$, and for every of that possible pairs, we will need to find if there exists a point that is found within the square made by the pair. That would be another $O(n)$.

So, instead, we can make an astute observation, as seen from this video. If we check the points starting with the smallest x, and for points with the same x, we check from the largest y, we can maintain a variable called prev_y that will be updated when we find a pair, to check if there exist a point within the square or not.

Complexity

• Time: $O(n^2)$
• Space: $O(n)$

Code

class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        n = len(points)
        res = 0
        # create a sorted array, sorted by ascending x and then
        # descending y as tie breaker
        points = sorted(points, key=lambda item: (item[0], -item[1]))
 
        for i, (x,y) in enumerate(points):
            # initialise a prev_y
            prev_y = 51 # no coord > 50
            for j in range(i+1,n):
                px, py = points[j]
                if py > y: continue
                # if no other points fall into the space between the 2 pairs
                if not py <= prev_y <= y:
                    res += 1
                    prev_y = py
 
        return res