HackerRank Inverse RMQ problem solution

In this HackerRank Inverse RMQ problem solution, we have given an array of distinct integers with size n = 2k and m queries. we need to find the minimum element on subsegment [Li, Ri].

One of the most efficient and famous solutions to this problem is a segment tree. A segment tree is a full binary tree with 2.n-1 nodes where the leaves contain the values of the original array and each non-leaf node contains the minimum value of its entire subtree.

Input Format

The first line contains a single integer, n, denoting the size of the array.
The second line contains 2.n-1 space-separated integers denoting the shuffled values of the segment tree.

Problem solution in Python.

import sys
import heapq

n = int(input())
a = list(map(int, input().split()))
freq = dict()
for i in a:
    if i not in freq:
        freq[i] = 0
    freq[i] += 1
if len(freq) < n:
    print("NO")
    sys.exit()
exp_freq = 1
depth = 1
while 2**(depth - 1) < n:
    depth += 1
prev = dict()
ans = [0] * (n + n - 1)
while exp_freq <= n:
    v = list()
    v1 = list()
    for key in prev:
        v1.append((key, prev[key]))
    for key in freq:
        if freq[key] == depth:
            v.append(key)
    if len(prev) == 0:
        ans[0] = v[0]
        prev[v[0]] = 0
        freq[v[0]] -= 1
        exp_freq *= 2
        depth -= 1
        continue
    v.sort()
    v1.sort()
    cur = exp_freq // 2 - 1
    pq = list()
    j = 0
    for i in v:
        if i in prev:
            ans[prev[i] * 2 + 1] = i
            prev[i] = prev[i] * 2 + 1
            freq[i] -= 1
        else:
            while j < len(v1):
                if v1[j][0] < i:
                    heapq.heappush(pq, v1[j][1])
                    j += 1
                else:
                    break
            if len(pq) == 0:
                print("NO")
                sys.exit()
            temp = heapq.heappop(pq)
            ans[temp * 2 + 2] = i
            prev[i] = temp * 2 + 2
            freq[i] -= 1
    exp_freq *= 2
    depth -= 1
print("YES")
for i in ans:
    print(i, end=" ")

Inverse RMQ problem solution in Java.

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.HashMap;
import java.io.IOException;
import java.io.Reader;
import java.io.InputStreamReader;
import java.util.TreeSet;
import java.util.TreeMap;
import java.util.StringTokenizer;
import java.util.Map;
import java.util.Map.Entry;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Solution {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        InversedRMQ solver = new InversedRMQ();
        solver.solve(1, in, out);
        out.close();
    }

    static class InversedRMQ {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.readInt();
            int k = 2 * n - 1;
            final Map<Integer, Integer> count = new TreeMap<>();
            for (int i = 0; i < k; i++) {
                int x = in.readInt();
                count.put(x, count.getOrDefault(x, 0) + 1);
            }
            final TreeSet<Integer>[] types = new TreeSet[k + 1];
            final Map<Integer, Integer> result = new HashMap<>();
            for (int i = 0; i < types.length; i++) {
                types[i] = new TreeSet<>();
            }
            int log = 0, n_ = n;
            while (n_ > 0) {
                n_ >>= 1;
                log++;
            }
            types[log].add(1);
            for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
                if (types[entry.getValue()].isEmpty()) {
                    out.printLine("NO");
                    return;
                }
                int wh = types[entry.getValue()].pollFirst();
                result.put(entry.getKey(), wh);
                for (int i = 0; i < entry.getValue() - 1; i++) {
                    types[entry.getValue() - i - 1].add(wh * 2 + 1);
                    wh <<= 1;
                }
            }
            final int[] ans = new int[k + 1];
            for (Map.Entry<Integer, Integer> entry : result.entrySet()) {
                int wh = entry.getValue(), value = entry.getKey();
                while (wh <= k) {
                    ans[wh] = value;
                    wh <<= 1;
                }
            }
            out.printLine("YES");
            for (int i = 1; i <= k; i++) {
                out.print(ans[i], ' ');
            }
            out.printLine();
        }

    }

    static class OutputWriter {
        private PrintWriter writer;

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public OutputWriter(OutputStream stream) {
            this(new OutputStreamWriter(stream));
        }

        public void print(Object... args) {
            for (Object arg : args) {
                writer.print(arg);
            }
        }

        public void printLine(Object... args) {
            print(args);
            writer.println();
        }

        void close() {
            writer.close();
        }

    }

    static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(Reader reader) {
            this.reader = new BufferedReader(reader);
        }

        public InputReader(InputStream stream) {
            this(new InputStreamReader(stream));
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public String readWord() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(nextLine());
            }
            return tokenizer.nextToken();
        }

        public int readInt() {
            return Integer.parseInt(readWord());
        }

    }
}

