Binary Search Flashcards
- Binary Search
Solved
Easy
Topics
Companies
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
Constraints:
1 <= nums.length <= 104
-104 < nums[i], target < 104
All the integers in nums are unique.
nums is sorted in ascending order.
https://leetcode.com/problems/binary-search/
class Solution(object):
def search(self, nums, target):
“””
:type nums: List[int]
:type target: int
:rtype: int
“””
l = 0
r = len(nums) - 1
while l<=r:
midx = l + (r-l)//2
mid = nums[midx]
left = nums[l]
right = nums[r]
if mid == target:
return midx
elif target > mid:
l = midx + 1
else:
r = midx - 1
return -1
- Search a 2D Matrix
Solved
Medium
Amazon Facebook
You are given an m x n integer matrix matrix with the following two properties:
Each row is sorted in non-decreasing order.
The first integer of each row is greater than the last integer of the previous row.
Given an integer target, return true if target is in matrix or false otherwise.
You must write a solution in O(log(m * n)) time complexity.
Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
https://leetcode.com/problems/search-a-2d-matrix/description/
each index in flat corresponds to [idx//cols][idx%cols] just to normal binary search
def searchMatrix(self, matrix, target):
“””
:type matrix: List[List[int]]
:type target: int
:rtype: bool
“””
# Bin search to find row
ROWS, COLS = len(matrix), len(matrix[0])
top, bot = 0, ROWS - 1
while top <= bot:
mid = top + ((bot-top)//2)
if matrix[mid][0] > target:
bot = mid - 1
elif matrix[mid][-1] < target:
top = mid + 1
else:
break
if not (top <= bot):
return False
row = mid
left, right = 0, COLS-1
while left <= right:
mid = left + ((right - left)//2)
if matrix[row][mid] > target:
right = mid-1
elif matrix[row][mid] < target:
left = mid + 1
else:
return True
return False
trick is to remember matrix flat goes from 0 to row * col - 1
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m = len(matrix)
if m == 0:
return False
n = len(matrix[0])
# binary search
left, right = 0, m * n - 1
while left <= right:
pivot_idx = (left + right) // 2
pivot_element = matrix[pivot_idx // n][pivot_idx % n]
if target == pivot_element:
return True
else:
if target < pivot_element:
right = pivot_idx - 1
else:
left = pivot_idx + 1
return False
- Koko Eating Bananas
Solved
Medium
Topics
Companies DoorDash Amazon
Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.
Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.
Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.
Return the minimum integer k such that she can eat all the bananas within h hours.
Example 1:
Input: piles = [3,6,7,11], h = 8
Output: 4
Example 2:
Input: piles = [30,11,23,4,20], h = 5
Output: 30
Example 3:
Input: piles = [30,11,23,4,20], h = 6
Output: 23
Constraints:
1 <= piles.length <= 104
piles.length <= h <= 109
1 <= piles[i] <= 109
https://leetcode.com/problems/koko-eating-bananas/description/
key point here, we want the slowest valid value which means we want the maximum of the left half of the range that is why we send the possible valid case of hours = h to the left side since we always increment the minimum value to get mid. If we find possible solution on the left side we will mark that as max. tldr the max value on the left side will be our likely solution.
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
minspeed = 1
maxspeed = max(piles)
while minspeed < maxspeed:
midspeed = minspeed + (maxspeed - minspeed)//2
hours = sum(math.ceil(pile/midspeed) for pile in piles)
if hours <= h:
maxspeed = midspeed
else:
minspeed = midspeed + 1
return minspeed
- Find Minimum in Rotated Sorted Array
Solved
Medium
Topics
Companies
Hint
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.
Constraints:
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All the integers of nums are unique.
nums is sorted and rotated between 1 and n times.
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
key is that as long as mid is less than right we know that the largest number has not over taken the middle point thus the smallest must be to the left of mid
class Solution:
def findMin(self, nums: List[int]) -> int:
left = 0
right = len(nums) - 1
while left < right:
mid = left + (right - left)//2
if nums[mid] < nums[right]:
right = mid
else:
left = mid + 1
return nums[left]
- Search in Rotated Sorted Array
Solved
Medium
Topics
Companies Amazon Facebook
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3:
Input: nums = [1], target = 0
Output: -1
Constraints:
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-104 <= target <= 104
https://leetcode.com/problems/search-in-rotated-sorted-array/description/
trick is to recognize and find what part of rotated array is sorted , if number lies within that or not. We check if left is sorted or right is sorted. (from mid)
class Solution:
def search(self, nums: List[int], target: int) -> int:
lidx = 0
ridx = len(nums) - 1
while lidx <= ridx:
midx = lidx + (ridx - lidx)//2
left, right, mid = nums[lidx], nums[ridx], nums[midx]
if target == mid:
return midx
if left <= mid:
if target >= left and target < mid:
ridx = midx - 1
else:
lidx = midx + 1
else:
if target > mid and target <= right:
lidx = midx + 1
else:
ridx = midx - 1
return -1
- Time Based Key-Value Store
Solved
Medium
Topics
Companies
Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key’s value at a certain timestamp.
Implement the TimeMap class:
TimeMap() Initializes the object of the data structure.
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 a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns “”.
Example 1:
Input
[“TimeMap”, “set”, “get”, “get”, “set”, “get”, “get”]
[[], [“foo”, “bar”, 1], [“foo”, 1], [“foo”, 3], [“foo”, “bar2”, 4], [“foo”, 4], [“foo”, 5]]
Output
[null, null, “bar”, “bar”, null, “bar2”, “bar2”]
Explanation
TimeMap timeMap = new TimeMap();
timeMap.set(“foo”, “bar”, 1); // store the key “foo” and value “bar” along with timestamp = 1.
timeMap.get(“foo”, 1); // return “bar”
timeMap.get(“foo”, 3); // return “bar”, since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is “bar”.
timeMap.set(“foo”, “bar2”, 4); // store the key “foo” and value “bar2” along with timestamp = 4.
timeMap.get(“foo”, 4); // return “bar2”
timeMap.get(“foo”, 5); // return “bar2”
Constraints:
1 <= key.length, value.length <= 100
key and value consist of lowercase English letters and digits.
1 <= timestamp <= 107
All the timestamps timestamp of set are strictly increasing.
At most 2 * 105 calls will be made to set and get.
https://leetcode.com/problems/time-based-key-value-store/description/
Netcode answer set the result to mid each time we find timestamp >= mid
class TimeMap:
def \_\_init\_\_(self):
self.store = {}
def set(self, key: str, value: str, timestamp: int) -> None:
if key not in self.store:
self.store[key] = [] # set to empty list.
self.store[key].append([value, timestamp])
def get(self, key: str, timestamp: int) -> str:
res = "" # if not exist just return empty
values = self.store.get(key, [])
low, high = 0, len(values) - 1
while low <= high:
mid = (low + high) // 2
# values[mid] will be a pair of values and timestamps
# we only need to check timestamps (which is in incr order) hence values[mid][1]
if values[mid][1] <= timestamp:
# if equal or less than timestamp -> ans found
res = values[mid][0] # closest we've seen so far -> store in ans
low = mid + 1 # check for closer values
else:
# not allowed (acc to question)
high = mid - 1 # don't assign any result here as this is an invalid val
return res
- Median of Two Sorted Arrays
Solved
Hard
Topics
Companies: Amazon Apple Goldman Sachs
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Example 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Constraints:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
https://leetcode.com/problems/median-of-two-sorted-arrays/description/
Binary Search of min array
https://leetcode.com/problems/median-of-two-sorted-arrays/description/
do binary search on it
find smallest array
the mid will be boundary for left half of smaller array
total/2 - mid will be boundary of left half of larger array
find a valid left subarray consisting of both arrays.
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
A = nums1
B = nums2
if len(A) > len(B):
A, B = B, A
LEFT = 0
RIGHT = len(A) - 1
TOTAL = len(A) + len(B)
HALF = TOTAL // 2
while True:
AMID = LEFT + (RIGHT-LEFT)//2
BMID = HALF - (AMID + 1) - 1
ALEFT = float('-inf') if AMID < 0 else A[AMID]
ARIGHT = float('inf') if AMID+1 > len(A) - 1 else A[AMID+1]
BLEFT = float('-inf') if BMID < 0 else B[BMID]
BRIGHT = float('inf') if BMID + 1 > len(B) - 1 else B[BMID+1]
if ALEFT <= BRIGHT and BLEFT <= ARIGHT:
# Left half is valid
if TOTAL % 2 == 0:
return (max(ALEFT, BLEFT) + min(ARIGHT, BRIGHT))/2
else:
return min(ARIGHT, BRIGHT)
else:
if ALEFT > BRIGHT:
RIGHT = AMID-1
else:
LEFT = AMID + 1
- Find Peak Element
Solved
Medium
Topics
Companies Facebook
A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.
Constraints:
1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
nums[i] != nums[i + 1] for all valid i.
https://leetcode.com/problems/find-peak-element/submissions/1251732304/?envType=study-plan-v2&envId=top-interview-150
Array elements are never equal according to the problem statement.
Thus we are either ascending peak on left or right or we are at peak at any given moment.
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
l = 0
r = len(nums) - 1
while l <= r:
m = l + (r-l)//2
left = nums[m-1] if m > 0 else float(‘-inf’)
right = nums[m+1] if m < len(nums) - 1 else float(‘-inf’)
if left > nums[m]:
r = m - 1
elif right > nums[m]:
l = m + 1
else:
return m
The 2D search does the same just finds max element first in the mid column. Then do the peak finding on the row of the max element. O(mLog(n)) M is number of rows.
https://leetcode.com/problems/find-a-peak-element-ii/description/
def find_peak_2d(matrix):
def find_peak_util(matrix, start_col, end_col):
if start_col > end_col:
return None
mid_col = (start_col + end_col) // 2
max_row = 0
max_value = matrix[0][mid_col]
# Find the maximum element in the middle column
for i in range(len(matrix)):
if matrix[i][mid_col] > max_value:
max_value = matrix[i][mid_col]
max_row = i
# Check if the maximum element is a peak
left_is_bigger = mid_col > 0 and matrix[max_row][mid_col-1] > max_value
right_is_bigger = mid_col < len(matrix[0]) - 1 and matrix[max_row][mid_col+1] > max_value
if not left_is_bigger and not right_is_bigger:
return (max_row, mid_col) # Return the peak coordinates
# Recur on the side that has a bigger neighbor
if left_is_bigger:
return find_peak_util(matrix, start_col, mid_col-1)
else:
return find_peak_util(matrix, mid_col+1, end_col)
if not matrix:
return None
return find_peak_util(matrix, 0, len(matrix[0]) - 1)
- Find First and Last Position of Element in Sorted Array
Solved
Medium
Topics
Companies
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.
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Example 3:
Input: nums = [], target = 0
Output: [-1,-1]
Constraints:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums is a non-decreasing array.
-109 <= target <= 109
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150
find left first then right
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
l = 0
r = len(nums) - 1
ret = [len(nums), -1]
found = False
while l <= r:
m = l + (r-l)//2
if nums[m] == target:
ret[0] = min(ret[0], m)
r = m-1
found = True
elif nums[m] < target:
l = m+1
else:
r = m-1
l = ret[0]
r = len(nums) - 1
while l <= r :
m =l + (r-l)//2
if nums[m] == target:
ret[1] = max(ret[1], m)
l = m+1
elif nums[m] < target:
l = m+1
else:
r = m-1
return ret if found else [-1, -1]
