CODEWITHSUNDEEP
python
Wizard
Wizard

Reputation: 22053

Merge bisect-leftmost and bisect-rightmost to find the range of duplicates in sorted array

I am working to solve Find First and Last Position of Element in Sorted Array - LeetCode

  1. Find First and Last Position of Element in Sorted Array

Medium

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

My solution is straightforward, bisect-leftmost and bisect-rightmost, then combine them 

#leftmost solution 
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = self.search_leftmost(nums, target)
        right = self.search_rightmost(nums, target)
        if left != len(nums) and right != len(nums) and nums[left] == nums[right] == target:
            return [left, right]
        else: return [-1, -1]

    def search_leftmost(self, nums, target) -> int:
        lo = 0
        hi = len(nums)
        while lo < hi:
            mid = (lo+hi) // 2
            if target > nums[mid]:
                lo = mid + 1
            else: 
                hi = mid 
        return lo 

    def search_rightmost(self, nums, target) -> int:
        lo = 0
        hi = len(nums)
        while lo < hi:
            mid = (lo+hi) // 2
            if target >= nums[mid]:
                lo = mid + 1
            else: 
                hi = mid
        return lo -1

Get the job done in two passes,
How could merge them together and solve the problem in one pass. since there are minor differences between them.

Upvotes: 1

Views: 102

Answers (1)

recnac
recnac

Reputation: 3744

to simplify the code, you can only use search_leftmost, actually search_rightmost(nums, target) is kind of search_leftmost(nums, target + 1) - 1:

    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = self.search_leftmost(nums, target)
        right = self.search_leftmost(nums, target + 1) - 1
        # right = self.search_rightmost(nums, target)
        if left != len(nums) and right != len(nums) and nums[left] == nums[right] == target:
            return [left, right]
        else: return [-1, -1]

a more concise version is:

def searchRange(self, nums: 'List[int]', target: int) -> 'List[int]':
    left = self.search_leftmost(nums, target)
    right = self.search_leftmost(nums, target + 1) - 1
    return [left, right] if target in nums[left:left + 1] else [-1, -1]

Hope that helps you, and comment if you have further questions. : )

Upvotes: 1

Related Questions