Algorithm


Problem Name: Data Structures - Median Updates

Problem Link: https://www.hackerrank.com/challenges/median/problem?isFullScreen=true

In this HackerRank in Data Structures - Median Updates solutions

The median of M numbers is defined as the middle number after sorting them in order if M is odd. Or it is the average of the middle two numbers if M is even. You start with an empty number list. Then, you can add numbers to the list, or remove existing numbers from it. After each add or remove operation, output the median.

Example:
For a set of M = 5 numbers 9,2,8,4,1 he median is the third number in the sorted set 1,2,4,8,9 which is 4. Similarly, for a set of M = 4 numbers, 5,2,10,4 the median is the average of the second and the third element in the sorted set 2,4,5,10  which is (4 + 5 ) / 2 = 4.5.

Input:
The first line is an integer, N, that indicates the number of operations.

Each of the next N lines is either a x or r x. a x indicates that x s added to the set, and r x indicates that x is removed from the set.

Output:
For each operation: If the operation is add, output the median after adding x in a single line. If the operation is remove and the number x is not in the list, output Wrong! in a single line. If the operation is remove and the number x is in the list, output the median after deleting x in a single line. (If the result is an integer DO NOT output decimal point. And if the result is a real number, DO NOT output trailing 0s.)

Note
If your median is 3.0, print only 3. And if your median is 3.50, print only 3.5. Whenever you need to print the median and the list is empty, print Wrong!

Constraints:

0 <= N <= 10**5

For each a x or r x, x will always be a signed integer (which will fit in 32 bits).

Sample Input:

 

7  
r 1  
a 1  
a 2  
a 1  
r 1  
r 2  
r 1  

 

Sample Output:

 

Wrong!  
1  
1.5  
1  
1.5  
1  
Wrong!

Note: As evident from the last line of the input, if after remove operation the list becomes empty, you have to print Wrong!.

 

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
/* Head ends here */
void insertionSort(int N,int *x){
        int temp = x[N-1];
        int j = N-2;
        while ( j >= 0 &&  x[j] > temp){
            x[j+1] = x[j];
            j--;  
        } 
        x[j+1] = temp;
}
void median(int N,char (*s), int *x) {
    int size = 0;
    int a[N];
    for(int i = 0; i  <  N; i++){
        if (s[i] == 'a'){
            a[size++] = x[i];
            insertionSort(size,&a[0]);
            if (size % 2 == 1)
                printf("%d",a[size/2]);
            else{
                 if ((a[size/2]+a[(size/2)-1]) % 2 == 0)
                       printf("%ld",((long)a[size/2]+a[(size/2)-1])/2);
                 else 
                     printf("%1.1f",((signed long)a[size/2]+a[(size/2)-1])/2.0);
                 }
            printf("\n");
        }
        else{
            if (size == 0) {printf("Wrong!\n");continue;}
            int found = 0;
            for(int j = 0; j  <  size; j++){
                if (a[j] == x[i]){
                    for(int k = j; k  <  size - 1; k++){
                        a[k] = a[k+1];
                    }
                    size--;
                    if (size == 0) printf("Wrong!");
                    else if (size % 2 == 1)
                        printf("%d",a[size/2]);
                    else{
                        if ((a[size/2]+a[(size/2)-1]) % 2 == 0)
                            printf("%ld",((long)a[size/2]+a[(size/2)-1])/2);
                        else 
                            printf("%1.1f",((signed long)a[size/2]+a[(size/2)-1])/2.0);
                    }
                    printf("\n");
                    found = 1;
                    break;
                }
            }
            if (!found) printf("Wrong!\n");
        }
   }
}

