Binary Search

You are given an array of **distinct** integers `nums`, sorted in ascending order, and an integer `target`. Implement a function to search for `target` within `nums`. If it exists, then return its index, otherwise, return `-1`. Your solution must run in $O(log n)$ time. **Example 1:** ```java Input: nums = [-1,0,2,4,6,8], target = 4 Output: 3 ``` **Example 2:** ```java Input: nums = [-1,0,2,4,6,8], target = 3 Output: -1 ``` **Constraints:** * `1 <= nums.length <= 10000`. * `-10000 < nums[i], target < 10000` * All the integers in `nums` are **unique**. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(logn)</code> time and <code>O(1)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Can you find an algorithm that is useful when the array is sorted? Maybe other than linear seacrh. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> The problem name is the name of the algorithm that we can use. We need to find a target value and if it does not exist in the array return <code>-1</code>. We have <code>l</code> and <code>r</code> as the boundaries of the segment of the array in which we are searching. Try building conditions to eliminate half of the search segment at each step. Maybe sorted nature of the array can be helpful. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We compare the target value with the <code>mid</code> of the segment. For example, consider the array <code>[1, 2, 3, 4, 5]</code> and <code>target = 4</code>. The <code>mid</code> value is <code>3</code>, thus, on the next iteration we search to the right of <code>mid</code>. The remaining segment is <code>[4,5]</code>. Why? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> Because the array is sorted, all elements to the left of <code>mid</code> (including <code>3</code>) are guaranteed to be smaller than the target. Therefore, we can safely eliminate that half of the array from consideration, narrowing the search to the right half and repeat this search until we find the target. </p> </details>

You are given an `m x n` 2-D integer array `matrix` and an integer `target`. * Each row in `matrix` is sorted in *non-decreasing* order. * The first integer of every row is greater than the last integer of the previous row. Return `true` if `target` exists within `matrix` or `false` otherwise. Can you write a solution that runs in `O(log(m * n))` time? **Example 1:**  ```java Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 10 Output: true ``` **Example 2:**  ```java Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 15 Output: false ``` **Constraints:** * `m == matrix.length` * `n == matrix[i].length` * `1 <= m, n <= 100` * `-10000 <= matrix[i][j], target <= 10000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(log(m * n))</code> time and <code>O(1)</code> space, where <code>m</code> is the number of rows and <code>n</code> is the number of columns in the matrix. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would be to do a linear search on the matrix. This would be an <code>O(m * n)</code> solution. Can you think of a better way? Maybe an efficient searching algorithm, as the given matrix is sorted. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use binary search, which is particularly effective when we visualize a row as a range of numbers, <code>[x, y]</code> where <code>x</code> is the first cell and <code>y</code> is the last cell of a row. Using this representation, it becomes straightforward to check if the target value falls within the range. How can you use binary search to solve the problem? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We perform a binary search on the rows to identify the row in which the target value might fall. This operation takes <code>O(logm)</code> time, where <code>m</code> is the number of rows. Now, when we find the potential row, can you find the best way to search the target in that row? The sorted nature of each row is the hint. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> Once we identify the potential row where the target might exist, we can perform a binary search on that row which acts as a one dimensional array. It takes <code>O(logn)</code> time, where <code>n</code> is the number of columns in the row. </p> </details>

You are given an integer array `piles` where `piles[i]` is the number of bananas in the `ith` pile. You are also given an integer `h`, which represents the number of hours you have to eat all the bananas. You may decide your bananas-per-hour eating rate of `k`. Each hour, you may choose a pile of bananas and eats `k` bananas from that pile. If the pile has less than `k` bananas, you may finish eating the pile but you can not eat from another pile in the same hour. Return the minimum integer `k` such that you can eat all the bananas within `h` hours. **Example 1:** ```java Input: piles = [1,4,3,2], h = 9 Output: 2 ``` Explanation: With an eating rate of 2, you can eat the bananas in 6 hours. With an eating rate of 1, you would need 10 hours to eat all the bananas (which exceeds h=9), thus the minimum eating rate is 2. **Example 2:** ```java Input: piles = [25,10,23,4], h = 4 Output: 25 ``` **Constraints:** * `1 <= piles.length <= 1,000` * `piles.length <= h <= 1,000,000` * `1 <= piles[i] <= 1,000,000,000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(nlogm)</code> time and <code>O(1)</code> space, where <code>n</code> is the size of the input array, and <code>m</code> is the maximum value in the array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Given <code>h</code> is always greater than or equal to the length of piles, can you determine the upper bound for the answer? How much time does it take Koko to eat a pile with <code>x</code> bananas? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> It takes <code>ceil(x / k)</code> time to finish the <code>x</code> pile when Koko eats at a rate of <code>k</code> bananas per hour. Our task is to determine the minimum possible value of <code>k</code>. However, we must also ensure that at this rate, <code>k</code>, Koko can finish eating all the piles within the given <code>h</code> hours. Can you now think of the upper bound for <code>k</code>? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> The upper bound for <code>k</code> is the maximum size of all the piles. Why? Because if Koko eats the largest pile in one hour, then it is straightforward that she can eat any other pile in an hour only. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> Consider <code>m</code> to be the largest pile and <code>n</code> to be the number of piles. A brute force solution would be to linearly check all values from <code>1</code> to <code>m</code> and find the minimum possible value at which Koko can complete the task. This approach would take <code>O(n * m)</code> time. Can you think of a more efficient method? Perhaps an efficient searching algorithm could help. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 5</summary> <p> Rather than linearly scanning, we can use binary search. The upper bound of <code>k</code> is <code>max(piles)</code> and since we are only dealing with positive values, the lower bound is <code>1</code>. The search space of our binary search is <code>1</code> through <code>max(piles)</code>. This allows us to find the smallest possible <code>k</code> using binary search. </p> </details>

