<repo_name>jp-tran/dsa<file_sep>/design/rate_limiter.py
"""
Design a rate limiter that limits the number of times clients can hit an API within
a given time window.

Time complexity: amortized O(1)
Each item is only added to and removed from the queue once.

Space complexity: O(n)
where n is the number of valid hits within any given time window
"""

from collections import deque, defaultdict

class RateLimiter:
    def __init__(self, max_hits, window_seconds):
        self.queue = deque() # queue item is a tuple (client id, hit time)
        self.clients = defaultdict(int)
        self.max_hits = max_hits
        self.window = window_seconds
        
    def hit(self, client_id, current_time):
        """ If the client `client_id` has called hit() fewer than max_hit 
        times in the last window_seconds, record the hit and return True
        else return False
        """
        # pop from left end of queue
        while self.queue and self.queue[0][1] < current_time - self.window:
            earliest = self.queue.popleft()
            if self.clients[earliest[0]] == 1:
                del self.clients[earliest[0]]
            else:
              self.clients[earliest[0]] -= 1
             
        
        # append new hit to queue if it's a valid hit
        if self.clients[client_id] < self.max_hits:
            queue.append((client_id, current_time))
            self.clients[client_id] += 1
            return True
        
        return False<file_sep>/problems/cyclic_sort/find_first_positive_num.py
"""
Given an unsorted array containing numbers, find the smallest missing positive number in it.

Time complexity: O(n)
Space complexity: O(1)
"""

def solution(A):
    i = 0

    # cyclic sort all numbers A[i] in which 0 < A[i] <= len(A)
    # to their corresponding index
    while i < len(A):
        j = A[i] - 1 # index the item should be at
        if A[i] > 0 and A[i] <= len(A) and A[i] != A[j]:
            A[i], A[j] = A[j], A[i]  # swap
        else:
            i += 1
    
    # find the first number that is not at its correct index
    for idx, num in enumerate(A):
        if num != idx + 1:
            return idx + 1
    
    return len(A) + 1
<file_sep>/problems/top_k_elements/schedule_tasks.py
from collections import Counter, deque
import heapq

"""
You are given a list of tasks that need to be run, in any order, on a server. 
Each task will take one CPU interval to execute but once a task has finished, 
it has a cooling period during which it can’t be run again. If the cooling period 
for all tasks is ‘K’ intervals, find the minimum number of CPU intervals that the 
server needs to finish all tasks.

Time complexity: O(N*log(N) + N*k)
Space complexity: O(N)
"""

def schedule_tasks(tasks, k):
  num_tasks_remaining = len(tasks)

  # count the number of times each task occurs
  task_counts = Counter(tasks)

  # put all tasks and their associated counts into a max heap
  max_heap = []

  for task, freq in task_counts.items():
    heapq.heappush(max_heap, (-freq, task))

  # process tasks
  num_intervals = 0
  queue = deque()

  while num_tasks_remaining > 0:
    num_intervals += 1

    if max_heap:
      freq, task = heapq.heappop(max_heap) # O(log(N)) operation
      freq += 1
      num_tasks_remaining -= 1
    else:
      freq, task = 1, 'idle'
    
    queue.append((freq, task))

    if len(queue) == k + 1:
      next_task = queue.popleft()
      if next_task[0] < 0:
        heapq.heappush(max_heap, next_task)
    
  return num_intervals


def main():
  print("Minimum intervals needed to execute all tasks: " +
        str(schedule_tasks(['a', 'a', 'a', 'b', 'c', 'c'], 2)))
  print("Minimum intervals needed to execute all tasks: " +
        str(schedule_tasks(['a', 'b', 'a'], 3)))


main()

<file_sep>/graphs/dijkstra/dijkstra_shortest_reach.py
# implementation of dijkstra's algorithm

import math
import os
import random
import re
import sys
import heapq


def shortestReach(n: int, edges: list, s: int) -> list:
    '''
    n: number of nodes
    edges: list of lists [[beginning node, ending node, edge length], ...]
    s: starting node
    returns a list of shortest distance from s to each node, excluding s
    '''
    #create adjacency list for undirected graph
    adj_list = {i: set() for i in range(1, n+1)}
    for begin, end, length in edges:
        adj_list[begin].add((end, length))
        adj_list[end].add((begin, length))

    queue = [(0, s)] #list of tuples that will be used as a min-heap for Dijkstra's greedy score
    dist = {i: float('inf') for i in range(1, n+1)} #dict of shortest distance to each node
    dist[s] = 0
    explored = {i: False for i in range(1, n+1)} #dict of explored state for each node

    #loop through priority queue until it's empty
    while queue:
        cur_dist, cur_node = heapq.heappop(queue)
        if explored[cur_node]: continue
        explored[cur_node] = True
        for adj_node, length in adj_list[cur_node]:
            if not explored[adj_node]:
                dijkstra_gs = cur_dist + length #dijkstra's greedy score
                if dijkstra_gs < dist[adj_node]:
                    dist[adj_node] = dijkstra_gs
                    heapq.heappush(queue, (dijkstra_gs, adj_node))

    #give all unexplored nodes a distance of -1
    for node_num, state in explored.items():
        if state == False:
            dist[node_num] = -1

    #delete starting node distance from dictionary
    del dist[s]

    return list(dist.values())


