Click here to see the problem details on LeetCode.
Problem Overview
We will be given an integer array (sorted in no-decreasing order) and an integer. We have to find the position of the given integer from the Array. But there is a trick. That is, we have to find the first and last position of the given integer.
Suppose the array is: [1, 4, 5, 5, 7, 10, 10] and the target value is: 10. the value 10 appears two times in the Array. So the first position is: 5 and the second position is 6. If there is only one value in an array, the first and last positions will be the same. For example,
nums = [1, 2, 3, 4, 5]
target = 3
result = [2, 2]If no target value exists in the Array, the answer will be [-1, -1].
First of all, we can’t use linear search to search the value. Because we have to solve this in O(log n) time complexity, but the time complexity of the linear search is O(n).
So, to solve this problem, we have to use Binary Search. I hope you already know about the binary search algorithm. Generally, this algorithm stops when it finds the searching value. But we need the first and last position. For that, we have to change the algorithm a little bit. Let’s see how to do it.
Coding Part
The most important part of the problem is, finding the two positions. For that, we will use two functions. Both are mainly binary search algorithms.
To find the leftmost position (AKA the first position) of the target value, we will continue searching on the left side of the array even if we detect the target value. But whenever we find the target value, we will store the index of the target value in a variable. Each time we will update the variable if a target value is detected.
The function will return the variable. The initial value of the variable will be -1.
The same way is applicable for searching for the last position. But this time, we will continue searching on the right side of the array even if we detect the target value.
Let’s see the code for better understanding.
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
first = self.firstPosition(nums, target)
last = self.lastPosition(nums, target)
return [first, last]
def firstPosition(self, nums, target):
start = 0
end = len(nums)-1
index = -1
while start <= end:
mid = (start+end) // 2
if target <= nums[mid]:
end = mid - 1
else:
start = mid + 1
if target == nums[mid]:
index = mid
return index
def lastPosition(self, nums, target):
start = 0
end = len(nums)-1
index = -1
while start <= end:
mid = (start + end) // 2
if target >= nums[mid]:
start = mid+1
else:
end = mid-1
if target == nums[mid]:
index = mid
return indexI hope you got the idea about the problem and the solution. If you submit this code, it will get accepted.