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 a new list that reflects these changes, so that element's greatest smaller predecessor will be in the corresponding index. 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.
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 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 nents 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 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).