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.
  1. Prepare
  2. Algorithms
  3. Sorting
  4. Find the Median
  5. Discussions

Find the Median

  • gnawer
     + 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.

    • thirty3
       + 1 comment

      Selection has a better complexity than sort because you only ever have to search one side of the pivot, where sorting necesitates sorting both sides.

      • alphasingh
         + 2 comments

        Like quicksort, the quickselect has good average performance, but is sensitive to the pivot that is chosen. If good pivots are chosen, meaning ones that consistently decrease the search set by a given fraction, then the search set decreases in size exponentially and by induction (or summing the geometric series) one sees that performance is linear, as each step is linear and the overall time is a constant times this (depending on how quickly the search set reduces). However, if bad pivots are consistently chosen, such as decreasing by only a single element each time, then worst-case performance is quadratic: O(n2). This occurs for example in searching for the maximum element of a set, using the first element as the pivot, and having sorted data.

        • ndon55555
           + 1 comment

          Not a problem if using the median of medians algorithm with worst case O(n)

          • Gh05t
             + 1 comment
            [deleted]

            • vishalbty
               + 0 comments

              35 marks is too much for this question.

              Solution in Python Hackerrank - Find the Median Solution

        • yashpalsinghdeo1
           + 0 comments

          here is problem solution in java python c++ c and javascript programming. https://programs.programmingoneonone.com/2021/05/hackerrank-find-the-median-solution.html

    • stepheneliot8891
       + 0 comments

      I think the idea was to encourage you to think about the problem on your own. I did and came up w/ the same idea as quickselection.

      That said, it was helpful to get your links because I needed confirmation I was on the right track. Thanks!

    • chera
       + 4 comments
      import java.io.*;
import java.util.*;

public class Solution {
    
    static int n;
    public static int partition(int[] a, int f, int l)
    {
        int pivot= a[l];
        int i,p_in=0;
        int temp;
        for(i=f;i<l;i++)
            {
                if(a[i]<=pivot)
                  { temp=a[i];
                    a[i]=a[p_in];
                    a[p_in]=temp;
                    p_in++;
                  }
            }
        temp= a[p_in];
        a[p_in]=a[l];
        a[l]=temp;
        return p_in;
    }
    
    
    
    public static void quickSort(int[] a, int s, int e)
    {
        int mid= (n-1)/2;
        int p_index;
        if(s<e)
        {
            p_index= partition(a,s,e);
           
            if(p_index==mid)
            {   System.out.println(a[p_index]);
                return;
            }
           if(p_index>mid)
           {
                quickSort(a,s,p_index-1);
           }
            if(p_index<mid)
            { quickSort(a,p_index+1,e);
            }
            
        }
    }

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc= new Scanner(System.in);
         n= sc.nextInt();
        int i;
        int []a= new int[n];
        for(i=0;i<n;i++)
        {
            a[i]= sc.nextInt();
        }
        quickSort(a,0,n-1);
    }
}

      this is my code in java but terminated due to timeout, can't understand why it is taking so much of time while many people have done the same thing and get all test cases passes. plz help!!!

      • jabhi207
         + 0 comments

        This only fails in testcase 2

        import java.io.*;
import java.util.*;

public class Solution {
    
    static int n;
    public static int partition(int[] a, int f, int l)
    {
        int pivot= a[l];
        int i,p_in=f;
        int temp;
        for(i=f;i<=l;i++){
                
            if(a[i] <= pivot){ 
                temp=a[i];
                a[i]=a[p_in];
                a[p_in]=temp;
                p_in++;
            }
         }
       
        return p_in-1;
    }
    
    
    
    
    
    
    public static void quickSort(int[] a, int s, int e)
    {
        int mid = n/2;
        int p_index;
        if(s<e){
           
            p_index = partition(a,s,e);
           
            if(p_index == mid){   
                System.out.println(a[p_index]);
                return;
            }
         
             quickSort(a,s,p_index-1);
             quickSort(a,p_index+1,e);
        
            
        }
    }

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc= new Scanner(System.in);
         n= sc.nextInt();
        int i;
        int []a= new int[n];
        for(i=0;i<n;i++)
        {
            a[i]= sc.nextInt();
        }
        quickSort(a,0,n-1);
    }
}

      • avinasshbharadh1
         + 3 comments

        it is taking a lot of time than alloted time by compiler(online) so use mergesort instead of quicksort [ quick has worsttime complexity of O[n^2] due to selction of pivot] mergesort has O[nlogn]

        • ndon55555
           + 1 comment

          Don't need to sort

        • zakiralig184
           + 1 comment

          I have used Quiksort() and it passes ALL TEst Cases!!!!!!

          • ruet_ujjal38
             + 0 comments

            which index you have selected for pivot?

        • decodefreak
           + 0 comments

          You can use randomized quicksort for better time complexity, i passed all testcases with this C++ code.

          sort(arr.begin(),arr.end());
int n=arr.size();
return arr[n/2];

      • jvsilvictor
         + 0 comments
        static int findMedian(int[] arr) 
{
    List<int> list = arr.ToList();
    list.Sort();
    return list[(int)(list.Count/2)];
}

    • rodbourn
       + 0 comments

      As a hint, you can 'alter' quicksort to better its complexity...

    • balraj888
       + 1 comment

      plz check this sol. O(n), 

      q=[0]*len(arr)
for i in arr:
    q[i]+=1

mid=len(arr)//2
m=0
print q
for i,v in enumerate(q):
    if m>mid:
        print(i,m)
        return i-1
    m+=v

      • paarav_dhp
         + 0 comments

        n, arr = int(input()), list(map(int, input().rstrip().split())) print(sorted(arr)[n//2])

    • kris_tobiasson
       + 0 comments

      Did I miss something here?? This is the easiest problem and yet it delivers 35 points upon successful completion. This should have been one of the first questions IMHO.. This ugly JS one liner solves it:

          return arr.sort((a,b) => a-b)[Math.ceil(arr.length*0.5)-1];

    • Evil_sting
       + 1 comment

      I just wanna ask , if some numbers in the array are repeated, even then quick select will be effective? like 3,2,4,2,6,2,1,5 is array , will quick select can find median element?

      • Gh05t
         + 0 comments

        As far as I remember quick select works on arrays with repeating data as well, you can just run your example once to check.

    • Mohd_Zohaib
       + 0 comments
      # pure maths 
def median(arr):
    arr.sort()
    if len(arr) % 2 == 1:
        ret_value = arr[int((len(arr)-1)/2)]
    else:
        ret_value = 0.5*(arr[int(len(arr)/2-1)]+arr[int(len(arr)/2)])
    return ret_value

#when yer graduated but cheated   
def findMedian(arr, n):
    return median(sorted(arr))
    

if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split(' ')))
    print(findMedian(arr, n))

Join us

Create a HackerRank account

Be part of a 26 million-strong community of developers

Already have an account?Log in