if __name__ == '__main__':
    with open('dijkstra_input.txt', 'r') as input_f:
        t = int(input_f.readline())

        for t_itr in range(t):
            nm = input_f.readline().split()

            n = int(nm[0])

            m = int(nm[1])

            edges = []

            for _ in range(m):
                edges.append(list(map(int, input_f.readline().rstrip().split())))

            s = int(input_f.readline())

            result = shortestReach(n, edges, s)

            print(' '.join(map(str, result)))
            # print('\n')
<file_sep>/problems/monotonic_stack_and_queue/sliding_window_maximum.py
"""
You are given an array of integers nums, there is a sliding window of 
size k which is moving from the very left of the array to the very right.
Find the maximum element in the window each time it slides.

Time complexity: O(n)
Space complexity: O(k) - not counting "ans" array
"""

from collections import deque

class MonotonicQueue:
    def __init__(self):
        self.queue = deque() # monotonic decreasing queue
    
    def push(self, n):
        while self.queue and self.queue[-1] < n:
            self.queue.pop()
        self.queue.append(n)
    
    def get_max(self):
        return self.queue[0]
    
    def popleft(self, n):
        if self.queue[0] == n:
            self.queue.popleft()

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans = []
        queue = MonotonicQueue() # maintain monotonic decreasing queue
        
        for i, num in enumerate(nums):
            if i < k - 1:
                queue.push(num)
            else:
                queue.push(num)
                ans.append(queue.get_max())
                queue.popleft(nums[i-k+1])
        
        return ans
    <file_sep>/sorting/mergesort/merge_sort_lilnked_list.py
# Top-down implementation of merge sort for a singly-linked list
# O(n log(n)) time, where n is the number of nodes
# O(log(n)) space for the recursive call stack

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        mid = self.getMid(head) # find the middle node
        left = self.sortList(head) # sort list on left side
        right = self.sortList(mid) # sort list on right side
        return self.mergeSortedLists(left, right)
        
    def getMid(self, node):
        # assume input list has at least 2 nodes
        # "fast" pointer advances twice as fast as "slow" pointer
        slow = None
        fast = node
        while fast and fast.next:
            slow = node if slow is None else slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None # break the pointer pointing to the middle node
        return mid
    
    def mergeSortedLists(self, node1, node2):
        head = ListNode()
        node = head
        
        # iteratively redirect pointers to create one sorted list
        # until one list is completely traversed
        while node1 and node2:
            if node1.val <= node2.val:
                node.next = node1
                node1 = node1.next
            elif node1.val > node2.val:
                node.next = node2
                node2 = node2.next
            node = node.next
        
        # point to the nodes of the remaining list
        if node1:
            node.next = node1
        elif node2:
            node.next = node2
        return head.next<file_sep>/datastructures/disjoint_sets.py
from collections import defaultdict

### for m operations and n nodes, time complexity is O(m alpha(n))
### for practical purposes, O(alpha(n)) is constant, so final complexity is O(m)

class Node:
    def __init__(self, value, parent = None, rank = 0):
        self.val = value
        self.parent = parent
        self.rank = rank

class DisjointSet:
    def __init__(self):
        self.hashtable = {}
    
    def makeSet(self, val):
        """Create a set with only one element."""
        node = Node(val)
        node.parent = node
        self.hashtable[val] = node
        
    def find(self, node):
        """Find uppermost ancestor of node using path compression."""
        if node.parent == node:
            return node
        node.parent = self.find(node.parent)
        return node.parent
        
    def union(self, val1, val2):
        """Union of two sets by rank.
        Returns true if val1 and val2 are in different sets before the union
        """
        if val1 not in self.hashtable:
            self.makeSet(val1)
        if val2 not in self.hashtable:
            self.makeSet(val2)
        node1 = self.hashtable[val1]
        node2 = self.hashtable[val2]
        parent1 = self.find(node1)
        parent2 = self.find(node2)
        
        # if they are part of the same set
        if parent1.val == parent2.val:
            return False
        # else the node with the higher rank becomes the parent of the other node
        elif parent1.rank < parent2.rank:
            parent1.parent = parent2
        elif parent1.rank > parent2.rank:
            parent2.parent = parent1
        else:
            parent1.parent = parent2
            parent2.rank += 1
        return True

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        ds = DisjointSet()
        for u, v in edges:
            are_in_same_set = not ds.union(u, v)
            # if nodes of an edge are in the same set before union, 
            # the edge is redundant
            if are_in_same_set:
                return [u, v]
                <file_sep>/problems/k-way-merge/merge_k_sorted_lists.py
