Discussion on: A common coding interview question

View post

Python solution, not in a nice format, and assuming the input are two integer arrays:


def common_arr(first, second):
    mi, ma = (first,second) if len(first) <= len(second) else (second,first)
    common = []
    i = 0
    j = 0
    while(i < len(mi)):
        if(mi[i] == ma[j]):
                common.append(mi[i])
                i += 1
                if j < len(ma)-1:
                    j += 1
                else:
                    break
        elif mi[i] < ma[j]:
            i += 1
        else:
            if j < len(ma)-1:
                j += 1
            else:
                break

    return common

arr = common_arr([1,2,3,4,5,9],[3,5,6,8,9])
print(arr)

So idea:
You iterate over the smallest array, at each step, you are in one of 3 situations

arr1[i] == arra2[j] // you increment i and j because of the invariant, that says the arrays are sorted, so if you found a match you can safely increment.

arr1[i] < arr2[j] // since at index i we have the smallest element, we increment that one because being sorter we ca safely increment until we hit what is at index j or greater

arr1[i] < arr2[j] // same as above only for j