Given two unsorted arrays find the number of pairs where A[i] > X and B[i] > Y

user_7472803 0
Viewed 269

We are given two unsorted arrays. We have to find the number of pairs such that for each pair A[i] > X and B[i] > Y. We will have to process 1 million such queries where each query will have different X and Y given. The length of the array will also be up to 1 million.

Constraints :

1 <=A[i],B[i],X,Y <=10^9 1<= A.size, B.size, Number of Queries <= 10^6

For ex :

     A = [7,2,10,15,12,9]
     B = [10,8,5,3,4,7]

Queries :

      X Y   o/p
      9 3    2  (As we have 2 pairs which satisfy above condition (10,5), (12,4))
      6 4    3  (As we have 3 pairs which satisfy above condition (7,10), (10,5), (9,7))

Is there any better approach than brute force as we have 1 million such queries?

data-structures algorithm
2 Answers

If the queries are provided offline, there's no need for a quad tree and we can solve this in O(n log n). Insert all query-pairs and array-pairs into one list, sorted by X or a (if an X is equal to an a, place the query pair after the array pair). Process the pairs in the list by descending order (of a or X). If it's an array pair, insert it into an order-statistic tree ordered by b. If it's a query, look up in the tree the count of tree nodes (these are array pairs) that have b > Y (we already know all pairs in the tree have a > X).

user_20347870

A quadtree would be better than brute force. Interpret the pairs (a, b) as 2D co-ordinates of points, and insert them into a quadtree. Each node in the quadtree should also store its cardinality, i.e. the number of points within the area represented by that node. Each point-counting query can then be answered recursively on the quadtree, where the base case is a node whose area is either completely contained within the region a > X && b > Y (in which case return the node's cardinality), or completely disjoint from it (in which case return 0).

Other similar data structures such as a k-d tree could be used similarly.

user_122990000
Related