First and Last Position of Element
Problem Statement
Given a sorted array nums and a target value target, return the starting and ending position of target in the array. If target is not found, return [-1, -1].
Example: nums = [5,7,7,8,8,10], target = 8 → Output: [3,4]
Approach 1: Two Binary Searches
Explanation: Use binary search twice: once to find the first occurrence, once for the last occurrence.
Time Complexity: O(log n)
Space Complexity: O(1)
function findFirst(nums, target):
low, high = 0, n-1
first = -1
while low <= high:
mid = (low+high)//2
if nums[mid] == target:
first = mid
high = mid - 1
else if nums[mid] < target:
low = mid + 1
else:
high = mid - 1
return first
function findLast(nums, target):
low, high = 0, n-1
last = -1
while low <= high:
mid = (low+high)//2
if nums[mid] == target:
last = mid
low = mid + 1
else if nums[mid] < target:
low = mid + 1
else:
high = mid - 1
return last
return [findFirst(nums,target), findLast(nums,target)]
💡 Think: Run binary search twice to pin leftmost and rightmost target boundaries.
Approach 2: Single Pass Modified Binary Search
Explanation: Use a modified binary search to find boundaries efficiently.
Time Complexity: O(log n)
Space Complexity: O(1)
// Similar logic combining first & last in one loop by tracking boundaries
💡 Think: Track first/last during one binary loop by adjusting bounds on equals.
Approach 3: Linear Scan (Naive)
Explanation: Scan array from start to end to find first and last occurrences.
Time Complexity: O(n)
Space Complexity: O(1)
start = -1, end = -1
for i in 0..n-1:
if nums[i] == target:
if start == -1:
start = i
end = i
return [start, end]
💡 Think: Walk once to record the first hit and keep updating the last index.