Median Again

Approach

• The first step would be to sort the array in non-decreasing order( In Java, we can use the inbuilt sort function).
• We keep increasing the median to equal its right values until it reaches the last element (largest value in array) or our operation limit or capacity is got.
• If the number of integers equals 1, i.e., n==1, then add the total capacity given into that number.
• If n>1, we will find the median calculated by finding the middle element in non-decreasing order.
• After finding the middle element, iterate through the array from mid+1 to n-1.
• For every iteration, we will try to make from mid to i-1 to i.
• After this, there will be two cases for utilizing the maximum capacity and finding the median.
• Curr variable will store the total number of operations performed on the mid to i-1 to i.
• And the ‘ans’ variable will store the maximum median of the array.

Also read, Euclid GCD Algorithm

Implementation

import java.util.*;
import java.io.*;
 
public class Main {

 public static void main(String args[]) throws IOException {

 
   Scanner sc = new Scanner(System.in);

   int n = sc.nextInt();

   // Total capacity
   long k = sc.nextLong();

   long a[] = new long[n];

   for(int i=0;i<n;i++){

     a[i] = sc.nextLong();

   }
 
   // If the number of integers is ‘1’ 
   if(n==1){

     System.out.println(a[0]+k);

     return;

   }

   // Sorting is non decreasing order
   Arrays.sort(a);

   // Finding the middle element 
   int mid = n/2;

   // For storing the mid element
   long ans = a[mid];

   // Iterating through the array from the middle element to check for every operation 
   // that it is equal to or greater than the next right element. 
   for(int i=mid+1;i<n;i++){

     long cur = a[i] - a[i-1];

     cur = cur * 1L * (i - mid);

     if(cur>=k){

       System.out.println(ans + k/(i-mid));

       return;

     }

     k -= cur;

     ans += a[i] - a[i-1];

   }

   ans += k/(n/2+1);

   System.out.println(ans);

 }

}

Analysis of Complexity

Time Complexity: The Time Complexity is O(N * log(N) + N/2) where O(N * log(N)) time is taken to sort the array and O(N/2) time to traverse the array for the median.

Space Complexity: The space complexity will be O(1).

FAQs

1). How many Sorting techniques do sort the elements?

     There are various sorting algorithms; some follow the in-place technique or divide and conquer approach.

• Insertion Sort
• Selection Sort
• Bubble Sort
• Counting Sort
• Radix Sort
• Bucket Sort
• Merge Sort
• Quick Sort
• Heap Sort

2). What is the time complexity to solve this problem?

     The Time Complexity is O(N*logN+N/2), where N is the number of the integers in the array.

3). What is the inbuilt function to sort the array in Java language?

     The inbuilt function to sort the array in Java language is Arrays.sort that uses dual-pivot Quicksort on primitives.

Key Takeaways

In this article, we have discussed the following things:

• What the actual problem Median Again is?
• Approach and Implementation to solve this problem.

Also Read - Selection Sort in C

Recommended Problems - 

• Sort 0 1 2 
• Wiggle sort
• Find first and last position in sorted array

Don’t forget to practice the wide variety of DSA problems frequently asked in interview rounds readily available on Coding Ninjas Studio. 

Happy coding!!