Given a set of 2D points (x1, y1)...(xn, yn) and one point from that same set (xi, yi), I need to return the number of points such that their x coordinate is bigger than xi and y coordinate is bigger than yi.

Approach is limited to usage of basic data structures such as Array, List (incl. Linked), Stack, Queue, Trees (Binary, BST, AVL, B-tree), Hash Table and Heap.

Required time complexity is O(logn) and you can assume the data is given to you in a data structure of your choice (from the ones provided above), however you wish it sorted and is not counted towards the time complexity.

Because the requirement is O(logn), I thought about having the x-coordinates sorted in an Array and using Binary Search. Though I'm not sure how to have the y-coordinates stored in a way that will preserve the time complexity.

I could most certainly use any hint at resolving this.

CodePudding user response：

One way to solve this problem in O(logn) time is to use a binary search tree. We can insert the points into the tree, sorted by their x coordinate similar to your suggestion (except using a BST struct) and then do a binary search for the point (xi, yi).

For each node in the tree, we can check if the y coordinate is greater than yi. If it is, we can add it to our count and then search the right subtree. We can repeat this process until we have reached the leaf nodes. This approach should take O(logn) time to complete.