7

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.

2
  • Should rather be on StackOverflow.com, I think.
    – haylem
    Jun 2, 2011 at 12:29
  • 2
    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, 2013 at 17:07

2 Answers 2

15

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.

1
  • 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, 2011 at 21:48
4

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
            continue
        if curr_full < curr_sub:
            full_ix +=1
        else:
            sub_ix+=1


test()
1
  • This is not an O(1) solution . . . Mar 15, 2013 at 0:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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