5/11/2020

[LeetCode] 34. Find First and Last Position of Element in Sorted Array

Problem : https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Search the left most element and right most element separately.

Push the "right' pointer to left as far as possible to find the left most element.
Push the "left" pointer to right as far as possible to find the right most element.



class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        
        def leftMost(left, right):
            while left < right:
                mid = left + (right - left) // 2
                
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid   # push 'right' to left as far as possible
            
            if right < len(nums) and nums[right] == target:
                return right
            
            return -1
        
        def rightMost(left, right):
            while left < right:
                mid = left + (right - left) // 2
                
                if nums[mid] <= target:
                    left = mid + 1  # push 'left' to right as far as possible
                else:
                    right = mid
                
            return left - 1
     
        left = leftMost(0, len(nums))
        if left == -1:
            return [-1, -1]
        
        return [left, rightMost(left, len(nums))]

Use built-in function:


class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = bisect.bisect_left(nums, target)
        if left == len(nums) or nums[left] != target:
            return -1, -1
        
        right = bisect.bisect_right(nums, target) - 1
        
        return left, right

Edited on 02/27/2021. Use buillt-in lib.

No comments:

Post a Comment