Binary Search solution ```python class Solution: def findBestValue(self, A: List[int], target: int) -> int: “”” tc O(Nlg(max(A))) sc O(1) find a minimun integer x, so that sum_at_most(x) == target +-1? x range [0,max(A)]? """ n = len(A) def sum_at(x): res = 0 for a in A: if a > x:...
[Read More]
1047. Remove All Adjacent Duplicates In String
Binary Search ```python class Solution: def maxProfit(self, A: List[int], orders: int) -> int: “”” tc O(Nlg(109)) sc O(1) 1. find the minimun threashold that meet orders (> orders, not >=) 2. use the max threashold to cacucalte amount of used orders that can be sold (up to threashold +1) 3....
[Read More]
1047. Remove All Adjacent Duplicates In String
Two Pointers
```python
class Solution:
def removeDuplicates(self, s: str) -> str:
def solu1(s):
""" tc O(N) sc O(N)
main idea: stack
[Read More]
1870. Minimum Speed to Arrive on Time
class Solution: def minSpeedOnTime(self, A: List[int], hour: float) -> int: """ tc O(Nlg(sumA)) sc O(1) note, except for last trip, all the other trips takes ceiling hours to complete speed => sum(dis_i/speed) <= hours ??? range of speed hour >= 1 => max speed sum(dist) => [1,sum(dist)] !! edge case:...
[Read More]
1802. Maximum Value at a Given Index in a Bounded Array
```python class Solution: def maxValue(self, n: int, index: int, maxSum: int) -> int: “”” tc O(lg(maxSum)) sc O(1) peak range [0,maxSum-n] """ n_maxSum = maxSum - n # tc O(1) def get_arr_sum(peak,idx,n): res = 0 end1 = max(0,peak-idx) res += (peak+end1)*(peak-end1+1)//2 #1 end2 = max(0,peak - ((n-1)-idx)) res += (peak+end2)*(peak-end2+1)//2...
[Read More]