Problem solution in C++.

#include<bits/stdc++.h>
using namespace std;
void Q(){
    cout << "NO" << endl;
    exit(0);
}
set<int> Adj[(1 << 21)];
int Ar[(1 << 20)] , X , nn;
vector<int> Ans[(1 << 20)];
void build(int lvl , int V , bool F){
    if(lvl == nn)return ;
    set<int> :: iterator no = Adj[lvl].upper_bound(V);
    if(F && (no == Adj[lvl].end() || *no <= V)){
        Q();
    }
    if(F){
        int x = *no;
        Ans[lvl].push_back(x);
        Adj[lvl].erase(no);
        build(lvl + 1 , x , 0);
        build(lvl + 1 , x , 1);
    }
    else {
        Ans[lvl].push_back(V);
        build(lvl + 1 , V , 0);
        build(lvl + 1 , V , 1);
    }
}
int main()
{
    int n;
    cin >> n;
    vector<int> A(2 * n - 1);
    map<int , int > mp ;
    map<int , set<int> > mp1;
    if(n == 1){
        cin >> n;
        cout << "YESn" << n << endl;;
        return 0;
    }
    int N = 2 * n - 1 , mx = 0 , idx = 0;
    for(int i = 0 ;i < N ; i ++){
        cin >> A[i] , mp[A[i]] ++;
        if(mp[A[i]] > mx)
            mx = mp[A[i]] , idx = A[i];
    }
    //if(mp.begin() -> first != idx)  Q();
    set<int> S;
    for(int i = 0 ;i < N ;i ++)
        mp1[mp[A[i]]].insert(A[i]),  S.insert(A[i]);
    for(int m = n / 2 , x = 1; m ; m >>= 1 , x ++){
        if(mp1[x].size() != m)
            Q();
    }
    for(auto no : S)
        Adj[mx - mp[no] + 1].insert(no);
    nn = mx + 1 ;
    int KK = *Adj[1].begin();
    Adj[1].erase(Adj[1].begin());
    build(1 , KK , 0);
    cout << "YESn";
    for(int i = 1; i <= mx ;i ++)
        for(int l = 0; l < Ans[i].size() ;l ++)
            cout << Ans[i][l] << " ";

}

Problem solution in C.

#include <assert.h>
#include <stddef.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();
char** split_string(char*);

