Find First And Last Position of Element in Sorted Array
Patrick LeatonGiven an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]
Example 3:
Input: nums = [], target = 0 Output: [-1,-1]
Constraints:
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9nums is a non-decreasing array.-10^9 <= target <= 10^9
The description was taken from https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/.
#O(Log(N)) Time, O(1) Space
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def binary_search(side:str) -> int:
left, right = 0, len(nums) - 1
spot = -1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else:
spot = mid
if side == "L":
right = mid - 1
else:
left = mid + 1
return spot
return [binary_search("L"), binary_search("R")]The problem description states that we need to write an algorithm with an O(Log(N)) time complexity.
That lets us know that we'll need a binary search, but even if that clarification wasn't there, the clues are all here that we would use it.
We are given a sorted array and are asked to return a specific target within that array.
If we only needed to find a position of the element within the array, that would be simple enough. We would just need a normal binary search.
To find the leftmost and rightmost position of the element, however, we don't need to tweak the traditional algorithm that much.
We can solve this problem by writing a normal binary search algorithm to find the element, which would entail cutting the current search space in half during each iteration. Once we find the target, however, we will just need to cut down the current search space further to find either the leftmost or rightmost position of it.
To achieve this, we can implement an identifier that lets us know which position we are looking for. If we know that in the binary search we are looking for the leftmost position, then once we find the target, all we will need to do is continuously cut down the right search space and vice versa for the rightmost position.
Let's start by creating our binary_search function.
The function will take a string identifier for the side of the target we are looking for and will return that target position's index.
def binary_search(side:str) -> int:
We'll set our left and right pointers to the beginning and end of the array, setting our initial search space to the entire array.
left, right = 0, len(nums) - 1
We'll also initialize the index spot to a negative one. In the scenario that the target isn't in the array, this is what we will be returning.
spot = -1
While the left and right pointers haven't crossed each other, (overlapping is fine because we can have an array of a single number according to the constraints), we will continue searching for the target.
while left <= right:
Let's set a mean index between the left and right pointers.
mid = (left + right) // 2
If that mid number is less than the target, then we will cut down the left search space.
if nums[mid] < target:
left = mid + 1
If that mid number is greater than the target, then we will cut down the right search space.
elif nums[mid] > target:
right = mid - 1
If the mid number is the target, we will save the spot and cut down the search space for the current side we are looking for.
else:
spot = mid
If we are looking for the leftmost position, we will cut down the right search space.
if side == "L":
right = mid - 1
Otherwise, we are looking for the rightmost position so we will cut down the left search space.
else:
left = mid + 1
Once the pointers cross each other, we have exhausted the entire search space.
When this happens, we will return the spot of the target if we found it, or the initial negative one value that the spot was initialized to if we didn't.
return spot
Now that our helper function is built, we just need to make a call to find the leftmost position and a second call to find the rightmost position, saving those outputs to a two-indexed array.
return [binary_search("L"), binary_search("R")]