from __future__ import print_function
import heapq

"""
Given an array of 'K' sorted LinkedLists, merge them into one sorted list.

Time complexity: O(N * log(K)), where N is the total number of elements
and K is the number of lists

Space complexity: O(K) for min-heap
"""

class ListNode:
  def __init__(self, value):
    self.value = value
    self.next = None

  # used by heapq to compare two nodes
  def __lt__(self, other):
    return self.value < other.value


def merge_lists(lists):
  resultHead = ListNode(0)

  min_heap = [head for head in lists] # assume all head nodes are valid nodes
  heapq.heapify(min_heap)
  curr = resultHead

  while min_heap:
    smallest = heapq.heappop(min_heap) # pop the smallest node
    if smallest.next:
      # heap push next node from the same list as the one that was popped
      heapq.heappush(min_heap, smallest.next)
    curr.next = smallest
    curr = curr.next

  return resultHead.next


def main():
  l1 = ListNode(2)
  l1.next = ListNode(6)
  l1.next.next = ListNode(8)

  l2 = ListNode(3)
  l2.next = ListNode(6)
  l2.next.next = ListNode(7)

  l3 = ListNode(1)
  l3.next = ListNode(3)
  l3.next.next = ListNode(4)

  result = merge_lists([l1, l2, l3])
  print("Here are the elements form the merged list: ", end='')
  while result != None:
    print(str(result.value) + " ", end='')
    result = result.next


main()<file_sep>/sorting/mergesort/merge_sort_custom_comparator.py
 class Solution:
   def mergeSort(self, nums):
      if len(nums) <= 1:
          return
      mid = len(nums) // 2
      left = nums[:mid]
      right = nums[mid:]
      self.mergeSort(left)
      self.mergeSort(right)
      self.merge(nums, left, right)
  
  def merge(self, nums, left, right):
      l = r = k = 0
      while l < len(left) and r < len(right):
          if self.compare(left[l], right[r]):
              nums[k] = left[l]
              l += 1
          else:
              nums[k] = right[r]
              r += 1
          k += 1
      
      while l < len(left):
          nums[k] = left[l]
          l += 1
          k += 1
      
      while r < len(right):
          nums[k] = right[r]
          r += 1
          k += 1

  
  def compare(self, n1, n2):
    # comparator function used in LC problem 179: Largest Number
    # e.g. return true if n1 = '34' and n2 = '3'
      return str(n1) + str(n2) > str(n2) + str(n1)<file_sep>/problems/merging_intervals/minimum_meeting_rooms.py
"""
Given a list of intervals representing the start and end time of 'n' meetings, 
find the minimum number of rooms required to hold all the meetings.

Time complexity: O(n*log(n))
    - sorting takes O(n*log(n))
    - iterating through sorted meetings, we may do up to 
    two log(n) operations per meeting
Space complexity: O(n)
    - sorting takes O(n)
    - min heap may grow to size O(n)
"""

import heapq

class Meeting:
  def __init__(self, start, end):
    self.start = start
    self.end = end
  
  def __lt__(self, other):
    return self.end < other.end

def min_meeting_rooms(meetings):
  if not meetings:
    return 0

  # sort by meeting start time
  meetings.sort(key=lambda x: x.start)

  # the min number of rooms required is the max number of rooms used
  # at any given time
  num_rooms = 0

  # maintain a min heap sorted by meeting end time
  # size of min heap at any given time will be the number of meetings
  # happening at that time
  min_heap = []
  
  for i in range(len(meetings)):
    meeting = meetings[i]
    while min_heap and min_heap[0].end <= meeting.start:
      heapq.heappop(min_heap)
    heapq.heappush(min_heap, meeting)
    num_rooms = max(num_rooms, len(min_heap))
  
  return num_rooms

def main():
  print("Minimum meeting rooms required: " + str(min_meeting_rooms(
    [Meeting(4, 5), Meeting(2, 3), Meeting(2, 4), Meeting(3, 5)]))) # prints 2
  print("Minimum meeting rooms required: " +
        str(min_meeting_rooms([Meeting(1, 4), Meeting(2, 5), Meeting(7, 9)]))) # prints 2 
  print("Minimum meeting rooms required: " +
        str(min_meeting_rooms([Meeting(6, 7), Meeting(2, 4), Meeting(8, 12)]))) # prints 1
  print("Minimum meeting rooms required: " +
        str(min_meeting_rooms([Meeting(1, 4), Meeting(2, 3), Meeting(3, 6)]))) # prints 2
  print("Minimum meeting rooms required: " + str(min_meeting_rooms(
    [Meeting(4, 5), Meeting(2, 3), Meeting(2, 4), Meeting(3, 5)]))) # prints 2


