

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

Suppose I have two lists of N 3 by 3 vectors of integers.

I need to find a quick way (say of running time at most N^(1+epsilon)) to find the vectors of the first list that have the same 1st coordinate with a vector of the second list.

Of course, I could do the following naive copmarison:

for u in list_1 do
for v in list_2
if u[1] equals v[1] then
print u;print v;
end if;end for; end for;

This, however, would require N^2 loops.

I feel that sorting the two lists according to their first coordinate and then look up for collisions is perhaps a fast way. Bubbleshort, etc., would probably take logN time, but I can't really see how to code the search for collision between the sorted lists.

Any help would be appreciated.

share|improve this question
Should rather be on, I think. – haylem Jun 2 '11 at 12:29
You can do it in O(n) without using hash tables, sets or any other data structures that are not simple arrays or linked lists. The fact that the lists are sorted helps you - inside of a while loop (not for loop) you would move a pointer to left list and a right list conditionally. The exact details can be somewhat messy, but because both lists are sorted, you only need to traverse each one once, going in one direction only. In fact, you do not need to be able to access them by index at all. The step is similar to a merge step of the merge sort algorithm. – Job Mar 14 '13 at 17:07

The naive way requires O(N^2) time, correct. Sorting the lists first takes O(N log N) time, assuming you use a good algorithm (bubblesort is O(N^2)), and the rest is O(N), so total time is O(N log N).

If you can use a hash table that allows multiple entries (C++0x's std::unordered_multimap would be ideal) you can get normal performance down to O(N). Just enter the elements of one vector into the hash table, first coordinate as the key and entire vector as the value, then go through the other vector, looking up first coordinate values.

share|improve this answer
Thanks for your suggestion. Since I am using MAGMA could you please provide some details (or a link?) on how unordered_multimap is implemented ? – manenir Jun 1 '11 at 21:48
+1 Spot on with the hash table implementation. – Ed Woodcock Jun 2 '11 at 8:39

Here is a quick and dirty O(N) Python answer for you that uses only the given lists. This only works if both lists are SORTED. I need to clean this up, but it does illustrate what you need to get done. I have chosen bad names for the variables; I will clean this up later.

def test():
    sorted_full = [1,3,5,7,9,11,15,17]
    sorted_sub = [5,11,17]

    full_ix = 0
    sub_ix = 0

    while full_ix < len(sorted_full) and sub_ix < len(sorted_sub):
        curr_full = sorted_full[full_ix]
        curr_sub = sorted_sub[sub_ix]
        if curr_full == curr_sub:
            print('Common id ' + str(curr_full) + ' at index ' + str(full_ix))
            full_ix +=1
            sub_ix +=1
        if curr_full < curr_sub:
            full_ix +=1

share|improve this answer
This is not an O(1) solution . . . – Chewy Gumball Mar 15 '13 at 0:04
@Chewy Gumball, duh, thanks, changed to O(n). – Job Mar 15 '13 at 0:08

Your Answer


