| Problem Names | Solution Writeups | Code |
|---|---|---|
| Binary Search |
While start <= end, updates with mid + 1 or mid - 1. |
|
| Search a 2D Matrix |
O((logn)2). First binary search the row first element, for < case, need to check if the next row first element >= target, if not set row_start = row_mid + 1, else search through the row_mid row. |
|
| Koko Eating Bananas |
Find min eating speed. Binary search through 1 to max(piles). Only record the min possible speed. Take not to use "long" and "double" for C++ precision issue. |
|
| Search in Rotated Sorted Array |
Binary search with modification. If mid is in left portion (nums[start] <= nums[mid]), update start when nums[mid] > target || nums[start] < target, else update end. If mid is in right portion, update start when nums[mid] > target && nums[end] <= target. |
|
| Find Min in Rotated Sorted Array |
Don't find pivot position. When we have nums[start] < nums[end], stop search and check if nums[start] is the min. Else, when nums[mid] >= nums[start], search through right portion and else search through left portion. Take note that min = min(nums[mid], min). |
|
| Time Based Key-value Store | Create a data structure of unordered_map of string as key and another map (in sorted order) with int timestamp as key and string as value, as the value of the unordered_map. Then, when looking at the timestamp, we need to ensure it is the previous nearest timestamp in the map if that timestamp is not found. | |
| Median of Two Sorted Arrays |
The idea is that we need to first calculate the position of the median if two arrays are merged, then this value tells us the size of the partition required. Then for each nums1 and nums2 array, partition according to the binary search algorithm. And then output the median according to the median position is even or odd, if is odd then it is min(Aright, Bright). If it is even, then the answer is (max(Aleft, Bleft), min(Aright, Bright)) / 2. |