int main(){

//Helpers for input/output
   int i, N;

   scanf("%d", &N);
   char s[N];
   int x[N];
   

   for( i = 0; i  <  N; i++){
      scanf("%s %d", &(s[i]), &(x[i]));
   }
   
   median(N,s,x);
   
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>>
using namespace std;
void median(vector < char> s,vector<ll> X) {
    ll n=s.size();
    multiset m,m1;
    for(ll i = 0;i  <  n; i++){
        if(s[i]=='a'){
            if(m.size() == 0 || (*m.rbegin()) >= X[i]){
                m.insert(X[i]);
                if(m.size()-m1.size() == 2){
                    ll x = *m.rbegin();
                    m.erase(m.find(x));
                    m1.insert(x);
                }   
            }
            else {
                m1.insert(X[i]);
                if(m1.size()>m.size()){
                    ll x = *m1.begin();
                    m1.erase(m1.find(x));
                    m.insert(x);
                }
            }   
        }
        else{
            if(m.find(X[i]) == m.end() && m1.find(X[i]) == m1.end()){
                cout<<"Wrong!\n";
                continue;
            }
            else if(m.find(X[i]) != m.end()){
                m.erase(m.find(X[i]));
                if(m.size() < m1.size()){
                    ll x = *m1.begin();
                    m1.erase(m1.find(x));
                    m.insert(x);
                } 
            }
            else {
                m1.erase(m1.find(X[i]));
                if(m.size()-m1.size(> >= 2){
                    ll x = *m.rbegin();
                    m.erase(m.find(x));
                    m1.insert(x);
                }
            }
        }
        if(m.size() == 0 && m1.size() == 0) {
            cout<<"Wrong!\n";
            continue;
        }
        if(m1.size() == 0){
            cout << *m.rbegin() << endl;
            continue;
        }
        double db = ((m.size() > m1.size() ? *m.rbegin(): (*m.rbegin()+*m1.begin())/2.0));
        if(ceil(db) != db) cout << fixed << setprecision(1) << db << endl;
        else  cout << fixed << setprecision(0) << db<< endl;
    }
}
int main(void){
    ll N;
    cin >> N;
    
    vector < char> s;
    vector<ll> X;
    char temp;
    ll tempint;
    for(ll i = 0; i  <  N; i++){
        cin >> temp >> tempint;
        s.push_back(temp);
        X.push_back(tempint);
    }
    
    median(s,X);
    return 0;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - Java Programming


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

public class Solution {

    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 scanner = new Scanner(System.in) ;
        Integer n = scanner.nextInt() ;
        if (n  <  1 || n > 100000) {
            throw new IllegalArgumentException("1 <= n <= 100000") ;
        }

        DecimalFormat fmt = new DecimalFormat("#.#") ;
        SplitedNumberSet set = new SplitedNumberSet() ;
        for (int i=0;i < n;i++) {
            String operation = scanner.next() ;
            if (operation.equals("a") ) {
                set.addNum(scanner.nextInt());
            } else if  (operation.equals("r")) {
                if (!set.removeNum(scanner.nextInt())) {
                    System.out.println("Wrong!") ;
                    continue ;
                }
            } else {
                throw new IllegalArgumentException("Operation must be a or r") ;
            }
            Double median = set.getMedian() ;
            if (median != null) {
                //System.out.println(fmt.format(median)+" "+set) ;
                System.out.println(fmt.format(median)) ;
            } else {
                System.out.println("Wrong!") ;
            }
       }       
    }
    
    private static class SplitedNumberSet {
        private NumberSet smallSet = new NumberSet() ;
        private NumberSet largeSet = new NumberSet() ;
        
        public void addNum(Integer num) {
            if (smallSet.getLastNum() >= num) {
                smallSet.addNum(num) ;
            } else {
                largeSet.addNum(num) ;
            }
            balanceTree() ;
        }
        
        public boolean removeNum(Integer num) {
            boolean removed = false ;
            if (smallSet.getLastNum() >= num) {
                removed = smallSet.removeNum(num) ;
            } else {
                removed = largeSet.removeNum(num) ;
            }
            if (removed) {
                balanceTree() ;
            }
            return removed ;
        }
        
        public void balanceTree() {
            if (smallSet.getNumberCnt()-largeSet.getNumberCnt()>1) {
                // Push last number in smallSet to large
                Integer middleNum = smallSet.getLastNum() ;
                smallSet.removeNum(middleNum);
                largeSet.addNum(middleNum) ;
            } else if (largeSet.getNumberCnt()>smallSet.getNumberCnt()) {
                // Push first number in largeSet to small
                Integer middleNum = largeSet.getFirstNum() ;
                largeSet.removeNum(middleNum);
                smallSet.addNum(middleNum) ;
            }
         }
        
        
        public Double getMedian() {
            if (smallSet.getNumberCnt() < =0 && largeSet.getNumberCnt() <=0) {
                return null ;
            }

            if (smallSet.getNumberCnt() > largeSet.getNumberCnt()) {
                return (double)smallSet.getLastNum() ;
            } else if (smallSet.getNumberCnt()  <  largeSet.getNumberCnt()) {
                return (double)largeSet.getFirstNum() ;
            } else {
                return (((long)smallSet.getLastNum()+(long)largeSet.getFirstNum())/2d) ;
            }
        }
        
        public String toString() {
            return "small:"+smallSet+" large:"+largeSet ;
        }
    }
    
    private static class NumberSet {
        private SortedMap < Integer,Integer> map = new TreeMap() ;
        private int numberCnt = 0;

        public void addNum(Integer num) {
            if (map.containsKey(num)) {
                map.put(num,map.get(num)+1) ;
            } else {
                map.put(num,1) ;
            }
            numberCnt++ ;
        }

        public boolean removeNum(Integer num) {
            Integer current = map.get(num) ;
            if (current == null) {
                return false ;
            }
            if (current==1) {
                map.remove(num) ;
            } else {
                map.put(num,current-1) ;            
            }
            numberCnt-- ;
            return true ;
        }
        
        public Integer getFirstNum() {
            if (map.isEmpty()) {
                return Integer.MIN_VALUE ;
            }
            return map.firstKey() ;
        }
        
        public Integer getLastNum() {
            if (map.isEmpty()) {
                return Integer.MAX_VALUE ;
            }
            return map.lastKey() ;
        }
        
        public Integer getNumberCnt() {
            return numberCnt ;
        }
        
        public String toString() {
            return map+":"+numberCnt ;
        }
    }

}
Copy The Code & Try With Live Editor

#4 Code Example with Javascript Programming

Code - Javascript Programming


class MinHeap {
    constructor() {
        this.heap = [];
    }
    
    size() {
        return this.heap.length;
    }
    
    insert(x) {
        let i = this.heap.length;
        this.heap.push(x);
        this.siftUp(i);
    }
    
    pop() {
        if (this.heap.length === 1) {
            return this.heap.pop();
        }
        let top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.siftDown(0);
        return top;
    }
    
    remove(x) {
        let i = 0;
        while (i  <  this.heap.length && this.heap[i] !== x) {
            i++;
        }
        if (i === this.heap.length - 1) {
            this.heap.pop();
            return true;
        }else if (i >= this.heap.length) {
            return false;
        }
        this.heap[i] = this.heap.pop();
        if (this.heap[i]  <  this.heap[Math.floor((i-1)/2)]) {
            this.siftUp(i);
        }else {
            this.siftDown(i);
        }
        return true;
    }
    
    siftUp(i) {
        while (this.heap[Math.floor((i-1)/2)] > this.heap[i]) {
            let t = this.heap[Math.floor((i-1)/2)];
            this.heap[Math.floor((i-1)/2)] = this.heap[i];
            this.heap[i] = t;
            i = Math.floor((i-1)/2);
        }
    }
    
    siftDown(i) {
        while ((i*2+1  <  this.heap.length && this.heap[i] > this.heap[i*2+1]) ||
                (i*2+2 < this.heap.length && this.heap[i] > this.heap[i*2+2]))  {
            let t = this.heap[i];
            if (i*2+1 >= this.heap.length) {
                this.heap[i] = this.heap[i*2+2];
                this.heap[i*2+2] = t;
                i = i * 2 + 2;
            }else if (i*2+2 >= this.heap.length) {
                this.heap[i] = this.heap[i*2+1];
                this.heap[i*2+1] = t;
                i = i * 2 + 1;
            }else if (this.heap[i*2+1]  < = this.heap[i*2+2]) {
                this.heap[i] = this.heap[i*2+1];
                this.heap[i*2+1] = t;
                i = i * 2 + 1;
            }else {
                this.heap[i] = this.heap[i*2+2];
                this.heap[i*2+2] = t;
                i = i * 2 + 2;
            }
        }
    }
    
    peak() {
        return this.heap[0];
    }

    check() {
        for (let i = 0; i  <  Math.floor(this.heap.length/2); i++) {
            if (this.heap[i] > this.heap[i*2+1] || this.heap[i] > this.heap[i*2+2]) {
                return false;
            }
        }
        return true;
    }
}

class MaxHeap extends MinHeap {
    constructor() {
        super();
    }
    
    insert(x) {
        let i = this.heap.length;
        this.heap.push(x);
        this.siftUp(i);
    }
    
    pop() {
        if (this.heap.length === 1) {
            return this.heap.pop();
        }
        let top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.siftDown(0);
        return top;
    }
    
    remove(x) {
        let i = 0;
        while (i  <  this.heap.length && this.heap[i] !== x) {
            i++;
        }
        if (i === this.heap.length - 1) {
            this.heap.pop();
            return true;
        }else if (i >= this.heap.length) {
            return false;
        }
        this.heap[i] = this.heap.pop();
        if (this.heap[i] > this.heap[Math.floor((i-1)/2)]) {
            this.siftUp(i);
        }else {
            this.siftDown(i);
        }
        return true;
    }
    
    siftUp(i) {
        while (this.heap[Math.floor((i-1)/2)]  <  this.heap[i]) {
            let t = this.heap[Math.floor((i-1)/2)];
            this.heap[Math.floor((i-1)/2)] = this.heap[i];
            this.heap[i] = t;
            i = Math.floor((i-1)/2);
        }
    }
    
    siftDown(i) {
        while ((i*2+1  <  this.heap.length && this.heap[i] < this.heap[i*2+1]) ||
                (i*2+2 < this.heap.length && this.heap[i] < this.heap[i*2+2]))  {
            let t = this.heap[i];
            if (i*2+1 >= this.heap.length) {
                this.heap[i] = this.heap[i*2+2];
                this.heap[i*2+2] = t;
                i = i * 2 + 2;
            }else if (i*2+2 >= this.heap.length) {
                this.heap[i] = this.heap[i*2+1];
                this.heap[i*2+1] = t;
                i = i * 2 + 1;
            }else if (this.heap[i*2+1] >= this.heap[i*2+2]) {
                this.heap[i] = this.heap[i*2+1];
                this.heap[i*2+1] = t;
                i = i * 2 + 1;
            }else {
                this.heap[i] = this.heap[i*2+2];
                this.heap[i*2+2] = t;
                i = i * 2 + 2;
            }
        }
    }

    check() {
        for (let i = 0; i  <  Math.floor(this.heap.length/2); i++) {
            if (this.heap[i] < this.heap[i*2+1] || this.heap[i] < this.heap[i*2+2]) {
                console.log(i, this.heap[i]);
                return false;
            }
        }
        return true;
    }
}

class MedianHeap {
    constructor() {
        this.min = new MinHeap();
        this.max = new MaxHeap();
        this.size = 0;
    }
    
    size() {
        return this.size();
    }
    
    insert(x) {
        if (this.size === 0) {
            this.min.insert(x);
        }else if (this.size % 2 === 1) {
            if (x > this.min.peak()) {
                this.min.insert(x);
                this.max.insert(this.min.pop());
            }else {
                this.max.insert(x);
            }
        }else {
            if (x > this.min.peak()) {
                this.min.insert(x);
            }else {
                this.max.insert(x);
                this.min.insert(this.max.pop());
            }
        }
        this.size++;
    }
    
    remove(x) {
        if (this.min.size() > 0 && x >= this.min.peak()) {
            let r = this.min.remove(x);
            if (r) {
                this.size--;
                if (this.size % 2 === 1) {
                    this.min.insert(this.max.pop());
                }
            }
            return r;
        }else if (this.max.size() > 0 && x  < = this.max.peak()) {
            let r = this.max.remove(x);
            if (r) {
                this.size--;
                if (this.size % 2 === 0) {
                    this.max.insert(this.min.pop());
                }
            }
            return r;
        }else {
            return false;
        }
    }
    
    median() {
        if (this.size === 0) {
            return 'Wrong!';
        }else if (this.size % 2 === 1) {
            return this.min.peak();
        }else {
            return this.min.peak()/2 + this.max.peak()/2;
        }
    }
}

function processData(input) {
    let h = new MedianHeap();
    input = input.split('\n');
    input.shift();
    for (const s of input) {
        let n = parseInt(s.split(' ').pop());
        if (s[0] === 'a') {
            h.insert(n);
            console.log(h.median());
        }else {
            if (h.remove(n)) {
                console.log(h.median());
            }else {
                console.log('Wrong!');
            }
        }
    }
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});
Copy The Code & Try With Live Editor

#5 Code Example with Python Programming

Code - Python Programming


import bisect

N = int(input())
s = []
x = []
length = 0
for i in range(0, N):
   tmp = input().strip().split(' ')
   a, b = [xx for xx in tmp]
   b = int(b) 
   if(a=="a"):
    bisect.insort(x, b)
    length += 1
   else:
    index = bisect.bisect_left(x, b)
    if index != length and x[index] == b:
        del x[index]
        length -=1
    else:
        print ("Wrong!")
        continue

   if(length<=0):
    print ("Wrong!")
    continue 
    
   nforme, nfm = divmod(length,2>
   nforme -= 1
   if(nfm>0):
    nforme += 1
    print(x[nforme])
   else:
    nfm = nforme + 1
    median = x[nforme] + x[nfm]
    median /= 2
    if(round(median)==median):
        median = round(median);
    print(median)
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Array and simple queries solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Kundu and Tree solution in Hackerrank - Hacerrank solution C, C++, java,js, Python