34_first_last_elem_sorted_array

dz / leetcode / 34_first_last_elem_sorted_array

Summary

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity.

Node Tree

• intuition
  • two_pass_binary_search
    • two_binary_searches
      • find_first_pos
        • only_when_midpoint_is_target
        • update_midpoint
        • find_last_pos
          • update_midpoint
    • find_lower_bound
      • find_upper_bound
    • find_upper_bound
  • two_pointers
• 1_binary_search
  • midpoint_discards_half
  • two_binary_searches
    • find_first_pos
      • only_when_midpoint_is_target
      • update_midpoint
      • find_last_pos
        • update_midpoint
  • update_midpoint
• URL
• editorial
  • 0_brute_force

Nodes

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

intuition
content	I've come to recognize this as a prototypical binary search problem. Sorted array, O(log(n)) time. The special extra bit here is making sure the array returns [-1,-1] if a range hasn't been found.
children	two_pass_binary_search, two_pointers

two_pointers
content	I'm guessing this solution will ultimately use the left/right pointer technique. You can solve this in about linear time by inching both sides until they converge towards the target. Based on what I've seen so far, a log time solution would involve some kind of midpoint?
parents	intuition

two_pass_binary_search
content	You can probably perform two binary searches to find the lower bound and upper bound of the target, somehow.
children	two_binary_searches (thinking about this problem correctly), find_lower_bound, find_upper_bound
parents	intuition

find_lower_bound
content	This is done based on which subarray to choose. To choose the lower bound: make sure the subarray has the range for the target. Eventually the midpoint will be the lower bound. The lower bound will always be greater than or equal to the first value of the left subarray.
children	find_upper_bound (similar)
parents	two_pass_binary_search

find_upper_bound
content	The upper bound is always going to be less than or equal two the last element in the right subarray.
parents	two_pass_binary_search, find_lower_bound

editorial
content	editorial
children	0_brute_force

0_brute_force
content	To begin, a hypothetical discussion of the brute force approach, which is a linear sweep. The first occurance is the lower bound, and the upper bound happens when the value is greater than the target or the end of the array. This approach however doesn't take advantage of the sorted nature of the array.
parents	editorial

1_binary_search
content	Approach: Binary Search, tweaked to find the first and last position of a given element
children	midpoint_discards_half (review of binary search), two_binary_searches (Try to work out this algorithm solution), update_midpoint

midpoint_discards_half
content	Given a sorted array, binary search finds the midpoint, and based on the midpoint, chooses to discard half of the array.
parents	1_binary_search

two_binary_searches
content	The solution involves using two binary searches, which pretty much how I thought this problem would be solved. The implementation though I don't feel 100% confident I'd get on the first go. Probably worth studying more in detail
children	find_first_pos
parents	two_pass_binary_search, 1_binary_search

find_first_pos
content	2 situations when an index will be the first occurance of the target in the array. 1. mid is equal to begin, which implies the first element in remaining subarray. 2. The element to the left of the index is not equal to the target being looked for (mid-1). If condition not met, keep searching the left side of array for first occurance of target.
children	only_when_midpoint_is_target (this only happens when midpoint is found to be target), update_midpoint (when nums[mid]==target), find_last_pos (similar)
parents	two_binary_searches

only_when_midpoint_is_target
content	Note that this only happens when the index is found to be target. Otherwise the midpoint update is done based on range.
parents	find_first_pos

update_midpoint
content	if nums[mid] > target, end=mid-1, discarding right subarray. if nums[mid] < target, begin=mid+1, discarding left subarray. if nums[mid]==target, determine if it is the first/last occurance
parents	find_first_pos, 1_binary_search, find_last_pos

find_last_pos
content	inverse of finding first position. 1. mid is same as end (instead of begin), which implies last elem in remaining array. 2. element to right of mid (mid + 1) is not equal to the target, meaning keep searching right.
children	update_midpoint (when nums[mid]==target)
parents	find_first_pos