You are given an array of length `n` which was originally sorted in ascending order. It has now been **rotated** between `1` and `n` times. For example, the array `nums = [1,2,3,4,5,6]` might become: * `[3,4,5,6,1,2]` if it was rotated `4` times. * `[1,2,3,4,5,6]` if it was rotated `6` times. Notice that rotating the array `4` times moves the last four elements of the array to the beginning. Rotating the array `6` times produces the original array. Assuming all elements in the rotated sorted array `nums` are **unique**, return the minimum element of this array. A solution that runs in `O(n)` time is trivial, can you write an algorithm that runs in `O(log n) time`? **Example 1:** ```java Input: nums = [3,4,5,6,1,2] Output: 1 ``` **Example 2:** ```java Input: nums = [4,5,0,1,2,3] Output: 0 ``` **Example 3:** ```java Input: nums = [4,5,6,7] Output: 4 ``` **Constraints:** * `1 <= nums.length <= 1000` * `-1000 <= nums[i] <= 1000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(logn)</code> time and <code>O(1)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would be to do a linear search on the array to find the minimum element. This would be an <code>O(n)</code> solution. Can you think of a better way? Maybe an efficient searching algorithm is helpful. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Given that the array is rotated after sorting, elements from the right end are moved to the left end one by one. This creates two parts of a sorted array, separated by a deflection point caused by the rotation. For example, consider the array <code>[3, 4, 1, 2]</code>. Here, the array is rotated twice, resulting in two sorted segments: <code>[3, 4]</code> and <code>[1, 2]</code>. And the minimum element will be the first element of the right segment. Can you do a binary search to find this cut? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We perform a binary search on the array with pointers <code>l</code> and <code>r</code>, which belong to two different sorted segments. For example, in <code>[3, 4, 5, 6, 1, 2, 3]</code>, <code>l = 0</code>, <code>r = 6</code>, and <code>mid = 3</code>. At least two of <code>l</code>, <code>mid</code>, and <code>r</code> will always be in the same sorted segment. Can you find conditions to eliminate one half and continue the binary search? Perhaps analyzing all possible conditions for <code>l</code>, <code>mid</code>, and <code>r</code> would help. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> There will be two conditions where <code>l</code> and <code>mid</code> will be in left sorted segment or <code>mid</code> and <code>r</code> will be in right sorted segement. If <code>l</code> and <code>mid</code> in sorted segement, then <code>nums[l] < nums[mid]</code> and the minimum element will be in the right part. If <code>mid</code> and <code>r</code> in sorted segment, then <code>nums[mid] < nums[r]</code> and the minimum element will be in the left part. After the binary search we end up finding the minimum element. </p> </details>

You are given an array of length `n` which was originally sorted in ascending order. It has now been **rotated** between `1` and `n` times. For example, the array `nums = [1,2,3,4,5,6]` might become: * `[3,4,5,6,1,2]` if it was rotated `4` times. * `[1,2,3,4,5,6]` if it was rotated `6` times. Given the rotated sorted array `nums` and an integer `target`, return the index of `target` within `nums`, or `-1` if it is not present. You may assume all elements in the sorted rotated array `nums` are **unique**, A solution that runs in `O(n)` time is trivial, can you write an algorithm that runs in `O(log n) time`? **Example 1:** ```java Input: nums = [3,4,5,6,1,2], target = 1 Output: 4 ``` **Example 2:** ```java Input: nums = [3,5,6,0,1,2], target = 4 Output: -1 ``` **Constraints:** * `1 <= nums.length <= 1000` * `-1000 <= nums[i] <= 1000` * `-1000 <= target <= 1000` * All values of `nums` are **unique**. * `nums` is an ascending array that is possibly rotated. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(logn)</code> time and <code>O(1)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would be to do a linear search on the array to find the target element. This would be an <code>O(n)</code> solution. Can you think of a better way? Maybe an efficient searching algorithm is helpful. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Given that the array is rotated after sorting, elements from the right end are moved to the left end one by one, creating two sorted segments separated by a deflection point due to the rotation. For example, consider the array <code>[3, 4, 1, 2]</code>, which is rotated twice, resulting in two sorted segments: <code>[3, 4]</code> and <code>[1, 2]</code>. In a fully sorted array, it's easy to find the target. So, if you can identify the deflection point (cut), you can perform a binary search on both segments to find the target element. Can you use binary search to find this cut? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We perform a binary search on the array with pointers <code>l</code> and <code>r</code>, which belong to two different sorted segments. For example, in <code>[3, 4, 5, 6, 1, 2, 3]</code>, <code>l = 0</code>, <code>r = 6</code>, and <code>mid = 3</code>. At least two of <code>l</code>, <code>mid</code>, and <code>r</code> will always be in the same sorted segment. Can you find conditions to eliminate one half and continue the binary search? Perhaps analyzing all possible conditions for <code>l</code>, <code>mid</code>, and <code>r</code> may help. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> There are two cases: <code>l</code> and <code>mid</code> belong to the left sorted segment, or <code>mid</code> and <code>r</code> belong to the right sorted segment. If <code>l</code> and <code>mid</code> are in the same segment, <code>nums[l] < nums[mid]</code>, so the pivot index must lie in the right part. If <code>mid</code> and <code>r</code> are in the same segment, <code>nums[mid] < nums[r]</code>, so the pivot index must lie in the left part. After the binary search, we eventually find the pivot index. Once the pivot is found, it's straightforward to select the segment where the target lies and perform a binary search on that segement to find its position. If we don't find the target, we return <code>-1</code>. </p> </details>

Implement a time-based key-value data structure that supports: * Storing multiple values for the same key at specified time stamps * Retrieving the key's value at a specified timestamp Implement the `TimeMap` class: * `TimeMap()` Initializes the object. * `void set(String key, String value, int timestamp)` Stores the key `key` with the value `value` at the given time `timestamp`. * `String get(String key, int timestamp)` Returns the most recent value of `key` if `set` was previously called on it *and* the most recent timestamp for that key `prev_timestamp` is less than or equal to the given timestamp (`prev_timestamp <= timestamp`). If there are no values, it returns `""`. Note: For all calls to `set`, the timestamps are in strictly increasing order. **Example 1:** ```java Input: ["TimeMap", "set", ["alice", "happy", 1], "get", ["alice", 1], "get", ["alice", 2], "set", ["alice", "sad", 3], "get", ["alice", 3]] Output: [null, null, "happy", "happy", null, "sad"] Explanation: TimeMap timeMap = new TimeMap(); timeMap.set("alice", "happy", 1); // store the key "alice" and value "happy" along with timestamp = 1. timeMap.get("alice", 1); // return "happy" timeMap.get("alice", 2); // return "happy", there is no value stored for timestamp 2, thus we return the value at timestamp 1. timeMap.set("alice", "sad", 3); // store the key "alice" and value "sad" along with timestamp = 3. timeMap.get("alice", 3); // return "sad" ``` **Constraints:** * `1 <= key.length, value.length <= 100` * `key` and `value` only include lowercase English letters and digits. * `1 <= timestamp <= 1000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(1)</code> time for <code>set()</code>, <code>O(logn)</code> time for <code>get()</code>, and <code>O(m * n)</code> space, where <code>n</code> is the total number of values associated with a key, and <code>m</code> is the total number of keys. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Can you think of a data structure that is useful for storing key-value pairs? Perhaps a hash-based data structure where we not only store unique elements but also associate additional information with each element? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We store key-value pairs in a hash map. In this case, we store the keys as usual, but instead of a single value, we store a list of values, each paired with its corresponding timestamp. This allows us to implement the <code>set()</code> method in <code>O(1)</code>. How can you leverage this hash map to implement the <code>get()</code> method? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> A brute force solution would involve linearly going through every value associated with the key and returning the most recent value with a timestamp less than or equal to the given timestamp. This approach has a time complexity of <code>O(n)</code> for each <code>get()</code> call. Can you think of a better way? Since the timestamps in the value list are sorted in ascending order by default, maybe an efficient searching algorithm could help. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We can use binary search because the timestamps in the values list are sorted in ascending order. This makes it straightforward to find the value with the most recent timestamp that is less than or equal to the given timestamp. </p> </details>

