SOLVED: LeetCode: 34. Find First and Last Position of Element in Sorted Array
A solution to LeetCode 34. First and Last Position of Element in Sorted Array
Intuition
The task is to find the starting and ending position of a given target value in a sorted array. My first thought is to leverage the sorted nature of the array to find the target efficiently. However, a linear scan could also work but might not be the most efficient method, especially for large arrays.
Approach
The approach implemented in the provided code is a linear scan through the array. It iterates over each element, comparing it with the target value. When it encounters the target for the first time, it records this position as both the first and last occurrence (initially). For subsequent encounters of the target value, it updates the last occurrence position. This approach guarantees that we find the first and last positions of the target value if it exists in the array.
Complexity
- Time complexity: O(n): The reason for this is that, in the worst case, the algorithm needs to iterate through the entire array to find the first and last occurrences of the target value.
- Space complexity: O(1): The space complexity is constant because the solution uses a fixed amount of space (a few variables) regardless of the input array size.
Code
class Solution(object):
def search_range(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
first = None
last = None
for index, value in enumerate(nums):
if value == target:
if first is None:
first = index
last = index
continue
last = index
return [-1, -1] if first is None else [first, last]
#Testing Arena:
assert search_range([5, 7, 7, 8, 8, 10], 8) == [3, 4]
assert search_range([5, 7, 7, 8, 8, 10], 6) == [-1, -1]
assert search_range([], 0) == [-1, -1]
#IMPROVED SOLUTION O(Log N)
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def binary_search(nums, target, is_searching_left):
left = 0
right = len(nums) - 1
idx = -1
while left <= right:
mid = (left + right) // 2
if nums[mid] > target:
right = mid - 1
elif nums[mid] < target:
left = mid + 1
else:
idx = mid
if is_searching_left:
right = mid - 1
else:
left = mid + 1
return idx
left = binary_search(nums, target, True)
right = binary_search(nums, target, False)
return [left, right]Credits, Sources, Etc
Made with 🤍🫶🏿 in N🗽C by @iamserda
