Binary Search / Div Conq. 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
Bisect, simpler easier
from collections import defaultdict
class TimeMap:
def \_\_init\_\_(self):
self.storage = defaultdict(list)
def set(self, key: str, value: str, timestamp: int) -> None:
self.storage[key].append((timestamp, value))
def get(self, key: str, timestamp: int) -> str:
if key not in self.storage or self.storage[key][0][0] > timestamp:
return ""
values = self.storage[key]
found_idx = bisect.bisect_right(values, timestamp, key=lambda x: x[0])
if found_idx == len(values) or found_idx !=0:
found_idx -= 1
return values[found_idx][1]
- 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.
Log(n), 10 - 15 mins.
https://leetcode.com/problems/find-peak-element
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
- Find a Peak Element II
Solved
Medium
Topics
Companies
Hint
A peak element in a 2D grid is an element that is strictly greater than all of its adjacent neighbors to the left, right, top, and bottom.
Given a 0-indexed m x n matrix mat where no two adjacent cells are equal, find any peak element mat[i][j] and return the length 2 array [i,j].
You may assume that the entire matrix is surrounded by an outer perimeter with the value -1 in each cell.
You must write an algorithm that runs in O(m log(n)) or O(n log(m)) time.
Example 1:
Input: mat = [[1,4],[3,2]]
Output: [0,1]
Explanation: Both 3 and 4 are peak elements so [1,0] and [0,1] are both acceptable answers.
Example 2:
Input: mat = [[10,20,15],[21,30,14],[7,16,32]]
Output: [1,1]
Explanation: Both 30 and 32 are peak elements so [1,1] and [2,2] are both acceptable answers.
Constraints:
m == mat.length n == mat[i].length 1 <= m, n <= 500 1 <= mat[i][j] <= 105 No two adjacent cells are equal.
Prerequisite: Find Peak - 1, nLog(m) or mLog(n)
https://leetcode.com/problems/find-a-peak-element-ii/description/
Find biggest mid column thus guranteeing that its peak element at least in this column.
check if it is peak on left right, and move left or right if it’s not, based on where the climb starts. Repeat.
*What if there is another peak element in that same row?
*
If there is one, we will find that column eventually because it will be a peak and thus biggest in it’s column.
class Solution(object):
def findPeakGrid(self, mat):
"""
:type mat: List[List[int]]
:rtype: List[int]
"""
rows = len(mat)
cols = len(mat[0])
def find_max(col):
max_row = 0
max_ele = float('-inf')
for r in range(rows):
if mat[r][col] > max_ele:
max_ele = mat[r][col]
max_row = r
return max_row
l = 0
r = cols - 1
while l <= r:
mid = l + (r-l)//2
max_row = find_max(mid)
left = -1 if mid < 1 else mat[max_row][mid-1]
right = -1 if mid > cols - 2 else mat[max_row][mid+1]
# the element mat[max_row][mid] is biggest in column, we do not need to check up down.
if mat[max_row][mid] < right:
l = mid+1
elif mat[max_row][mid] < left:
r = mid-1
else:
return [max_row, mid]
- 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
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]
- Random Pick with Weight
Medium
Companies: Facebook 2024
You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index.
You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).
For example, if w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), and the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).
Example 1:
Input
[“Solution”,”pickIndex”]
[[[1]],[]]
Output
[null,0]
Explanation
Solution solution = new Solution([1]);
solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.
Example 2:
Input
[“Solution”,”pickIndex”,”pickIndex”,”pickIndex”,”pickIndex”,”pickIndex”]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]
Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.
Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
……
and so on.
Constraints:
1 <= w.length <= 104 1 <= w[i] <= 105 pickIndex will be called at most 104 times.
https://leetcode.com/problems/random-pick-with-weight/description/
obj = Solution(w)
Do prefix sum, call random to get a frac b/w 0 and 1, multiply it by the total sum.
Find the insertion point of this number in the prefix weights and return the idx.
import random
from itertools import accumulate
class Solution(object):
def \_\_init\_\_(self, w):
"""
:type w: List[int]
"""
self.w = 0
self.prefix_sum = list(accumulate(w))
self.total_sum = sum(w)
def pickIndex(self):
"""
:rtype: int
"""
frac = random.random()
comp_sum = self.total_sum * frac
idx = bisect.bisect(self.prefix_sum, comp_sum)
return idx
Your Solution object will be instantiated and called as such:
# param_1 = obj.pickIndex()
O(n) space, O(nLog(n)) time
- Pow(x, n)
Medium
Companies: Facebook
Implement pow(x, n), which calculates x raised to the power n (i.e., xn).
Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000
Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100
Example 3:
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Constraints:
-100.0 < x < 100.0 -231 <= n <= 231-1 n is an integer. Either x is not zero or n > 0. -104 <= xn <= 104
log(n) , O(1) space 15 mins
https://leetcode.com/problems/powx-n/description/
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
powp = abs(n)
ans = 1
while powp:
if powp % 2:
powp -= 1
ans *= x
x *= x
powp //= 2
if n < 0:
return 1/ans
return ans
Why n%2 is 1 we do ans * x
2^100=(2∗2)^50
4^50=(4∗4)^25
16^25=16∗(16)^24
16^25=16∗(16∗16)^12
16∗256^12=16∗(256∗256)^6
16∗655366=16∗(65536∗65536)^3
16∗4294967296^3=16∗4294967296∗(4294967296)^2
16∗4294967296^3=16∗4294967296∗(4294967296∗4294967296)^1
2^100=1267650600228229401496703205376
- Find K Closest Elements
Solved
Medium
Topics
Companies
Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.
An integer a is closer to x than an integer b if:
|a - x| < |b - x|, or
|a - x| == |b - x| and a < b
Example 1:
Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]
Example 2:
Input: arr = [1,1,2,3,4,5], k = 4, x = -1
Output: [1,1,2,3]
Constraints:
1 <= k <= arr.length
1 <= arr.length <= 104
arr is sorted in ascending order.
-104 <= arr[i], x <= 104
https://leetcode.com/problems/find-k-closest-elements/
import bisect
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
if k == len(arr):
return arr
if x <= arr[0]:
return arr[:k]
elif x >= arr[-1]:
return arr[-k:]
insert_idx = bisect.bisect_left(arr, x)
l = insert_idx - 1
r = insert_idx
while r-l-1 < k:
if l < 0:
r+=1
continue
if r == len(arr) or abs(x-arr[l]) <= abs(x-arr[r]):
l-=1
else:
r+=1
return arr[l+1:r]
O(log(n) + k), O(1)
