Nuts and Bolts

'''
M-1:
push all the nuts into the set which takes O(n) extra space.make an order array also because we need to do
inplace changes and that inplace also in the order.
go one by one element of the order, check in the nut_set, if it is there means it was there in the nut arr
now if nut is there then Bolt must be there.make both arr at the index as that ch or nut, incremenet idx.

T.C -> O(n)
Space Compleixty-> O(n)
'''
class Solution:
    def matchPairs(self, nuts, bolts):
        order = ['!', '#', '$', '%', '&', '*', '?', '@', '^']

        nut_set = set(nuts)

        idx = 0
        for ch in order:
            if ch in nut_set:
                nuts[idx] = ch
                bolts[idx] = ch
                idx += 1

###We have an extra case here when we are checking the pivot and putting at the end but we don't do it in the quick sort and the reason is we in quick sort we are having the pivot element at the right but here pivot element can be in between also so push at the end first.
'''
M-2
Just apply the quicksort as they are ASCII codes internally and the order they have given is also proper ASCII code increasing order.
T.C: O(n log n) avg
S.C: O(1)
'''

def partition(arr, low, high, pivot):
    i = low
    j = low

    while j < high:
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
        elif arr[j] == pivot: #if you got the pivot element,just place it at the end for now because before returning from this fun, we swap with the ith position
            arr[j], arr[high] = arr[high], arr[j]
            j -= 1
        j += 1

    arr[i], arr[high] = arr[high], arr[i]
    return i


def quicksort(nuts, bolts, low, high):
    if low < high:
        # use last bolt as pivot to partition nuts
        pivot_index = partition(nuts, low, high, bolts[high])

        # now use matched nut to partition bolts
        partition(bolts, low, high, nuts[pivot_index]) #Here after partition, you will get parition point as pivot_index only because both have same elements but unsorted.so we can say, pivot_index is the point whose left is all smaller than nuts[pivot_index]
        # lace which is paritioned, all left elmenets in bolts are smaller and right are bigger than bolts[pivot_index] and pivot_index is same in both arr.

        # recurse
        quicksort(nuts, bolts, low, pivot_index - 1)
        quicksort(nuts, bolts, pivot_index + 1, high)


class Solution:
    def matchPairs(self, nuts, bolts):
        quicksort(nuts, bolts, 0, len(nuts) - 1)