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

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

Leetcode Solutions

Key approach of the solution: Binary Search for First and Last Position

  1. Define a helper function findBound that performs a binary search to find the first or last occurrence of the target.
  2. Use two pointers, begin and end, to keep track of the current search range.
  3. While begin is less than or equal to end, calculate the middle index mid.
  4. If nums[mid] is equal to the target, check if it's the first or last occurrence based on the isFirst flag.
  5. If searching for the first occurrence and mid is 0 or nums[mid - 1] is not the target, return mid.
  6. If searching for the last occurrence and mid is the last index or nums[mid + 1] is not the target, return mid.
  7. Adjust the begin or end pointers based on the comparison between nums[mid] and the target.
  8. If the target is not found, return -1.
  9. In the main function searchRange, call findBound twice with isFirst set to true and false to find the first and last positions, respectively.
  10. If the first position is -1, return [-1, -1] as the target is not present.
  11. Otherwise, return the array containing the first and last positions found.
UML Thumbnail

Alternative approach: Linear Scan for First and Last Position

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...