3

So I have an array of distinct pairs of positive integers. That is, my array looks something like this (for instance):

{ (1,5) , (6,4), (5,3), (2,3), (2,4) }

And my task is, for a given pair (a,b) find (if it exists) the pair (c,d) which has c > a and d > b and, in addition, is the "minimal" such pair (that is, c is minimal and, if there are multiple pairs which satisfy this with the same c, then d is minimal).

So for instance, if I run the query for the above array for pair (1,1), it should return (2,3) and if I feed it (5,2) it should return (6,4).

Now the problem is that I have to run multiple queries so linear time is not good enough. And my question is: is there any way in / any law by which I can "sort" such an array so that I can later run binary searches on it to find my answer?

I was thinking I could simply go like this: let (x1,y1) and (x2,y2) be two pairs to compare. Then:

if(x1<x2)
    //pair 1 is smaller
else if(x1==x2 && y1<y2)
    //pair 1 is smaller
else
    //pair 2 is smaller 

This seemed to solve most cases, however.. if I have an array which looks like this:

{ .... (50,60) ..... }

where (50, 60) is at the middle of the array. And I run a query for (40,70) for instance. The problem is that the pair that I want to find could be either on the left or on the right of (50,60) (we could have something like (45,90) on the right of (50, 60), but then again we could only have (x,10) on the left of (50,60) where x<50 so no pair on the left would satisfy our condition and I'd have to look to the right).

So to sum it up, if I'm running a query for pair (x1,y1) and through my binary search I come across and element (x2,y2) which has x1<x2 and y1>=y2, then my algorithm cannot decide whether it should keep searching left or right. So I have to search both sides and in a worst case scenario this ends up being O(n).

So is there a more clever way in which you can do this? Any help would be appreciated. Thanks in advance :)

1

Without using any extra storage, I think the best you can do is a binary search on the first element, then linear search forward from there to match the second element. This has O(n) worst case performance, but should be close to O(log n) in the average case, especially since you only need to search this way after hitting an ambiguous direction.

If you have sufficient storage and the time to do the precalculation, you could make a two-dimensional pre-sorted data structure, like the following for your example { (1,5) , (6,4), (5,3), (2,3), (2,4) }:

[(1, [(2,3), (5,3), (2,4), (6,4), (1,5)]),
 (2, [(2,3), (5,3), (2,4), (6,4)]),
 (5, [(5,3), (6,4)]),
 (6, [(6,4)])]

Then just do a binary search for the 1, 2, 5, or 6 as the first element, which gives you a list sorted by the second element, where you can do another binary search. This is O(n2) for space, but gives you O(log n) in runtime.

  • The second solutions (with the array) seems to be the closest to what I am looking for. However, the problem with precalculations is I'm trying to use these results for a dynamic data structure in which I do constant add and remove operations (my "array" is actually a BST in my implementation but I've simplified the problem to an array for the sake of this forum post). Also I'm not sure if I can afford O(n^2) space, but I will definitely think about this. Thanks for the answer :). Any other solutions would be welcome, if possible. – Nu Nunu Nov 24 '14 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.