The problem wants to demonstrate "selection algorithm". Specifically the implementation is Quickselect.

https://en.wikipedia.org/wiki/Selection_algorithm
https://en.wikipedia.org/wiki/Quickselect

Quickselect has worst-case time complexity O(n2) same as quicksort, but practical complexity O(n).

The problem should have explained that. From the definition it's unclear what we were supposed to do. Easiest approach is to just sort the array and get the middle element. Unless you know math, it's unclear why selection is supposed to have better complexity than sort, because from simply eyeballing it it looks exactly the same.

i know this problem can be easily solved by sorting the array and returning the middle elemrnt. But I wanted to challenge myself and reduce the run time from O(nlogn) to O(n). Quick Select shown below implemented in a pythonic way has that run time. Hope it helps!

def partition(l, start, end):
    pivot = l[start]
    bound = start + 1
    for i in range(start+1, end+1):
        if l[i] < pivot:
            l[i], l[bound] = l[bound], l[i]
            bound += 1
            
    bound -= 1
    l[start], l[bound] = l[bound], l[start]
    return bound

def find_median(l, start, end, k):
    if(start == end):
        return l[end]
    
    cur = partition(l, start, end)
    if cur == k:
        return l[k]
    elif cur > k:
        return find_median(l, start, cur - 1, k)
    else:
        return find_median(l, cur + 1, end, k)
        
n = int(input())
l = list(map(int, input().split()))

k = n // 2
    
print(find_median(l,0,n-1,k))

The problem statement clearly says: "Can you figure out a way to use your partition code to find the median in an array?"

Yet most people seem to just use sort in their submission. That seems to totally miss the point!

The grader should be fixed such that a solution that uses sort in O(nlog(n)) would time out, whereas one with partition only, O(n) would pass.

find most people implemented it with sort(), which is O(n*logN)? nth_element would give O(N)

The way I did this is to notice that we are certain of only the location of the pivot, if we have l items less than the pivot, then the pivot is in the lth position, if the we count from 0. The median is the object at the len(ar)//2 position starting at 0 for odd number arrays. So we try to find that position.
If the position we are looking for is in the left partition we just recurse for the same position on the left side (pos < len(leftside)) If the position is in the right side we recurse on that side to search for position pos- len(leftside) -1 Since the positions in the right side start after the leftside positions + 1 for the pivot. Eventually you will get an array of size one and a search for position 0, which only has a pivot and no right or left side, and you have found the answer. This method should find any kth order statistic, such as the 0th or minimum and the len(ar)-1 th or maximum