int* canTree(int n, int* arr){
    int logn = 0;
    while(n >> logn > 1){
        logn++;
    }

    int sortarr[2*n - 1];
    for(int i = 0; i < 2*n - 1; i++){
        sortarr[i] = arr[i];
        int curr = i;
        int inplace = 0;
        while(curr > 0 && inplace == 0){
            int next = (curr - 1)/2;
            if(sortarr[next] < sortarr[curr]){
                int temp = sortarr[curr];
                sortarr[curr] = sortarr[next];
                sortarr[next] = temp;
                curr = next;
            }
            else{
                inplace = 1;
            }
        }
    }

    for(int i = 0; i < 2*n - 1; i++){
        int temp = sortarr[0];
        sortarr[0] = sortarr[2*n - i - 2];
        sortarr[2*n - i - 2] = temp;

        int curr = 0;
        int reheaped = 0;
        while(reheaped == 0){
            int next = curr;
            if(2*curr + 1 < 2*n - i - 2 && sortarr[2*curr + 1] > sortarr[next]){
                next = 2*curr + 1;
            }
            if(2*curr + 2 < 2*n - i - 2 && sortarr[2*curr + 2] > sortarr[next]){
                next = 2*curr + 2;
            }
            if(next != curr){
                temp = sortarr[curr];
                sortarr[curr] = sortarr[next];
                sortarr[next] = temp;
                curr = next;
            }
            else{
                reheaped = 1;
            }
        }
    }

    int *levellist[logn + 1];
    int numatlevel[logn + 1];
    int **numopen[logn + 1];
    for(int i = 0; i <= logn; i++){
        levellist[i] = malloc((1<<i)*sizeof(int));
        assert(levellist[i] != NULL);
        for(int j = 0; j < 1<<i; j++){
            levellist[i][j] = INT_MIN;
        }
        numopen[i] = malloc((1<<i)*sizeof(int*));
        assert(numopen[i] != NULL);
        for(int j = 0; j <= (1<<i); j++){
            numopen[i][j] = malloc((logn + 1)*sizeof(int));
            assert(numopen[i][j] != NULL);
            for(int k = 0; k <= logn; k++){
                numopen[i][j][k] = 0;
            }
        }
        numatlevel[i] = 0;
    }
    numopen[0][0][0] = 1;
    

    

    int index = 0;
    while(index < 2*n - 1){
        int currval = sortarr[index];
        int currindex = index;
        while(index < 2*n - 1 && sortarr[index] == currval){
            index++;
        }
        int numreps = index - currindex;
        int level = (logn + 1) - numreps;
        int pos = 0;
        if(level < 0 || numopen[0][0][level] == 0){
            return NULL;
        }
        for(int i = 0; i < level; i++){
            assert(numopen[i][pos][level] > 0);
            numopen[i][pos][level] -= 1;
            for(int j = level + 1; j <= logn; j++){
                numopen[i][pos][j] += 1;
            }
            if(i + 1 < level && numopen[i + 1][2*pos][level] > 0){
                pos = 2*pos;
            }
            else{
                pos = 2*pos + 1;
            }
        }
        for(int i = level; i <= logn; i++){
            levellist[i][pos] = currval;
            for(int j = i + 1; j <= logn; j++){
                numopen[i][pos][j] += 1;
            }
            pos = 2*pos;
        }
    }

    int *toreturn = malloc((2*n - 1)*sizeof(int));
    assert(toreturn != NULL);
    index = 0;
    for(int i = 0; i <= logn; i++){
        for(int j = 0; j < (1<<i); j++){
            toreturn[index] = levellist[i][j];
            index++;
        }
    }
    
    return toreturn;
}

int main() {
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    char* n_endptr;
    char* n_str = readline();
    int n = strtol(n_str, &n_endptr, 10);

    if(n_endptr == n_str || *n_endptr != ''){ exit(EXIT_FAILURE);}
    
    char** vals_str = split_string(readline());
    int *treelist = malloc((2*n - 1) * sizeof(int));

    for(int i = 0; i < 2*n - 1; i++){
        char* currval_str = vals_str[i];
        char* currval_endptr;
        int currval = strtol(currval_str, &currval_endptr, 10);

        if(currval_endptr == currval_str || *currval_endptr != ''){ exit(EXIT_FAILURE);}
        treelist[i] = currval;
    }
    int* arrlist = canTree(n, treelist);
    if(arrlist == NULL){
        fprintf(fptr, "NO");
    }
    else{
        fprintf(fptr, "YESn");
        for(int i = 0; i < 2*n - 2; i++){
            fprintf(fptr, "%d ", arrlist[i]);
        }
        fprintf(fptr, "%d", arrlist[2*n - 2]);
    }   
    return 0;
}


char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == 'n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == 'n') {
        data[data_length - 1] = '';
    }
    if(data[data_length - 1] != ''){
        data_length++;
        data = realloc(data, data_length);
        data[data_length - 1] = '';
    }

    data = realloc(data, data_length);

    return data;
}

char** split_string(char* str) {
    char** splits = NULL;
    char* token = strtok(str, " ");

    int spaces = 0;

    while (token) {
        splits = realloc(splits, sizeof(char*) * ++spaces);
        if (!splits) {
            return splits;
        }

        splits[spaces - 1] = token;

        token = strtok(NULL, " ");
    }

    return splits;
}