Sorting Algorithms in Python: Intersection of Two Sorted Arrays

In this video, we will be solving the following problem:

Problem:
Given two arrays, A and B, determine their intersection. That is, what elements are common to A and B?

There is a one-line solution to this in Python that will also work in the event when the arrays are not sorted. However, since we are aware that the arrays A and B are sorted, we can use this to our advantage and solve the problem in a way that leverages this and gives us a slightly better runtime.

The software written in this video is available at:

Do you like the development environment I'm using in this video? It's a customized version of vim that's enhanced for Python development. If you want to see how I set up my vim, I have a series on this here:

If you've found this video helpful and want to stay up-to-date with the latest videos posted on this channel, please subscribe:

[wulymammoth]

This is the second video I've watched from you, but it is so clear. You literally code the solution in a manner that is almost identical to the way you've described the procedure. Thank you for sharing the time complexity as well. It would be a nice touch to add the space complexity, too. But again, thanks, Vinnie!

[TheFotoGuys]

Very good and helpful video! Thank you :D

[muraliperi]

Hi Lucid, Hope you are having a great day ! You are a great teacher as always when it comes to simplifying complicated problem into easy and simple one . You have deserved more subscribers than the current counts . Coming to the point, i have applied below algorithm and its works too.
Just want to check your opinion on this .

A = [2, 3, 3, 5, 7, 11]
B = [3, 3, 7, 15, 31]

def intersection(a, b):
i = 0
j = 0
result = []
while i < len(a) and j < len(b):
if a[i] == b[j] and a[i] not in result:
result.append(a[i])
i += 1
j += 1
elif a[i] < b[j]:
i += 1
else:
j += 1
return result
intersection(A, B)

[husseinfathy]

def intersect_sorted_array(a, b):
s = set()
for i in a:
if i in b:
s.add(i)
return list(s)


# Is this logic correct also.


# BIG THANKS.

[keaganferrao]

What would be the time complexity if we use the built-in intersection( ) method?

[rohi]

Hi Can you make a video on Couting sort algorithm?

[devashishtuteja]

can we use hash table method you used in anagram..printing only those keys with value greater than 1, i think this was a bit complex code..but thanks to you I started enjoying programming though!!

[khaihoang]

which algorithm did you use to solve this prob, sir?

[GopalaKrishnangk]

How about using binary search algo here, but time complexity is high i believe O(n^2)


def intersetc(a1, a2):
for i in range(len(a1)):
bb = binary_search(a1[i], a2, 0, len(a2)-1)
if bb:
print(bb)




def binary_search(target, data, low, high):
mid = low+high // 2
while low <= high :
if data[mid] == target:
return data[mid]
elif target < data[mid]:
return binary_search(target, data, low, mid-1)
else:
return binary_search(target, data, mid+1, high)
return None

[Roblox]

def intersect_sorted_array(A, B):
common = []
for i in A:
for j in B:
if i==j:
common.append(i)
return common

Another solution