Common subview between two views hierarchy

Question

I have two views V1 and V2 which have n and m subviews respectively. Among the m and n subviews there is a view 'p' which is common.

I am trying to find out this common view 'p' among m and n subviews. Obviously the brute force approach of O(m*n) works fine to get the common view p. But I would like to know if there is a better efficient algorithm that I can use to get that one unique common view which is present in both V1 and V2.

V1 = {B, K, L, P, O, B, C, A, Q, R} V2 = {A, X, W, S, T, K, O};

Running brute-force gives me O as the answer in O(m*n). Here the views O and O have same class. As pointed out in the comments, I am NOT looking for views which have same frame.

Any efficient way to do this?

After some thoughts and also @CrimsonChris answer's, I have the below solution

- (void)commonView:(UIView *)a1 with:(UIView *)a2 {

    NSMutableSet *s = [[NSMutableSet alloc] initWithCapacity:[[a1 subviews] count]];
    for (UIView *a1SubViews in [a1 subviews]) {
        [s addObject:[a1SubViews class]];
    }

    for (UIView *a2SubView in [a2 subviews]) {
        if ([s containsObject:[a2SubView class]]) {
            NSLog(@"#Boom, I found the common view %@", a2SubView);
            return;
        }
    }
    NSLog(@"NO common subview");
    return;
}

But this uses O(n) space, can we optimize it more further?

Answer 1

You could build a hash table out of the subviews with each subview's class name as the key.

That's O(n) performance but also O(n) in size.

Answer 2

We can do this with O(1) space and O(max(m , n) log m ) time (with m <= n).

If we have two array int[]a and b with n and m elements:

• First, we can sort array b -> time complexity is O(mlogm)
• For each element of array a -> use binary search to search for this element in array b -> time complexity is O(nlogm)

So at the end, we have a total time complexity is O(max(m , n) log m ) with space is O(1) if you use in-place sorting algorithm (for example: merge - sort).

We can replace int[] a and b with any Object array, as long as these Object are comparable. (Using hash code is also an option).