Question
Design an algorithm to find all the common elements in two sorted lists of numbers. For example, for the lists 2, 5, 5, 5 and 2, 2, 3, 5, 5, 7, the output should be 2, 5, 5.What is the maximum number of comparisons your algorithm makes if the lengths of the two given lists are m and n, respectively?
Answer
To find all the common elements in two sorted lists of numbers, you can use a simple algorithm that compares the elements of the two lists. Here's the algorithm:
-
Initialize two pointers, one for each list, starting at the first element.
-
While both pointers are within the bounds of their respective lists:
- If the elements pointed to by both pointers are equal, add the element to the common elements list and move both pointers to the next element.
- If the element in the first list is smaller, move the first pointer to the next element.
- If the element in the second list is smaller, move the second pointer to the next element.
-
Return the common elements list.
The algorithm works because the lists are sorted. The maximum number of comparisons made by this algorithm occurs when both lists are fully traversed. In the worst-case scenario, each element in one list must be compared to every element in the other list.
Therefore, the maximum number of comparisons is m * n, where m is the length of the first list and n is the length of the second list.