• Binary search:

  1 Sqrt of x

  mid = l+r/2
  if mid*mid == x:
    return mid
  if mid*mid < x:
    l = mid+1
    ans = mid
  else:
    r = mid-1
  

  2 Search for a Range

    while lower_bound < upper_bound:
      mid = (upper_bound+lower_bound)/2
        if B <= A[mid]:
          upper_bound = mid
        else:
          lower_bound= mid+1
    l = lower_bound
    while  lower_bound < upper_bound:
      mid = (lower_bound+upper_bound)/2+1
        if B >= A[mid]:
          lower_bound = mid
        else:
          upper_bound = mid-1
    u = upper_bound
  

• Given a sorted array and a number x, find the pair in array whose sum is closest to x

        while r > l: 
        # Check if this pair is closer than the  
        # closest pair so far 
        if abs(arr[l] + arr[r] - x) < diff: 
            res_l = l 
            res_r = r 
            diff = abs(arr[l] + arr[r] - x) 
      
        if arr[l] + arr[r] > x: 
        # If this pair has more sum, move to  
        # smaller values. 
            r -= 1
        else: 
        # Move to larger values 
            l += 1
  

  Find Smallest Letter Greater Than Target

    while lo < hi {
      int mi = lo + (hi - lo) / 2;
      if (letters[mi] <= target) lo = mi + 1;
      else hi = mi;
    return letters[lo % letters.length]
  

  Find peak element in array

  Find Minium in rotated sorted array[Duplicates doesnt exist in array]

          # If the list has just one element then return that element.
        if len(nums) == 1:
            return nums[0]
  
        # left pointer
        left = 0
        # right pointer
        right = len(nums) - 1
  
        # if the last element is greater than the first element then there is no rotation.
        # e.g. 1 < 2 < 3 < 4 < 5 < 7. Already sorted array.
        # Hence the smallest element is first element. A[0]
        if nums[right] > nums[0]:
            return nums[0]
  
        # Binary search way
        while right >= left:
            # Find the mid element
            mid = left + (right - left) / 2
            # if the mid element is greater than its next element then mid+1 element is the smallest
            # This point would be the point of change. From higher to lower value.
            if nums[mid] > nums[mid + 1]:
                return nums[mid + 1]
            # if the mid element is lesser than its previous element then mid element is the smallest
              if nums[mid - 1] > nums[mid]:
                return nums[mid]
  
            # if the mid elements value is greater than the 0th element this means
            # the least value is still somewhere to the right as we are still dealing with elements greater than nums[0]
            if nums[mid] > nums[0]:
                left = mid + 1
            # if nums[0] is greater than the mid value then this means the smallest value is somewhere to the left
            else:
                right = mid - 1
  

  Find minimum in rotated sorted array[Duplicates exist in array]

    # the least value is still somewhere to the right as we are still dealing with elements greater than nums[0]
    if nums[mid] >= nums[0]:
        left = mid + 1
    # if nums[0] is greater than the mid value then this means the smallest value is somewhere to the left
    else:
        right = mid - 1
  

  Find k closest number to a number in an array

• 1. If the ques says in any case the first node will be removed or reversed, use a p0 dummy pointer at the start
• 2 If the quest says after every n perform this. Move the dummy pointer n times and rest pointers accordingly.
• 3 If the question always check for the dummy pointer for next and next.next and update rest pointer accordingly otherwise if you check the next next pointer of others:
• the operation for the last node will be missed.
• 1. Reverse of any time even in the middle or deletion of any time will require should use dummy for handling edge case.
• 5 Always take care of the connections which you havent removed. The can be used to access others
• 1. dummy.next is the head for most cases.
• 1. The very first step should be saving the next pointer of the node before making changes to the node (IN LOOP) no matter if it saved outside the loop

DFS magic spell:

• 1]push to stack,
• 2] pop top ,
• 3] retrieve unvisited neighbours of top, push them to stack,
• 4] repeat 1,2,3 while stack not empty.

1. If we need to keep care of parents then just pass root.left and root.right in recursive call and assign it to root.left and root.right only

class Solution:

    def __init__(self):
        
        self.li = []
        self.lis = []
    
    def dfs(self, root, sum):
        if not root:
            return
        self.lis.append(root.val)
        print(self.lis)
        if not root.left and not root.right and sum == root.val:
            print(root.val)
            self.li.append(list(self.lis))
        else:
            self.dfs(root.left, sum-root.val)
            self.dfs(root.right, sum-root.val)
        self.lis.pop()
        return
        
    def pathSum(self, root, sum):
        
        if not root:
            return []
        self.dfs(root, sum)
        
        return self.li
        
        ```python 
```python    
class Solution:
    
    def inorderTraversal(self, root):
        
        result, stack, visited = [], [(root, False)], {} 
        
        if not root:
            return None
        
        while stack:
            val = stack.pop()
            if val.val in visited and visited[val.val] == True:
                result.append(val.val)
                # visited[val.val] = False
                continue
            if not val.left and not val.right:
                result.append(val.val)
                continue
            visited[val.val] = True
            if val.right:
                stack.append(val.right)
            stack.append(val)
            if val.left:
                stack.append(val.left)

        return result
```python

1. LRU

Keypoints:

Whenever you break a connection from one place make sure the rest of the connections remain intact in old place and new place. IN case of put:

• First delete the entry if it already exists _ Otherwise for all cases add the entry at the starting. _ If nothing exists already and cache side exceeds limit aftering the new entry, remove from the end (the last recent entry) In case of get:
• Add the entry to be get at the starting.
• Add function: If new entry simply add at the staring, if old entry then do handling for the connections of the old place to remain intact and then the usual add at the start.

python```


array: 
- arr = list(map(int, input().rstrip().split()))

numCourse = 4, prerequistites = [[1, 0], [0, 2],[3, 0]]

g = [[1, 3], []. [0]] outdegree = [1,1,0,1]

bfs = 2

for i in bfs: for j in G[i]: outdegree[j]--

Python code to demonstrate the working of

bisect(), bisect_left() and bisect_right()

importing "bisect" for bisection operations

import bisect 

# initializing list 
li = [1, 3, 4, 4, 4, 6, 7] 

# using bisect() to find index to insert new element 
# returns 5 ( right most possible index ) 
print ("The rightmost index to insert, so list remains sorted is : ", end="") 
print (bisect.bisect(li, 4)) 

# using bisect_left() to find index to insert new element 
# returns 2 ( left most possible index ) 
print ("The leftmost index to insert, so list remains sorted is : ", end="") 
print (bisect.bisect_left(li, 4)) 

# using bisect_right() to find index to insert new element 
# returns 4 ( right most possible index ) 
print ("The rightmost index to insert, so list remains sorted is : ", end="") 
print (bisect.bisect_right(li, 4, 0, 4))