Better way to find matches in two sorted lists than using for loops?

Question

I have two sorted lists, both in non-decreasing order. For example, I have one sorted linked list with elements [2,3,4,5,6,7...] and the other one with elements [5,6,7,8,9...].

I need to find all common elements in both lists. I know I can use a for loop and a nested loop to iterate all matches to find the same two elements. However, is there another way to do this that has running time less than O(n^2)?

No, @JasonSperske - "increasing" would mean that duplicates are forbidden. By saying "non-decreasing", he/she implies that duplicates are permitted. — Dawood ibn Kareem, Oct 02 '13 at 03:11
using an algorithm and knowing that they are sorted, you can make it in O(n) — nachokk, Oct 02 '13 at 03:16
@DavidWallace, I was so ready to say "no way", until I looked it up : http://stackoverflow.com/questions/1963474/is-a-non-decreasing-sequence-increasing you learn something new every day I guess :) — Jason Sperske, Oct 02 '13 at 03:46
possible duplicate of [Finding common elements in two arrays of different size](http://stackoverflow.com/questions/4529819/finding-common-elements-in-two-arrays-of-different-size) — madth3, Oct 02 '13 at 04:20

Blorgbeard · Accepted Answer · 2015-06-17T20:26:09.880

10

You can do it in O(n) time. Pseudocode:

a = list1.first
b = list2.first
repeat:
    if a == b:
        output a
        a = list1.next
        b = list2.next
    elif a < b:
        a = list1.next
    else
        b = list2.next
until either list has no more elements

edited Jun 17 '15 at 20:26

answered Oct 02 '13 at 03:16

Blorgbeard

101,031
48
228
272

score 1 · Answer 2 · answered Jan 05 '14 at 16:11

Actually you can do a little better:

def dropWhile(ls, cond):
    if cond(ls[0]): return dropWhile(ls[1:], cond)
    return ls

def bisect(ls, v):
    """
    Finds largest i s.t. ls[i]<=v and returns it.
    If no such i exists it returns -1.
    Runs in O(log n)
    """
    pass

def find_commons(ls1, ls2, ret):
    if not (ls1 or ls2): return
    i = bisect(ls2, ls1[0])
    if i<0: find_commons(ls2, ls1[1:], ret)
    elif ls2[i]==ls1[0]:
        ret.append(ls1[0])
        trim = lambda ls: dropWhile(lambda x: x==ls1[0], ls)
        find_commons(trim(ls1), trim(ls2), ret)
    else: find_commons(ls2[i+1:], ls1, ret)

score 0 · Answer 3 · answered Oct 02 '13 at 03:14

0

Convert the first list to a HashSet; then iterate through the second list checking whether each element is in the HashSet.

answered Oct 02 '13 at 03:14

Dawood ibn Kareem

77,785
15
98
110

score 0 · Answer 4 · answered Oct 02 '13 at 03:19

In the main loop, take the first elements from both lists and compare. If they are not equal, scan the list with less element until it gets equal or more than the element of the other loop. If it gets equal, this means you found a common element. Read both list sequentially until the common element is passed. Continue the main loop. The complexity of this approach is O(n+m).

Better way to find matches in two sorted lists than using for loops?

4 Answers4

Linked

Related