You are given two integer arrays `nums1` and `nums2` of size `m` and `n` respectively, where each is sorted in ascending order. Return the [median](https://en.wikipedia.org/wiki/Median) value among all elements of the two arrays. Your solution must run in $O(log (m+n))$ time. **Example 1:** ```java Input: nums1 = [1,2], nums2 = [3] Output: 2.0 ``` Explanation: Among `[1, 2, 3]` the median is 2. **Example 2:** ```java Input: nums1 = [1,3], nums2 = [2,4] Output: 2.5 ``` Explanation: Among `[1, 2, 3, 4]` the median is (2 + 3) / 2 = 2.5. **Constraints:** * `nums1.length == m` * `nums2.length == n` * `0 <= m <= 1000` * `0 <= n <= 1000` * `-10^6 <= nums1[i], nums2[i] <= 10^6` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(log(min(n, m)))</code> time and <code>O(1)</code> space, where <code>n</code> is the size of <code>nums1</code> and <code>m</code> is the size of <code>nums2</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would be to create a new array by merging elements from both arrays, then sorting it and returning the median. This would be an <code>O(n + m)</code> solution. Can you think of a better way? Maybe you can use the criteria of both the arrays being sorted in ascending order. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Suppose we merged both arrays. Then, we would have <code>half = (m + n) / 2</code> elements to the left of the median. So, without merging, is there any way to use this information to find the median? You can leverage the fact that the arrays are sorted. Consider the smaller array between the two and use binary search to find the correct partition between the two arrays, which will allow you to directly find the median without fully merging the arrays. How will you implement this? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We will always try to keep array <code>A</code> smaller and interchange it with array <code>B</code> if <code>len(A) > len(B)</code>. Now, we perform binary search on the number of elements we will choose from array <code>A</code>. It is straightforward that when we choose <code>x</code> elements from array <code>A</code>, we have to choose <code>half - x</code> elements from array <code>B</code>. But we should also ensure that this partition is valid. How can we do this? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> When we do a partition for both arrays, we should ensure that the maximum elements from the left partitions of both arrays are smaller than or equal to the minimum elements of the right partitions of both the arrays. This will ensure that the partition is valid, and we can then find the median. We can find the min or max of these partitions in <code>O(1)</code> as these partitions are sorted in ascending order. Why does this work? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 5</summary> <p> For example, consider the arrays <code>A = [1, 2, 3, 4, 5]</code> and <code>B = [1, 2, 3, 4, 5, 6, 7, 8]</code>. When we select <code>x = 2</code>, we take <code>4</code> elements from array <code>B</code>. However, this partition is not valid because value <code>4</code> from the left partition of array <code>B</code> is greater than the value <code>3</code> from the right partition of array <code>A</code>. So, we should try to take more elements from array <code>A</code> to make the partition valid. Binary search will eventually help us find a valid partition. </p> </details>