IN PYTHON

from __future__ import annotations # allow self-reference from typing import List, Optional

class TreeNode: def __init__(self, val: int, left: TreeNode = None, right: TreeNode = None): self.val = val self.left = left self.right = right

def rewind_combo(points: List[int]) -> List[Optional[int]]: pass

In this problem you will be given a list of integers. Each element of the input list should be replaced with the greatest element that is smaller than the current element and is to its left. Your function will return nothing, but instead will edit the input list inplace so the element's greatest smaller predecessor will take its place. For example, if the input list [4, 6, 3, 9, 7, 10) the output would be [None, 4, None, 6, 6, 9]. Please see the below examples for a detailed walk through of the example. As an added twist, we will be requiring you to adhere to an average & worst case time complexity this time around! We highly recommend that you use a BST to solve this problem because it will give you the desired average runtime. Please note that the BST would be non-balancing so, don't worry about the additional overhead that would be required when using/making a balancing BST. The following TreeNode class is given to you class TreeNode: def __init__(self, val: int, left: TreeNode = None, right: TreeNode = None): self.val = val self.left = left self.right = right Modify the following function rewind_combo(points: List[int]) -> List[Optional[int]): points: List[int]: Python integer list of size n representing hit points Return: A new list with the greatest smaller predecessor for each element in the list Average Case Time Complexity: O(nlogn) where n is the size of the points list Worst Case Time Complexity: O(n^2) where n is the size of the points list Space Complexity: O(n) where n is the size of the points list Note: You will not receive any runtime points for this function unless you meet both the average and worst case time complexities. . 0 Guarantees The points list will always contain integers with no duplicates Examples: ORIGINAL input = [4, 6, 3, 9, 7, 10] Input = [4, 6, 3, 9, 7, 10] The first element of the original list has no elements to its left, which guarantees it will be replaced with None. So the return list should look like [None] Input = [4, 6, 3, 9, 7, 10] The first element of the original list has no elements to its left, which guarantees it will be replaced with None. So the return list should look like [None] Input = [4, 6, 3, 9, 7, 10] The second element, 6, has one element to its left in the original list [4, 6, 3, 9, 7, 10] with a value of 4.4 is less than 6 and is the greatest of all 1 values to its left, so the second element will be replaced with 4. The return list should now look like [None, 4] Input = [4, 6, 3, 9, 7, 10] The third element, 3, has two elements to its left in the original list [4, 6, 3, 9, 7, 10) with the values of 4 and 6. Neither of these values are less than 3, guaranteeing the third element will be replaced with None. The return list should now look like [None, 4, None] Input = [4, 6, 3, 9, 7, 10] The fourth element, 9, has three elements to its left in the original list (4, 6, 3, 9, 7, 10] with the values of 4, 6 and 3. All of these values are less than 9, so the element will be replaced with the largest of the three, 6. The return list should now look like [None, 4, None, 6] Input = [4, 6, 3, 9,7,10) The fifth element, 7, has four elements to its left in the original list [4, 6, 3, 9, 7, 10) with the values of 4, 6, 3 and 9. All of these values except 9 are less than 7, so the element will be replaced with the largest of the three, 6. The return list should now look like [None, 4, None, 6, 6] Input = [4, 6, 3, 9, 7, 10) Finally the last element, 10, is the largest element of the list, and will be replaced with the largest value coming before it, 9. So the return list should look like [None, 4, None, 6,6,9) Once the function is all done the returned list should look like [None, 4, None, 6, 6, 9). In this problem you will be given a list of integers. Each element of the input list should be replaced with the greatest element that is smaller than the current element and is to its left. Your function will return nothing, but instead will edit the input list inplace so the element's greatest smaller predecessor will take its place. For example, if the input list [4, 6, 3, 9, 7, 10) the output would be [None, 4, None, 6, 6, 9]. Please see the below examples for a detailed walk through of the example. As an added twist, we will be requiring you to adhere to an average & worst case time complexity this time around! We highly recommend that you use a BST to solve this problem because it will give you the desired average runtime. Please note that the BST would be non-balancing so, don't worry about the additional overhead that would be required when using/making a balancing BST. The following TreeNode class is given to you class TreeNode: def __init__(self, val: int, left: TreeNode = None, right: TreeNode = None): self.val = val self.left = left self.right = right Modify the following function rewind_combo(points: List[int]) -> List[Optional[int]): points: List[int]: Python integer list of size n representing hit points Return: A new list with the greatest smaller predecessor for each element in the list Average Case Time Complexity: O(nlogn) where n is the size of the points list Worst Case Time Complexity: O(n^2) where n is the size of the points list Space Complexity: O(n) where n is the size of the points list Note: You will not receive any runtime points for this function unless you meet both the average and worst case time complexities. . 0 Guarantees The points list will always contain integers with no duplicates Examples: ORIGINAL input = [4, 6, 3, 9, 7, 10] Input = [4, 6, 3, 9, 7, 10] The first element of the original list has no elements to its left, which guarantees it will be replaced with None. So the return list should look like [None] Input = [4, 6, 3, 9, 7, 10] The first element of the original list has no elements to its left, which guarantees it will be replaced with None. So the return list should look like [None] Input = [4, 6, 3, 9, 7, 10] The second element, 6, has one element to its left in the original list [4, 6, 3, 9, 7, 10] with a value of 4.4 is less than 6 and is the greatest of all 1 values to its left, so the second element will be replaced with 4. The return list should now look like [None, 4] Input = [4, 6, 3, 9, 7, 10] The third element, 3, has two elements to its left in the original list [4, 6, 3, 9, 7, 10) with the values of 4 and 6. Neither of these values are less than 3, guaranteeing the third element will be replaced with None. The return list should now look like [None, 4, None] Input = [4, 6, 3, 9, 7, 10] The fourth element, 9, has three elements to its left in the original list (4, 6, 3, 9, 7, 10] with the values of 4, 6 and 3. All of these values are less than 9, so the element will be replaced with the largest of the three, 6. The return list should now look like [None, 4, None, 6] Input = [4, 6, 3, 9,7,10) The fifth element, 7, has four elements to its left in the original list [4, 6, 3, 9, 7, 10) with the values of 4, 6, 3 and 9. All of these values except 9 are less than 7, so the element will be replaced with the largest of the three, 6. The return list should now look like [None, 4, None, 6, 6] Input = [4, 6, 3, 9, 7, 10) Finally the last element, 10, is the largest element of the list, and will be replaced with the largest value coming before it, 9. So the return list should look like [None, 4, None, 6,6,9) Once the function is all done the returned list should look like [None, 4, None, 6, 6, 9)