educative.io

Provided solution is not the most optimal

Courses
,
#1

A learner proposed the following solution:

Time complexity is not analyzed correctly. Also, this is not the most optimized solution. Provided solution’s time complexity is O(L1+L2+L3) where L1 is size of first array, L2 for second and L3 for third array. Consider this case: [1,2,4,6,7,9] [2,3,5,6,8,9] [3,4,5,7,8,9] If we use hash table and binary search, we can iterate through two arrays and find common element using hashtable, and use binary search for third array which runs logarithmic. So total complexity would be: O(L1+L2+logL3) with additional O(L1) memory. We can change the order of the arrays by size for less memory and fast performance by doing L1

#2

While your solution does perform the required task, the runtime complexity that you mentioned does not cover the worst case, i.e, the third array does not contain the smallest common number.

Suppose you have the following arrays: [1, 2, 4, 6, 7, 9] [1, 2, 4, 6, 7, 9] [3, 5, 8, 10, 11] and n1, n2 and n3 are the sizes of these arrays. We will find the smallest common number in the first two arrays, which is 1 but we will not find it in the third array using binary search, with the runtime complexity of lg(n3). So, we will find the next smallest common number, which is 2. We will again not find it in the third array, then we will find the next smallest common number, i.e., 4 in the third array. We will keep on doing so for all elements of the second array until we find the smallest common number of all the arrays. The runtime complexity of this search in the worst case will be n2*lg(n3).

Best Regards,
Waleed | Developer Advocate
Educative