Leetcode 34: Find First and Last Position of Element in Sorted Array

The original question can be found here.

The question is asking to return a tuple with first and last position of target element in a sorted array.

Brute Force

Iterate through the whole array and keep track of first and last position of target element.

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        res = [-1, -1]
        if not nums:
            return res
        for index, element in enumerate(nums):
            if element == target:
                if res[0] == -1:
                    res[0] = index
                res[1] = index
        return res

Time complexity: O(n). Space complexity: O(1).

Binary Search

This question is explictly asking for O(logn) solution. If we infer algorithm from time complexity, natually it should be binary search. If you’re not familiar with this topic, please visit my another post here. So we’ll do 2 searches, one for finding left most position, and the other one for finding right most position.

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        res = [-1, -1]
        if not nums:
            return res
        res[0] = self.find_element(nums, target, True)
        res[1] = self.find_element(nums, target, False)
        return res
    
    def find_element(self, nums: List[int], target: int, find_left: bool) -> int:
        left, right = 0, len(nums) - 1
        while left + 1 < right:
            mid = (left + right) // 2
            if nums[mid] == target:
                if find_left:
                    right = mid
                else:
                    left = mid
            elif nums[mid] < target:
                left = mid
            else:
                right = mid
        
        if find_left:
            if nums[left] == target:
                return left
            if nums[right] == target:
                return right
        else:
            if nums[right] == target:
                return right
            if nums[left] == target:
                return left
        
        return -1

Time complexity: O(logn). Space complexity: O(1).