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

January 7, 2025

We're working through binary search problems. This one has an initial solution with many lines duplicated. We further work the solution to use a function and a boolean variable to make the code more clean via the DRY principle.

Initial Solution

1class Solution:
2    def searchRange(self, nums: List[int], target: int) -> List[int]:
3        
4        start, end = 0, len(nums) - 1
5        result = [-1, -1]
6        while start <= end:
7            mid = start + (end - start) // 2
8            left = nums[mid - 1] if mid > 0 else float('-inf')
9            if nums[mid] == target:
10                if left != target:
11                    result[0] = mid
12                    break
13                end = mid - 1
14            elif nums[mid] < target:
15                start = mid + 1
16            else:
17                end = mid - 1
18        start, end = 0, len(nums) - 1
19        while start <= end:
20            mid = start + (end - start) // 2
21            right = nums[mid + 1] if mid < len(nums) - 1 else float('inf')
22            if nums[mid] == target:
23                if right != target:
24                    result[1] = mid
25                    break
26                start = mid + 1
27            elif nums[mid] < target:
28                start = mid + 1
29            else:
30                end = mid - 1
31        return result

Time complexity is O(logn) and space complexity is O(1).

LeetCode 207. Course Schedule

LeetCode 120. Triangle