def bubbleSort(arr):
    n = len(arr)
    # Traverse through all array elements
    for i in range(n-1):
        # Last i elements are already in place
        for j in range(0, n-i-1):
            # Traverse the array from 0 to n-i-1
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

# Example usage
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
print("Sorted array is:")
for i in range(len(arr)):
    print("%d" % arr[i], end=" ")

def quick_sort(arr):
    # Base case: an array with 0 or 1 elements is already sorted
    if len(arr) <= 1:
        return arr

    # Choosing the pivot element from the array
    pivot = arr[len(arr) // 2]

    # Elements less than pivot
    left = [x for x in arr if x < pivot]

    # Elements equal to pivot
    middle = [x for x in arr if x == pivot]

    # Elements greater than pivot
    right = [x for x in arr if x > pivot]

    # Recursively sort the left and right parts and combine them with the middle
    return quick_sort(left) + middle + quick_sort(right)

# Example usage
array = [3, 6, 8, 10, 1, 2, 1]
sorted_array = quick_sort(array)
print(sorted_array)

def heapify(arr, n, i):
    largest = i  # Initialize largest as root
    left = 2 * i + 1     # left child
    right = 2 * i + 2    # right child

    # See if left child of root exists and is greater than root
    if left < n and arr[i] < arr[left]:
        largest = left

    # See if right child of root exists and is greater than root
    if right < n and arr[largest] < arr[right]:
        largest = right

    # Change root, if needed
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # swap

        # Heapify the root.
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)

    # Build a maxheap.
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # One by one extract elements
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]   # swap
        heapify(arr, i, 0)

# Example usage
arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
print("Sorted array is:", arr)

def bucketSort(arr):
    # Find maximum value in the array and use length of the array to determine which value in the array goes into which bucket
    max_value = max(arr)
    size = max_value/len(arr)

    # Create n empty buckets where n is equal to the length of the array
    buckets_list= [[] for _ in range(len(arr))]

    # Put array elements in different buckets based on size
    for i in range(len(arr)):
        j = int(arr[i] / size)
        if j != len (arr):
            buckets_list[j].append(arr[i])
        else:
            buckets_list[len(arr) - 1].append(arr[i])

    # Sort elements within the buckets using Insertion Sort
    for z in range(len(arr)):
        insertionSort(buckets_list[z])
            
    # Concatenate buckets with sorted elements into a single array
    final_output = []
    for x in range(len(arr)):
        final_output = final_output + buckets_list[x]
    return final_output

def insertionSort(b):
    for i in range(1, len(b)):
        up = b[i]
        j = i - 1
        while j >=0 and b[j] > up: 
            b[j + 1] = b[j]
            j -= 1
        b[j + 1] = up    
    return b    

# Example usage
arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
print("Sorted Array is")
print(bucketSort(arr))

# brute force
#  - time: O(n2)
#  - space: O(n)
    def isValid(self, s: str) -> bool:
        while '()' in s or '{}' in s or '[]' in s:
            s = s.replace('()', '')
            s = s.replace('{}', '')
            s = s.replace('[]', '')
        return s == ''
# stack
#  - time: O(n)
#  - space: O(n)
    def isValid(self, s):
        stack = []
        m = {"(": ")", "{": "}", "[": "]"}
        for char in s:
            if char in m:
                stack.append(char)
            else:
                if len(stack) == 0: # )
                    return False
                top = stack.pop()
                if char != m[top]: # [)
                    return False

        return stack # [()

给定一个只包含 "()[]{}" 六种字符的字符串。规定它们的优先级由外至内为："{}", "[]", "()"，同一级的可以嵌套，并列。要求判断给定的字符串是否是合法的括号字串？

例："()", "{((()())())[()]}()" 是合法的。"())", "([])", "())(()", "[{}]" 都是不合法的。
({})

样例1:
[输入]
"{((()())())[()]}()"
[输出]
True

# ()[] OK
# {[()]} OK
# {([]{})} !OK
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        pair_map = {"(": ")", "{": "}", "[": "]"}
        priority_map = {
            "(": 1, ")": 1,
            "[": 2, "]": 2,
            "{": 3, "}": 3
        }
        stack = []  # space: O(n)
        for char in s:  # time: O(n)
            if char in pair_map:
                # 开括号入栈前，若栈顶存在，则要求新开括号优先级 <= 栈顶开括号优先级
                if stack:
                    top_char = stack[-1]
                    if priority_map[char] > priority_map[top_char]:  # 若想要往里嵌套更高优先级的括号，非法
                        return False
                stack.append(char)

            else:
                if len(stack) == 0:  # e.g., ]]]]
                    return False
                top_char = stack.pop()
                if pair_map[top_char] != char:  # [}
                    return False
        return len(stack) == 0

