Table of Contents
Inverse RMQ – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Inverse RMQ HackerRank Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
const int INF=1001001001001001001ll;
int N;
priority_queue<int,vint,greater<int>>cand[20];
int A[1<<19];
signed main(){
scanf("%lld",&N);
map<int,int>mp;
rep(i,2*N-1){
int a;
scanf("%lld",&a);
mp[a]++;
}
vpint vec;
each(it,mp)vec.pb(*it);
fill_n(A,1<<19,INF);
if(vec.size()!=N||vec[0].se>=20||(1<<vec[0].se)!=N*2){
puts("NO");
return 0;
}
cand[vec[0].se].push(0);
rep(i,N){
int t=vec[i].se;
if(t>=20){
puts("NO");
return 0;
}
while(cand[t].size()&&A[cand[t].top()]!=INF)cand[t].pop();
if(cand[t].size()==0){
puts("NO");
return 0;
}
int k=cand[t].top();cand[t].pop();
while(true){
A[k]=vec[i].fi;
if(k>=N-1)break;
t--;
cand[t].push(k*2+2);
k=k*2+1;
}
}
puts("YES");
rep(i,2*N-1){
if(i)printf(" ");
printf("%lld",A[i]);
}
puts("");
return 0;
}
Java Inverse RMQ HackerRank Solution
import java.io.*;
import java.util.*;
import java.util.Scanner;
import java.util.stream.Collectors;
public class Solution {
private static ArrayList<Integer> solve(ArrayList<Integer> A, int N) {
int H = 1;
{
int x = N;
while (x > 1) {
assert x % 2 == 0;
H += 1;
x /= 2;
}
}
Map<Integer, Integer> d = new HashMap<>();
for (int y : A) {
d.put(y, d.getOrDefault(y, 0) + 1);
}
int n = N;
ArrayList<ArrayList<Integer>> levels = new ArrayList<>();
for (int h = H - 1; h >= 0; h--) {
levels.add(null);
}
for (int h = H - 1; h >= 0; h--) {
if (d.size() != n) {
return null;
}
ArrayList<Integer> elems = new ArrayList<>(d.size());
elems.addAll(d.keySet());
int min_el = Collections.min(elems);
if (d.get(min_el) != h + 1) {
return null;
}
levels.set(h, elems);
for (int x : elems) {
d.put(x, d.get(x) - 1);
if (d.get(x) == 0) {
d.remove(x);
}
}
n = n / 2;
}
n = 2;
for (int h = 1; h < H; h++) {
ArrayList<Integer> pelems = levels.get(h - 1);
Set<Integer> dset = new HashSet<>(levels.get(h));
dset.removeAll(pelems);
TreeSet<Integer> delems = new TreeSet<>(dset);
ArrayList<Integer> elems = new ArrayList<>(n);
for (int le : pelems) {
Integer re = delems.ceiling(le);
if (re == null) {
return null;
}
elems.add(le);
elems.add(re);
delems.remove(re);
}
levels.set(h, elems);
n = n * 2;
}
ArrayList<Integer> T = new ArrayList<>();
for (int h = 0; h < H; h++) {
T.addAll(levels.get(h));
}
return T;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
ArrayList<Integer> A = new ArrayList<>();
for (int i = 0; i < 2*N-1; i++) {
A.add(scanner.nextInt());
}
// System.out.println(A);
ArrayList<Integer> sol = Solution.solve(A, N);
if (sol == null) {
System.out.println("NO");
} else {
System.out.println("YES");
String buf = sol.stream()
.map(Object::toString)
.collect(Collectors.joining(" "));
System.out.println(buf);
}
}
}
Python 3 Inverse RMQ HackerRank Solution
import sys
from bisect import bisect_right
def z(a, b):
B = sorted(b)
r = []
for i in range(len(a)):
ind = bisect_right(B, a[i])
r += [a[i], B[ind]]
del B[ind]
#print(a, b, r)
return r
n = int(input())
nl = 0
x = n
while x:
nl += 1
x >>= 1
a = list(map(int,input().split()))
occ = {}
for e in a:
if not e in occ:
occ[e] = 0
occ[e] += 1
# test #############
cnt_occ = {}
for i, v in occ.items():
if not v in cnt_occ:
cnt_occ[v] = 0
cnt_occ[v] += 1
for i in range(1, nl):
if not i in cnt_occ or cnt_occ[i] != (1 << (nl - 1 - i)):
print('NO')
sys.exit(0)
#####################
ah = [[] for _ in range(nl + 2)]
for i, v in occ.items():
ah[v].append(i)
sofar = ah[nl]
res = list(sofar)
for i in range(1, nl):
sofar = z(sofar, ah[nl - i])
res += sofar
print('YES')
print(' '.join(map(str,res)))
Python 2 Inverse RMQ HackerRank Solution
#! /usr/bin/python
import collections
def build_segtree(a):
v=[0 for x in range(2*len(a)-1)]
for i in range(len(a)):
v[len(a)-1+i]=a[i]
n=len(a)/2
p=len(a)-1
while n>0:
p -= n
for i in range(n):
v[p+i]=min(v[2*(p+i)+1],v[2*(p+i)+2])
n /= 2
return v
def verify_segtree(a,b):
a2=build_segtree(b)
for x,y in zip(a,a2):
if x != y:
return False
return True
def reconstruct(a):
cnt={}
for e in a:
if e in cnt:
cnt[e]+=1
else:
cnt[e]=1
l=[]
for k in cnt:
l.append( (cnt[k],k) )
if (len(l)*2-1) != len(a):
return []
n=1
re=[]
l.sort(key=lambda x:x[1])
l.sort(key=lambda x:x[0],reverse=True)
re=[None for x in a]
p=0
l=collections.deque(l)
while p<len(a):
if re[p] == None:
if len(l) == 0:
return []
x,y=l.popleft()
p2=p
for i in range(x):
if (p2 > len(a)):
return []
while (re[(p2-1)/2] > y) or (re[p2] != None):
p2+=2
if p2 >= len(a):
return []
re[p2]=y
p2=p2*2+1
else:
p+=1
if not verify_segtree(re,re[len(cnt)-1:] ):
return []
return re
n=int(raw_input().strip())
st=map(int,raw_input().strip().split())
a=reconstruct(st)
if len(a) == 0:
print "NO"
else:
print "YES"
print " ".join(map(str,a))
C Inverse RMQ HackerRank Solution
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
