We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Sorting
  4. Find the Median
  5. Discussions

Find the Median

Problem
Submissions
Leaderboard
Discussions

Sort 435 Discussions, By:

votes

Please Login in order to post a comment

  • gnawer
    7 years ago+ 8 comments

    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.

    103|
    Permalink
    View more Comments..
  • ayushr2
    5 years ago+ 3 comments

    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))
    
    22|
    Permalink
  • someknowit
    6 years ago+ 2 comments

    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.

    11|
    Permalink
  • softarts
    7 years ago+ 1 comment

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

    11|
    Permalink
  • cjerian
    7 years ago+ 0 comments

    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

    10|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature