Buckets:
| tags: | |
| - notes | |
| - binary-search | |
| ### [Search in 2D Matrix](https://neetcode.io/problems/search-2d-matrix?list=neetcode150) MEDIUM | |
| 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? | |
| ![[search-in-2d-matrix.png.png]] | |
| ```python | |
| Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 10 | |
| Output: true | |
| ``` | |
| ![[search-in-2d-matrix-2.png.png]] | |
| ```python | |
| Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 15 | |
| Output: false | |
| ``` | |
| > [!info] Time and Space complexity | |
| > You should aim for a solution with `O(log(m * n))` time and `O(1)` space, where `m` is the number of rows and `n` is the number of columns in the matrix. | |
| #### Solution | |
| This problem can be solved by two methods: | |
| 1. **Finding the element in row and then in the column**: Loop over the rows to find the possible location of the target, using binary search technique. Once found, loop over the columns for that row using binary search technique. If found return `True` else return `False`. | |
| ```python | |
| class Solution: | |
| def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: | |
| ROWS, COLS = len(matrix), len(matrix[0]) | |
| if target < matrix[0][0] or target > matrix[ROWS - 1][COLS - 1]: | |
| return False | |
| row = 0 | |
| top, bottom = row, ROWS - 1 | |
| while top <= bottom: | |
| row = (top + bottom) // 2 | |
| if target < matrix[row][0]: | |
| bottom = row - 1 | |
| elif target > matrix[row][-1]: | |
| top = row + 1 | |
| else: | |
| break | |
| col = 0 | |
| left, right = col, COLS - 1 | |
| while left <= right: | |
| mid = (right + left) // 2 | |
| if target == matrix[row][mid]: | |
| return True | |
| elif target < matrix[row][mid]: | |
| right = mid - 1 | |
| elif target > matrix[row][mid]: | |
| left = mid + 1 | |
| return False | |
| ``` | |
| 2. **Considering the entire matrix as a flat list**: The matrix can be visualised as a flattened 1D sorted array because each row is sorted and every row starts after the previous ends. Using this property, binary search is applied across the entire matrix by converting the 1D mid index into 2D coordinates using `row = mid // COLS` and `col = mid % COLS`. This allows efficient comparison with the target in O(log (m × n)) time. No extra space is used, and the search continues by adjusting the binary range based on comparisons until the target is found or the range is exhausted. | |
| ```python | |
| class Solution: | |
| def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: | |
| ROWS, COLS = len(matrix), len(matrix[0]) | |
| total = ROWS * COLS | |
| start, end = 0, total - 1 | |
| while start <= end: | |
| mid = (start + end) // 2 | |
| i = mid // COLS | |
| j = mid % COLS | |
| if target == matrix[i][j]: | |
| return True | |
| elif target < matrix[i][j]: | |
| end = mid - 1 | |
| else: | |
| start = mid + 1 | |
| return False | |
| ``` | |
| ### [Koko Eating Bananas](https://neetcode.io/problems/eating-bananas?list=neetcode150) MEDIUM | |
| 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 | |
| ``` | |
| > [!info] Time and Space Complexity | |
| > You should aim for a solution with `O(nlogm)` time and `O(1)` space, where `n` is the size of the input array, and `m` is the maximum value in the array. | |
| #### Solution | |
| We start with max pile size to be the starting threshold. We calculate the mid threshold between 1 and max pile size and calculate the time taken to complete all piles. We compare the time taken with max provided time `h` and check if its valid. We continue till we have the ideal threshold. | |
| ```python | |
| class Solution: | |
| def minEatingSpeed(self, piles: List[int], h: int) -> int: | |
| start, end = 1, max(piles) | |
| threshold = max(piles) | |
| total = sum(piles) | |
| while start <= end: | |
| mid = (start + end) // 2 | |
| time = 0 | |
| for pile in piles: | |
| time += math.ceil(float(pile) / mid) | |
| if time <= h: | |
| threshold = mid | |
| end = mid - 1 | |
| else: | |
| start = mid + 1 | |
| return threshold | |
| ``` | |
| ### [Find Minimum in Rotated Sorted Array](https://neetcode.io/problems/find-minimum-in-rotated-sorted-array?list=neetcode150) MEDIUM | |
| 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 | |
| ``` | |
| > [!info] Time and Space Complexity | |
| > You should aim for a solution with `O(logn)` time and `O(1)` space, where `n` is the size of the input array. | |
| #### Solution | |
| ```python | |
| class Solution: | |
| def findMin(self, nums: List[int]) -> int: | |
| start, end = 0, len(nums) - 1 | |
| res = float("inf") | |
| while start <= end: | |
| if nums[start] < nums[end]: | |
| res = min(res, nums[start]) | |
| break | |
| mid = (start + end) // 2 | |
| res = min(res, nums[mid]) | |
| if nums[mid] < nums[end]: | |
| end = mid - 1 | |
| else: | |
| start = mid + 1 | |
| return res | |
| ``` | |
| ### [First Bad Version]() EASY | |
| You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. | |
| Suppose you have `n` versions `[1, 2, ..., n]` and you want to find out the first bad one, which causes all the following ones to be bad. | |
| You are given an API `bool isBadVersion(version)` which returns whether `version` is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API. | |
| ```java | |
| Input: n = 5, bad = 4 | |
| Output: 4 | |
| Explanation: | |
| call isBadVersion(3) -> false | |
| call isBadVersion(5) -> true | |
| call isBadVersion(4) -> true | |
| Then 4 is the first bad version. | |
| ``` | |
| #### Solution | |
| We start from the mid of the version list. If we find a version that is bad, we flag it and shrink the search space. | |
| ```python | |
| # The isBadVersion API is already defined for you. | |
| # def isBadVersion(version: int) -> bool: | |
| class Solution: | |
| def firstBadVersion(self, n: int) -> int: | |
| start, end = 1, n | |
| bad = float("inf") | |
| while start <= end: | |
| mid = (start + end) // 2 | |
| if isBadVersion(mid): | |
| bad = mid | |
| end = mid - 1 | |
| else: | |
| start = mid + 1 | |
| return bad | |
| ``` | |
Xet Storage Details
- Size:
- 8.48 kB
- Xet hash:
- 5b7bd122ff83ee267efb72fd954746502df71c328937f5b992564ed6f9105446
·
Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.