# backtrack + tack
# - time: O(4^N/\sqrt{n})
# - space: O(n)
def generateParenthesis(self, n: int) -> List[str]:
		res = []
		stack = []

		def backTracking(openCountUsed, closeCountUsed):
			if openCountUsed == closeCountUsed == n:  # All open and close have been used
				res.append("".join(stack))
				return

			if openCountUsed < n:  # Still have open to be used
				stack.append("(")
				backTracking(openCountUsed + 1, closeCountUsed)
				stack.pop(-1)

			if closeCountUsed < openCountUsed:  # Able to add a close, e.g., "(()", and not able to add a close if like "()"
				stack.append(")")
				backTracking(openCountUsed, closeCountUsed + 1)
				stack.pop(-1)

		backTracking(0, 0)
		return res

# brute force
# - time: O(n2)
# - space: O(n)
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        while len(tokens) > 1:
            for i in range(len(tokens)):
                if tokens[i] in "+-*/":
                    a = int(tokens[i-2])
                    b = int(tokens[i-1])
                    if tokens[i] == '+':
                        result = a + b
                    elif tokens[i] == '-':
                        result = a - b
                    elif tokens[i] == '*':
                        result = a * b
                    elif tokens[i] == '/':
                        result = int(a / b)
                    tokens = tokens[:i-2] + [str(result)] + tokens[i+1:]
                    break
        return int(tokens[0])
      
# stack
# - time: O(n)
# - space: O(n)
def evalRPN(self, tokens: List[str]) -> int:
		stack = []
		for token in tokens:
			if token == "+":
				res = stack.pop(-1) + stack.pop(-1)
				stack.append(res)
			elif token == "-":
				# e.g., ["13","5","/"] -> 13/5
				n1 = stack.pop(-1)  # 5
				n2 = stack.pop(-1)  # 13
				stack.append(n2 - n1)
			elif token == "*":
				res = stack.pop(-1) * stack.pop(-1)
				stack.append(res)
			elif token == "/":
				n1 = stack.pop(-1)  # 5
				n2 = stack.pop(-1)  # 13
				stack.append(int(n2 / n1))  # The division between two integers always truncates toward zero.
			else:
				stack.append(int(token))
		return stack[-1]

# stack
# - time: O(1)
# - space: O(n)
class MinStack:

	def __init__(self):
		self.stack = []  # [cur_element, cur_min]

	def push(self, val: int) -> None:
		curMin = val
		if len(self.stack) > 0:
			curMin = min(curMin, self.stack[-1][1])
		self.stack.append([val, curMin])

	def pop(self) -> None:
		return self.stack.pop(-1)[0]

	def top(self) -> int:
		return self.stack[-1][0]

	def getMin(self) -> int:
		return self.stack[-1][1]

# solution 1 - 两个 queue
class MyStack(object):
	def __init__(self):
		# space: O(n)
		self.queue1 = []  
		self.queue2 = []  

	# time: O(n)
	def push(self, x):
		# 入栈操作时，首先将元素入队到 queue2 ，然后将 queue1 的全部元素依次（从左端）出队并入队到 queue2，此时 queue2的左端的元素即为新入栈的元素，
		# 再将 queue1 和 queue2 互换，则 queue1 的元素即为栈内的元素，queue1 的左端和右端分别对应栈顶和栈底。
		self.queue2.append(x)
		while self.queue1:
			self.queue2.append(self.queue1.pop(0))
		self.queue1, self.queue2 = self.queue2, self.queue1

	# 由于每次入栈操作都确保 queue1 的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。
	# 出栈操作只需要移除 queue1 的前端元素并返回即可，获得栈顶元素操作只需要获得 queue1 的前端元素并返回即可（不移除元素）。
	def pop(self):
		return self.queue1.pop(0)

	def top(self):
		return self.queue1[0]

	def empty(self):
		# 由于 queue1 用于存储栈内的元素，判断栈是否为空时，只需要判断 queue1 是否为空即可。
		return not self.queue1

  
# solution 2 - 一个 queue
class MyStack(object):
	def __init__(self):
		# space: O(n)
		self.queue = []

	# time: O(n)
	def push(self, x):
		n = len(self.queue)
		self.queue.append(x)
		for _ in range(n):
			self.queue.append(self.queue.pop(0))

	def pop(self):
		return self.queue.pop(0)

	def top(self):
		return self.queue[0]

	def empty(self):
		return not self.queue

class MyQueue:
	def __init__(self):
		# space: O(n). 最差情况下，栈 A 和 B 共保存 N 个元素。
		self.inStack = []
		self.outStack = []

	# time: O(1)
	def push(self, x: int) -> None:
		self.inStack.append(x)

	# pop 和 peek 为均摊 O(1)。对于每个元素，至多入栈和出栈各两次，故均摊复杂度为 O(1)
	def pop(self) -> int:
		self.peek()
		return self.outStack.pop()

	# pop 和 peek 为均摊 O(1)。对于每个元素，至多入栈和出栈各两次，故均摊复杂度为 O(1)
	def peek(self) -> int:
		if not self.outStack:
			while self.inStack:
				self.outStack.append(self.inStack.pop(-1))
		return self.outStack[-1]

	# time: O(1)
	def empty(self) -> bool:
		return not self.inStack and not self.outStack