main()
<file_sep>/bit-manipulation/three_number_bit_manip.py
"""
Given a, b, and c, return d such that
For each bit of c: if the bit is a 1, choose the corresponding bit from a.  
If it's a 0, choose the corresponding bit from b.
"""


def select(a, b, c):
    # Truth tables:
    
    # c a a1
    # 0 0  0
    # 0 1  0
    # 1 0  0
    # 1 1  1
    # c and a
    
    # c b b1
    # 0 0 0
    # 0 1 1
    # 1 0 0
    # 1 1 0
    #
    # (not c) and a
    
    

    # a1 = a0aaa0
    # b1 = 0b000b
    #a1|b1=abaaab

    return (c & a) | (~c & b) <file_sep>/problems/dynamic_programming/longest_common_subsequence.py
"""
Given two strings text1 and text2, return the length of their longest common subsequence. 
If there is no common subsequence, return 0.

Time Complexity: O(m*n)
Space Complexity: O(m*n)

In general, we have 2 choices when comparing a letter from str1 and another letter from str2:
1. If the current letters match, the answer is 1 + lcs(rest of str1, rest of str2). 

2. If the current letters don't match, the answer is 
max(lcs(exclude current letter of str1), lcs(exclude current letter of str2))
"""

def lcs(word1, word2):
  # top down approach
  memo = [[-1]*len(word2) for _ in range(len(word1))]
  ans = top_down(memo, word1, word2, 0, 0)

  #bottom up approach
  ans = bottom_up(word1, word2)

  return ans

## Top-down approach
def top_down(dp, word1, word2, i, j):
  # base case when either index is out of bounds
  if (i == len(word1) or j == len(word2)):
    return 0
  
  # if the answer is already memoized
  if dp[i][j] > -1:
    return dp[i][j]
  
  # if curr letters are the same, 
  # find the lcs given the rest of word 1 and the rest of word 2
  if (word1[i] == word2[j]):
    top_down = 1 + top_down(dp, word1, word2, i+1, j+1)
  else:
    option1 = top_down(dp, word1, word2, i, j+1) # include curr letter of word1, exclude curr letter of word2
    option2 = top_down(dp, word1, word2, i+1, j) # exclude curr letter of word1, include curr letter of word2
    top_down = max(option1, option2)
  
  dp[i][j] = top_down
  return top_down

def bottom_up(word1, word2):
  # pad left column and top row with zeros
  dp = [[0]*(len(word2)+1) for _ in range(len(word1)+1)]

  for i in range(1, len(word1) + 1):
    for j in range(1, len(word2) + 1):
      if (word1[i-1] == word2[j-1]):
        # dp[i-1][j-1] represents the lcs(word1[:i], word2[:j])
        # (i.e. exclude curr letter of word1, exclude curr letter of word2)

        # +1 because the current letters match
        dp[i][j] = 1 + dp[i-1][j-1] 
      else:
        # dp[i-1][j] represents lcs(word1[:i], word2[:j+1]) 
        # (i.e. exclude curr letter of word1, include curr letter of word2)

        # dp[i][j-1] represents lcs(word1[:i+1], word2[:j]) 
        # (i.e. include curr letter of word1, exclude curr letter of word2)
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  return dp[-1][-1]<file_sep>/problems/subsets/permutations.py
from collections import deque

"""
BFS-like approach to generating permutations
Generates each "node" by inserting at different positions

Time complexity: O(N ∗ N!)
There are N! permutations. At each iteration, we insert a new number in each of the
current permutations, which take O(N) time.

Space complexity: O(N ∗ N!)
There are N! permutations, each containing N elements.
"""

def find_permutations(nums):
  numsLength = len(nums)
  result = []
  permutations = deque() 
  permutations.append([]) # initialize queue with root node

  for currentNumber in nums:
    # we will take all existing permutations and add the current number to create new permutations
    n = len(permutations) # get size of current level
    for _ in range(n): # iterate through all nodes at current level
      oldPermutation = permutations.popleft()
      # create a new permutation by adding the current number at every position
      
      for j in range(len(oldPermutation)+1):
        newPermutation = list(oldPermutation)
        newPermutation.insert(j, currentNumber)

        # decide if we should append current node's children to queue
        if len(newPermutation) == numsLength:
          result.append(newPermutation)
        else:
          permutations.append(newPermutation)

  return result


def main():
  print("Here are all the permutations: " + str(find_permutations([1, 3, 5])))


main()
<file_sep>/searching/binary_search.py
""" Standard Binary Search """
def binary_search(nums: List[int], target: int) -> int:
  l = 0
  r = len(nums) - 1
  while l <= r:
    mid = (l + r) // 2
    if nums[mid] == target:
      return mid
    elif target < nums[mid]:
      r = mid - 1
    elif nums[mid] < target:
      l = mid + 1
  return -1

""" 
Modified binary search
While loop collapses window to 1 element using while (lo < hi)
and either lo = mid or high = mid

Set lo = mid + 1 if the target can never be at index mid 
when lo = mid + 1 is triggered. 
In the example below, peak_idx can never be mid when the slope is increasing.
"""
def search_bitonic_array(arr, key):
  # find the peak index
  lo = 0
  hi = len(arr) - 1
  while (lo < hi):
    mid = (hi + lo) // 2
    is_increasing = arr[mid] < arr[mid+1]
    if is_increasing:
      # mid can never be the peak when is_increasing, so we can safely set low = mid +1
      lo = mid + 1 
    else:
      hi = mid
  
  peak_idx = lo

  return peak_idx

""" Binary Search for a Range of Numbers """
class Solution:
  def searchRange(self, nums: List[int], target: int) -> List[int]:
    # binary search for target
    def bs(nums, target, searching_left):
      l = 0
      r = len(nums) # allows while loop to run even if array only has one entry
      # we want to run loop to put r past its actual position
      # outside the function we always subtract 1 from r
      while l < r:
        mid = (l + r) // 2
        if nums[mid] > target or (searching_left and nums[mid] == target):
          r = mid
        else:
          l = mid + 1 # need to add 1 because mid value is floored (without +1 we could be stuck in inf loop)
      return l
    
    if not nums:
      return [-1, -1]
    
    #search for leftmost/starting position
    starting = bs(nums, target, True)
    
    #check that leftmost index is our target
    if starting == len(nums) or nums[starting] != target:
      return [-1, -1]
    
    #search for rightmost/ending position
    ending = bs(nums, target, False) - 1
    
    return [starting, ending]<file_sep>/problems/merging_intervals/free_time.py
"""
For 'K' employees, we are given a list of intervals representing each employee’s working hours. 
Our goal is to determine if there is a free interval which is common to all employees. 
You can assume that each list of employee working hours is sorted on the start time.

Time complexity: O(n*log(k))
    where n is the total number of intervals, and k is the total number of employees

Space complexity: O(n)
    note that this could be improved to O(k) by appending to results inside of the while loop
"""


from __future__ import print_function
import heapq

class Interval:
    def __init__(self, start, end):
        self.start = start
        self.end = end

    def print_interval(self):
        print("[" + str(self.start) + ", " + str(self.end) + "]", end='')

    def __lt__(self, other):
        if self.start < other.start:
            return True
        else:
            return False

class EmployeeInterval:
    def __init__(self, interval, employee_idx, interval_idx):
        self.interval = interval
        self.employee_idx = employee_idx
        self.interval_idx = interval_idx
    
    def __lt__(self, other):
        return self.interval.start < other.interval.start

def find_employee_free_time(schedule):
    result = []

    # k-way merge 
    intervals = []
    heap = []

    # initialize heap
    for employee_idx, times in enumerate(schedule):
        heap.append(EmployeeInterval(times[0], employee_idx, 0))
    
    heapq.heapify(heap)

    # add all heap items to the intervals list, sorted by start time
    while heap:
        employee_interval = heapq.heappop(heap)
        intervals.append(employee_interval.interval)

        employee_idx = employee_interval.employee_idx
        interval_idx = employee_interval.interval_idx
        work_times = schedule[employee_idx]
        if interval_idx + 1 < len(work_times):
            nxt = EmployeeInterval(work_times[interval_idx + 1], employee_idx, interval_idx + 1)
            heapq.heappush(heap, nxt)

    # determine free intervals (to save memory, this could be done inside the while loop above)
    prev_end = intervals[0].end
    for i in range(1, len(intervals)):
        interval = intervals[i]
        if interval.start <= prev_end:
            prev_end = max(prev_end, interval.end)
        else:
            result.append(Interval(prev_end, interval.start))
            prev_end = interval.end

    return result


def main():

    # result = [3, 5]
    input = [[Interval(1, 3), Interval(5, 6)], [
        Interval(2, 3), Interval(6, 8)]]
    print("Free intervals: ", end='')
    for interval in find_employee_free_time(input):
        interval.print_interval()
    print()

    # result = [4,6], [8,9]
    input = [[Interval(1, 3), Interval(9, 12)], [
        Interval(2, 4)], [Interval(6, 8)]]
    print("Free intervals: ", end='')
    for interval in find_employee_free_time(input):
        interval.print_interval()
    print()

    # result = [5,7]
    input = [[Interval(1, 3)], [
        Interval(2, 4)], [Interval(3, 5), Interval(7, 9)]]
    print("Free intervals: ", end='')
    for interval in find_employee_free_time(input):
        interval.print_interval()
    print()


main()
<file_sep>/problems/binary_search/bitonic_array.py
def search_bitonic_array(arr, key):
  # find the peak index
  lo = 0
  hi = len(arr) - 1
  while (lo < hi):
    mid = (hi + lo) // 2
    is_increasing = arr[mid] < arr[mid+1]
    if is_increasing:
      # mid can never be the peak when is_increasing, so we can safely set low = mid +1
      lo = mid + 1 
    else:
      hi = mid
  
  peak_idx = lo

  # binary search for key in left half
  left_search_result = binary_search(arr, 0, peak_idx, key, True)
  if left_search_result != -1:
    return left_search_result

  # binary search for key in right half
  right_search_result = binary_search(arr, peak_idx+1, len(arr)-1, key, False)
  if right_search_result != -1:
    return right_search_result

  return -1

def binary_search(arr, lo, hi, key, is_increasing):
  while (lo <= hi):
    mid = (hi + lo) // 2
    if arr[mid] == key:
      return mid
    elif (is_increasing and key < arr[mid]) or (not is_increasing and key > arr[mid]):
      hi = mid - 1
    else:
      lo = mid + 1
  return -1

def main():
  print(search_bitonic_array([1, 3, 8, 4, 3], 4))
  print(search_bitonic_array([3, 8, 3, 1], 8))
  print(search_bitonic_array([1, 3, 8, 12], 12))
  print(search_bitonic_array([10, 9, 8], 10))


main()
<file_sep>/sorting/quicksort/quicksort.py
# quicksort algorithm
import random
import copy

# returns random index in the array segment
# left: left index of array segment
# right: right index of array segment
def choose_pivot(left, right):
    return random.randint(left, right)


# partitions so that all values less than pivot are placed to the left of pivot
# and all values greater than pivot are placed to the right of pivot
# returns index of pivot once arr has been partitioned
# arr: original array to partition
# left: left index bounding segment to partition
# right: right index bounding segment to partition
# pivot: index of pivot
def partition(arr, left, right, pivot):
    arr[left], arr[pivot] = arr[pivot], arr[left] #swap pivot with leftmost element
    pivot_val = arr[left]
    i = left + 1 #index of leftmost element greater than the pivot value
    for j in range(left + 1, right + 1):
        if arr[j] < pivot_val:
            arr[j], arr[i] = arr[i], arr[j]
            i+=1
    arr[left], arr[i-1] = arr[i-1], arr[left] #swap pivot to correct position
    return i-1


# implementation of quicksort algorithm
# arr: array to be sorted
# left: left index of array segment to be sorted
# right: right index of array segment to be sorted
def quicksort(arr, left, right):
    global TOTAL_COMP
    TOTAL_COMP += (right - left) #keep track of number of comparisons
    if left >= right:
        return
    pivot = choose_pivot(left, right) #index of randomly chosen pivot
    pivot = partition(arr, left, right, pivot) #index of chosen pivot after partition
    quicksort(arr, left, pivot - 1)
    quicksort(arr, pivot + 1, right)


def compare_sort_funcs(quicksort_arr, python_sort_arr):
    # flag = True
    # incorrect = []
    # for index, num in enumerate(quicksort_arr):
    #     if index+1 != num:
    #         flag = False
    #         incorrect.append([index, num])
    # print("Both arrays are the same: ", flag)
    # print("Incorrect locations:")
    # print(incorrect)
    print("Both arrays are the same: " + str(quicksort_arr == python_sort_arr))

if __name__ == '__main__':
    TOTAL_COMP = 0 #running total of comparisons for a way of choosing the pivot

    with open('quick_sort_test_data.txt', 'r') as f:
        orig_array = [int(num.strip()) for num in f]
    
    print(orig_array[0])
    arr1 = copy.deepcopy(orig_array)
    n = len(arr1)
    quicksort(arr1, 0, n-1)

    with open('quick_sort_test_output.txt', 'w') as output_f:
        for num in arr1:
            output_f.write(f'{num}\n')

    # compare quicksort and python's sort function
    compare_sort_funcs(arr1, sorted(orig_array))

    print('Total number of comparisons: ', TOTAL_COMP)<file_sep>/problems/top_k_elements/frequency_stack.py
import heapq

"""
Design a stack-like data structure with the following operations:
- push(int num): Pushes the number 'num' on the stack.
- pop(): Returns the most frequent number in the stack. If there is a tie, 
  return the number which was pushed later.

Time complexity: O(log(N)) for both push() and pop() methods
Space complexity: O(N)
"""

class Element:
  def __init__(self, num, freq, time):
    self.num = num
    self.freq = freq
    self.time = time

  # methods in heapq will use the __lt__ method to sort the heap's elements
  def __lt__(self, other):
    # sort by higher frequency first
    if self.freq != other.freq:
      return self.freq > other.freq # true means current instance comes before "other"
    # if both have the same frequency, sort by the element that was pushed later
    return self.time > other.time

class FrequencyStack:
  def __init__(self):
    self.max_heap = [] # max heap sorted by frequency
    self.freq_map = {} # maps number to frequency
    self.time = 0

  def push(self, num):
    self.freq_map[num] = self.freq_map.get(num, 0) + 1
    elem = Element(num, self.freq_map[num], self.time)
    heapq.heappush(self.max_heap, elem)
    self.time += 1

  def pop(self):
    num = heapq.heappop(self.max_heap).num
    self.freq_map[num] -= 1
    return num


def main():
  frequencyStack = FrequencyStack()
  frequencyStack.push(1)
  frequencyStack.push(2)
  frequencyStack.push(3)
  frequencyStack.push(2)
  frequencyStack.push(1)
  frequencyStack.push(2)
  frequencyStack.push(5)
  print(frequencyStack.pop())
  print(frequencyStack.pop())
  print(frequencyStack.pop())


main()<file_sep>/problems/monotonic_stack_and_queue/largest_rectangle_in_histogram.py
"""
Given an array of integers heights representing the histogram's bar height where 
the width of each bar is 1, return the area of the largest rectangle in the histogram.

Time complexity: O(n)
Space complexity: O(n)
"""

from typing import List

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # i is the index of the bar whose height is the height of a candidate rectangle
        # l is the first index of a bar to the left with height h[l] < h[i]
        # r is the first index of a bar to the right with height h[r] < h[i]
        
        max_area = 0
        indexes = [-1]
        heights.append(0) # ensures "indexes" stack will never be empty
        # also ensures that all heights > 0 will be popped from stack when you reach
        # the end of the heights array
        
        for r, height in enumerate(heights):
            while heights[indexes[-1]] > height:
                i = indexes.pop()
                h = heights[i]
                w = r - indexes[-1] - 1 # right - left - 1
                max_area = max(max_area, h*w)
            indexes.append(r)
        
        heights.pop()
        return max_area<file_sep>/problems/subsets/evaluate_expression.py
"""
Given an expression containing digits and operations (+, -, *), 
find all possible ways in which the expression can be evaluated 
by grouping the numbers and operators using parentheses.

Soln: If we know all of the ways to evaluate the left-hand 
side (LHS) of an expression and all of the ways to evaluate 
the right-hand side (RHS), we can determine all of the ways 
to evaluate the entire expression.

Time complexity: O(N * 2^N)

Space complexity: O(2^N)
"""

def diff_ways_to_evaluate_expression(input):
  # base case
  if input.isdigit():
    return [int(input)]
  
  result = []
  for i in range(len(input)):
    char = input[i]
    
    if char.isdigit():
      continue

    LHS = diff_ways_to_evaluate_expression(input[:i])
    RHS = diff_ways_to_evaluate_expression(input[i+1:])

    for left_part in LHS:
      for right_part in RHS:
        if char == '+':
          result.append(left_part + right_part)
        elif char == '-':
          result.append(left_part - right_part)
        else:
          result.append(left_part * right_part)
   
  return result


def main():
  print("Expression evaluations: " +
        str(diff_ways_to_evaluate_expression("1+2*3")))

  print("Expression evaluations: " +
        str(diff_ways_to_evaluate_expression("2*3-4-5")))


main()
<file_sep>/graphs/topological_sort.py
"""
Given a directed graph, return an array of nodes where 
each node appears before all the nodes it points to.

Time complexity: O(|V| + |E|)
    - |V| is the number of vertices
    - |E| is the number of edges
    
Space complexity: O(|V|)
"""

### Kahn's Algorithm ###
from collections import deque
class SolutionKahn:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # create adj list and track degree of each node (number of incoming edges)
        degree = [0]*numCourses
        adj = [set() for _ in range(numCourses)]
        for course, prereq in prerequisites:
            adj[prereq].add(course)
            degree[course] += 1
        
        # implement topological sort using Kahn's algorithm
        queue = deque([i for i in range(numCourses) if degree[i] == 0])
        topsort = []
            
        while queue:
            course = queue.popleft()
            topsort.append(course)
            # iterate through neighboring nodes and reduce degree by 1
            for course_next in adj[course]:
                degree[course_next] -= 1
                # nodes in a cycle would never have degree 0,
                # so they would never be added to the queue
                if degree[course_next] == 0:
                    queue.append(course_next)
        
        # if there is a cycle, not all nodes will have degree 0, 
        # which means not all nodes have been added to the list "topsort"
        if len(topsort) != numCourses:
            return []
        return topsort
        

### DFS solution ###
class SolutionDfs:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # create adj list
        adj = [set() for _ in range(numCourses)]
        for course, prereq in prerequisites:
            adj[prereq].add(course)
            
        ### dfs method
        # visited[i] == 0 means not visited, 1 means has visited, -1 means is visiting
        visited = [0 for course in range(numCourses)]
        self.ans = []
        self.is_possible = True # true if topological order is possible
        for i in range(numCourses):
            self.dfs(i, visited, adj)
            if not self.is_possible: 
                return []
        return self.ans[::-1]
        
    def dfs(self, node, visited, adj):
        # going to a node that you are "visiting" means you have a cycle
        # and a topological ordering is impossible
        if visited[node] == -1:
            self.is_possible = False
            return
        if visited[node] == 1:
            return
        
        visited[node] = -1
        for neighbor in adj[node]:
            self.dfs(neighbor, visited, adj)
        self.ans.append(node) # append in reverse topological order
        visited[node] = 1
        
<file_sep>/problems/subsets/balanced_parentheses.py
from collections import deque

"""
BFS-like approach
Generates each "node" part by part

Time complexity: O(N * 2^N) --> good enough for interview purposes
Each position can hold an open or close parenthesis, so there are
approx 2^N combinations to generate. For each combination, we have to
concatenate a new parenthesis to the current string, which takes O(N)

Space complexity: O(N * 2^N)
"""

def generate_valid_parentheses(num):
  result = deque([''])
  # count[0] is the number of open paren
  # count[1] is the number of close paren
  counts = deque([[0, 0]]) 

  for i in range(1, 2*num + 1):
    level_size = len(result)
    for _ in range(level_size):
      parens = result.popleft()
      count = counts.popleft()

      # add open paren
      if count[0] < num:
        result.append(parens + '(')
        counts.append([count[0] + 1, count[1]])
      # add close paren
      if count[0] > count[1]:
        result.append(parens + ')')
        counts.append([count[0], count[1] + 1])
     
  return list(result)


def main():
  print("All combinations of balanced parentheses are: " +
        str(generate_valid_parentheses(2)))
  print("All combinations of balanced parentheses are: " +
        str(generate_valid_parentheses(3)))


main()
<file_sep>/graphs/bfs/bfs_shortest_reach.py
# find distance to any node in an undirected graph using bfs

import math
import os
import random
import re
import sys

# Complete the bfs function below.
def bfs(n, m, edges, s):
    #create an adjacency list
    adj_list = [set() for _ in range(n)] #zero-indexed
    for edge in edges:
        adj_list[edge[0]-1].add(edge[1])
        adj_list[edge[1]-1].add(edge[0])

    explored = [False]*n #zero-indexed
    explored[s-1] = True
    dist = [-1]*n #zero-indexed
    dist[s-1] = 0 #distance at starting node is zero
    queue = [s] #queue to track order of nodes to explore
    while queue:
        v = queue.pop(0) #current vertex
        for w in adj_list[v-1]:
            if not explored[w-1]:
                explored[w-1] = True
                queue.append(w)
                dist[w-1] = dist[v-1] + 6
    # print(adj_list)
    # print(explored)
    return dist[:s-1] + dist[s:]

            
if __name__ == '__main__':
    with open('input.txt') as input_f:

        q = int(input_f.readline())

        for q_itr in range(q):
            nm = input_f.readline().split()

            n = int(nm[0])

            m = int(nm[1])

            edges = []

            for _ in range(m):
                edges.append(list(map(int, input_f.readline().rstrip().split())))

            s = int(input_f.readline())

            result = bfs(n, m, edges, s)

            print(' '.join(map(str, result)))

        # fptr.close()
<file_sep>/problems/top_k_elements/rearange_string.py
import heapq

"""
Given a string, find if its letters can be rearranged 
in such a way that no two same characters come next to each other.

Time complexity: O(N * log(N))
Space complexity: O(N)
"""

def rearrange_string(str):
  charFrequencyMap = {}
  for char in str:
    charFrequencyMap[char] = charFrequencyMap.get(char, 0) + 1

  maxHeap = []
  # add all characters to the max heap
  for char, frequency in charFrequencyMap.items():
    heapq.heappush(maxHeap, (-frequency, char))

  # alternate between appending different letters by using a previousChar
  # variable to track which letter you just appended
  previousChar, previousFrequency = None, 0
  resultString = []
  while maxHeap:
    frequency, char = heapq.heappop(maxHeap)
    # add the previous entry back in the heap if its frequency is greater than zero
    if previousChar and -previousFrequency > 0:
      heapq.heappush(maxHeap, (previousFrequency, previousChar))
    # append the current character to the result string and decrement its count
    resultString.append(char)
    previousChar = char
    previousFrequency = frequency+1  # decrement the frequency

  # if we were successful in appending all the characters to the result string, return it
  return ''.join(resultString) if len(resultString) == len(str) else ""


def main():
  print("Rearranged string:  " + rearrange_string("aappp"))
  print("Rearranged string:  " + rearrange_string("Programming"))
  print("Rearranged string:  " + rearrange_string("aapa"))


main()
