Given an array A[] containing N elements of an array and their frequency in that array (say arr[]), the task is to find the median of the array whose elements and frequency are given.
Note: Median of an array is the element at the middle of the sorted array
Examples:
Input: A[] = { {1, 2}, {4, 2}, {5, 1} }
Output: 4
Explanation: The array whose elements are given is {1, 1, 4, 4, 5}.
Therefore, the median of the array will be 4.Input: A[] = { {3, 4}, {2, 3}, {9, 2} }
Output: 3
Explanation: The newly created array will be {2, 2, 2, 3, 3, 3, 3, 9, 9}.
Therefore the median of the array will be 3.
Naive Approach: The basic approach is to create the array and then sort the array and find the middle element of that array.
C++
// C++ code for above approach.#include<bits/stdc++.h>using namespace std;// Function to find medianint findMedian(vector<vector<int> > a, int n){ // Initialising a vector vector<int> v; // Adding elements to the vector for(int i=0;i<a.size();i++) { for(int j=0;j<a[0].size();j++) v.push_back(a[i][0]); } // sorting the vector sort(v.begin(),v.end()); // Return middle element return v[v.size()/2];}// Driver Codeint main() { vector<vector<int> > A; A = { { 1, 2 }, { 4, 2 }, { 5, 1 } }; int N = A.size(); // Function call cout << findMedian(A, N); return 0;}// This code is contributed by Utkarsh |
Java
import java.util.Arrays;import java.util.Vector;public class Main { // Function to find median static int findMedian(Vector<int[]> a, int n) { // Initializing a vector Vector<Integer> v = new Vector<>(); // Adding elements to the vector for (int i = 0; i < a.size(); i++) { for (int j = 0; j < a.get(0).length; j++) v.add(a.get(i)[0]); } // Sorting the vector Integer[] arr = v.toArray(new Integer[v.size()]); Arrays.sort(arr); // Return middle element return arr[arr.length / 2]; } // Driver code public static void main(String[] args) { Vector<int[]> A = new Vector<>(); A.add(new int[] { 1, 2 }); A.add(new int[] { 4, 2 }); A.add(new int[] { 5, 1 }); int N = A.size(); // Function call System.out.println(findMedian(A, N)); }} |
Python3
# Python3 code for above approach# Function to find mediandef findMedian(a, n): # Initialising a vector v = [] # Adding elements to the vector for i in range(len(a)): for j in range(len(a[0])): v.append(a[i][0]) # sorting the vector v.sort() # Return middle element return v[len(v)//2]# Driver Codeif __name__ == "__main__": A = [[1, 2], [4, 2], [5, 1]] N = len(A) # Function call print(findMedian(A, N)) |
Javascript
// Javascript equivalent// Function to find medianfunction findMedian(arr, n) { // Initializing an array let v = []; // Adding elements to the array for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr[0].length; j++) v.push(arr[i][0]); } // Sorting the array v = v.sort(function(a, b){return a-b}); // Return middle element return v[v.length / 2];}// Driver codelet A = [[1, 2], [4, 2], [5, 1]];let N = A.length;// Function callconsole.log(findMedian(A, N)); |
C#
using System;using System.Collections.Generic;using System.Linq;class Program { // Function to find median static int FindMedian(List<int[]> a, int n) { // Initializing a vector List<int> v = new List<int>(); // Adding elements to the vector for (int i = 0; i < a.Count; i++) { for (int j = 0; j < a[0].Length; j++) v.Add(a[i][0]); } // Sorting the vector int[] arr = v.ToArray(); Array.Sort(arr); // Return middle element return arr[arr.Length / 2]; } // Driver code static void Main(string[] args) { List<int[]> A = new List<int[]>(); A.Add(new int[] { 1, 2 }); A.Add(new int[] { 4, 2 }); A.Add(new int[] { 5, 1 }); int N = A.Count; // Function call Console.WriteLine(FindMedian(A, N)); }}// This code is contributed by shivamgupta310570 |
Output
4
Time Complexity: O(M * log M) where M is the sum of the frequencies of all elements given in A[].
Auxiliary Space: O(M)
Efficient approach: As the sum of frequencies of the elements present in A[] can be very large it is not feasible to build an array. This can be solved efficiently based on the following idea:
Sort the array A[] based on the value of elements. Now calculate the total number of elements that will be in the array formed from these elements (say M). The element at M/2 th position is the median.
So iterate from the minimum elements and with the help of their frequencies find out the element and M/2 th position.
Follow the below steps to implement the above idea:
- Insert all the elements in a map with the elements as the key and their frequency as value (a map is sorted based on the value of the key. Therefore it satisfies the need of sorting).
- Count total elements that will be in the array.
- Iterate from the minimum elements and check if the total elements till the current value is the same as M/2:
- If it is same, then the current element is the required median.
- Otherwise, increase the total number of elements till now.
- Return the median.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Find median of the newly created arrayint findMedian(vector<vector<int> > a, int n){ map<int, int> m; // Size of the newly created array int totalsize = 0; // Put all elements in the map for (int i = 0; i < n; i++) { int val = a[i][0]; int time = a[i][1]; m[val] += time; totalsize += time; } // Find the element present at the middle // of the newly created array int meidanpos = totalsize / 2; long long pos = 0; for (auto it : m) { // If the pos + current element times // is greater than medianpos // then return current element if (pos + it.second > meidanpos) { return it.first; } else { pos += it.second; } }}// Driver Codeint main(){ vector<vector<int> > A; A = { { 1, 2 }, { 4, 2 }, { 5, 1 } }; int N = A.size(); // Function call cout << findMedian(A, N); return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // Find median of the newly created array public static int findMedian(int a[][], int n) { TreeMap<Integer, Integer> m = new TreeMap<Integer, Integer>(); // Size of the newly created array int totalsize = 0; // Put all elements in the map for (int i = 0; i < n; i++) { int val = a[i][0]; int time = a[i][1]; if (m.get(val) != null) m.put(val, m.get(val) + time); else m.put(val, time); totalsize += time; } // Find the element present at the middle // of the newly created array int meidanpos = totalsize / 2; long pos = 0; for (Map.Entry<Integer, Integer> it : m.entrySet()) { // If the pos + current element times // is greater than medianpos // then return current element if (pos + it.getValue() > meidanpos) { return it.getKey(); } else { pos += it.getValue(); } } return 0; } public static void main(String[] args) { int A[][] = { { 1, 2 }, { 4, 2 }, { 5, 1 } }; int N = A.length; // Function call System.out.print(findMedian(A, N)); }}// This code is contributed by Rohit Pradhan |
Python3
# Python3 code to implement the approach# Find median of the newly created arraydef findMedian(a, n): m = dict() # Size of the newly created array totalsize = 0 # Put all elements in the map for i in range(n): val = a[i][0] time = a[i][1] if val in m: m[val] += time else: m[val] = time totalsize += time # find the element present at the middle # of the newly created array medianpos = totalsize // 2 pos = 0 for it in m.items(): # if the pos + current element times # is greater than medianpos # then return the current element if pos + it[1] > medianpos: return it[0] else: pos += it[1]# Driver CodeA = [[1, 2], [4, 2], [5, 1]]N = len(A)# Function Callprint(findMedian(A, N)) # This code is contributed by phasing17 |
C#
// C# program to implement the approachusing System;using System.Collections.Generic;class GFG{ // Find median of the newly created array static int findMedian(int[,] a, int n) { Dictionary<int,int> m = new Dictionary<int,int>(); // Size of the newly created array int totalsize = 0; // Put all elements in the map for (int i = 0; i < n; i++) { int val = a[i,0]; int time = a[i,1]; if (m.ContainsKey(val)) m[val]=m[val] + time; else m[val]=time; totalsize += time; } // Find the element present at the middle // of the newly created array int meidanpos = totalsize / 2; long pos = 0; foreach(KeyValuePair<int, int> it in m) { // If the pos + current element times // is greater than medianpos // then return current element if (pos + it.Value > meidanpos) { return it.Key; } else { pos += it.Value; } } return 0; }// Driver Codepublic static void Main(){ int[,] A = { { 1, 2 }, { 4, 2 }, { 5, 1 } }; int N = A.GetLength(0);; // Function call Console.Write(findMedian(A, N));}}// This code is contributed by Pushpesh Raj |
Javascript
<script>// JavaScript code to implement the approach// Find median of the newly created arrayfunction findMedian(a, n){ let m = new Map() // Size of the newly created array let totalsize = 0 // Put all elements in the map for(let i = 0; i < n; i++){ let val = a[i][0] let time = a[i][1] if(m.has(val)) m.set(val,m.get(val)+time) else m.set(val,time) totalsize += time } // find the element present at the middle // of the newly created array let medianpos = Math.floor(totalsize / 2) let pos = 0 for(let [it,it2] of m) { // if the pos + current element times // is greater than medianpos // then return the current element if(pos + it2 > medianpos) return it else pos += it2 }}// Driver Codelet A = [[1, 2], [4, 2], [5, 1]]let N = A.length// Function Calldocument.write(findMedian(A, N)) // This code is contributed by shinjanpatra</script> |
Output
4
Time Complexity: O(N * logN)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
