Intersection of Two Sorted Arrays

I made a second attempt in the “Intersection of Two Sorted Arrays” problem from my growth plan document, except I wasn’t able to come up with both optimal solutions within 35 minutes, because I messed up with the binary search approach.

This is the link to the challenge on LeetCode:

(However, this is an unsorted version of the problem)

From reading the solutions, what I don’t understand is why in the BFS function, we need to have an explicit parameter for the start index, and when update high in the while loop, we don’t offset by -1.

Hey Gregory,
I’m assuming you mean Binary Search and not BFS in your question.

To answer your questions,

  1. The explicit start parameter is required because we don’t want to reuse a number twice. Eg: intersection of A = [1,2,2,2] and B = [1,2,2,3] is [1,2,2]. In this case if we are searching for the last(third) 2 in array B, our start parameter would be index 3, and won’t be able to find a third 2 in array B.

  2. We don’t offset by one, because we are looking for the first occurrence of the number, starting from the start parameter. I’d suggest reviewing the Binary Search workshop to get a better idea of this. There are different ways to write the Binary Search algorithm (l<r, l<=r, and l<r+1), which modify the update conditions of the left and right parameters differently. You should try rewriting it with the template you learned during the Binary Search workshop.

Also you can take a look at this Programming Session, where Derrick does a great job of explaining the approach in depth: