Find First and Last Position of Element in Sorted Array

Hello everyone,

Today we will be going over another LeetCode problem: "Find First and Last Position of Element in Sorted Array." As always, source code is at the end of the post. Without further adieu, lets get right into it!

Find First and Last Position of Element in Sorted Array

The problem is asking us to return a vector<int> with the position of the first and last occurrence of a given target value:

There is a time complexity requirement of O(log N). If there is no occurrence of the target value, we return a vector<int> containing [-1, -1].

Solution

We know that the vector is sorted in ascending order and that the run time complexity must be O(log N).

We can achieve the O(log N) time complexity by using the binary search algorithm. Binary search will allow us to find at least one occurrence of the target value and also tell us if the target does not exist within the array.

The issue with binary search is that it gives the position of the first occurrence of the target it finds. That means that the position it gives is not necessarily the very first or last occurrence of the target, as shown in the image below:

To solve this, we will be using "The Battleship" method. "Battleship" is a board game where you try to sink all of your opponent's ships. The thing is that the locations of those ships are unknown to you because of a barrier between you and your opponent. A common tactic used in the game is to first figure out the location of an opponent's ships by guessing random locations. Once you hit one of your opponent's ships, you start attacking locations in proximity of the first hit. You keep doing this until you sink the ship:

In our case, the result from the binary search is our "first hit". Starting at the location given by the binary search, we do a proximal check to determine where are the first and last occurrence of the target.

Results

The results were pretty good. I don't really have much to say about them. One thing though is that I wonder how some people made solutions that are faster than 4 ms based on distribution graphs.

Another is that I was looking through the official solutions for this problem, and I was surprised that one of them was a linear search solution. I may submit a linear search solution to see if it will be accepted, since the problem asked for a O(log N) solution, not an O(N) solution.

Conclusion

Overall, this was a pretty good problem. I am currently looking for a new problem, so it will be a while until I post again. Until then, thank you for reading!

Link to source code: https://github.com/EricFlorin/Leetcode-Solutions/blob/master/Find%20First%20and%20Last%20Position%20of%20Element%20in%20Sorted%20Array.cpp