# Java segment tree and binary indexed tree solution.

• ``````public class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, new Comparator<int[]>(){
public int compare(int[] p1, int[] p2){
if(p2[0] != p1[0]){
return p1[0] - p2[0];
}else{
return p2[1] - p1[1];
}
}
});

SegTree seg = new SegTree(people.length);

int[][] res = new int[people.length][2];
for(int[] person: people){
int idx = seg.getAndRemoveKth(person[1] + 1) - 1;
res[idx] = person;
}
return res;
}
}

class SegTree{
int[] st;
int[] arr;

public SegTree(int N){
arr = new int[N+1];	// 1: available  0: occupied
Arrays.fill(arr, 1);
arr[0] = 0;

int b = 1;
while(b < N+1){
b = b << 1;
}
st = new int[2*b-1];
constructUtil(0, N, 0);
}

private int constructUtil(int arrLo, int arrHi, int stIdx){
if(arrLo == arrHi){
st[stIdx] = arr[arrLo];
}else{
int mid = arrLo + (arrHi - arrLo) / 2;
st[stIdx] = constructUtil(arrLo, mid, 2 * stIdx + 1) + constructUtil(mid + 1, arrHi, 2 * stIdx + 2);
}
return st[stIdx];
}

public int getAndRemoveKth(int k){
int res = getKthUtil(0, arr.length - 1, k, 0);
arr[res] = 0;
removeKthUtil(0, arr.length - 1, res, 0);
return res;
}

private int getKthUtil(int arrLo, int arrHi, int k, int stIdx){
if(st[stIdx] == k && arr[arrHi] == 1){
return arrHi;
}
int mid = arrLo + (arrHi - arrLo) / 2;
if(st[2 * stIdx + 1] >= k){
return getKthUtil(arrLo, mid, k, 2 * stIdx + 1);
}else{
return getKthUtil(mid + 1, arrHi, k - st[2 * stIdx + 1], 2 * stIdx + 2);
}
}

private void removeKthUtil(int arrLo, int arrHi, int K, int stIdx) {
if(K < arrLo || arrHi < K){
return;
}
st[stIdx]--;
if(arrLo < arrHi){
int mid = arrLo + (arrHi - arrLo) / 2;
removeKthUtil(arrLo, mid, K, 2 * stIdx + 1);
removeKthUtil(mid + 1, arrHi, K, 2 * stIdx + 2);
}
}
}
``````
``````public class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, new Comparator<int[]>(){
public int compare(int[] p1, int[] p2){
if(p2[0] != p1[0]){
return p1[0] - p2[0];
}else{
return p2[1] - p1[1];
}
}
});

BITRQ bit = new BITRQ(people.length);

int[][] res = new int[people.length][2];
for(int[] person: people){
int idx = bit.getAndRemoveKth(person[1] + 1) - 1;
res[idx] = person;
}
return res;
}
}
class BITRQ{
private int[] bit;
public BITRQ(int N){		// empty: 1, occupied: 0
bit = new int[N+1];
for(int i = 0; i < N; i++){
set(i, 1);
}
}

public int getAndRemoveKth(int rank){
int ans = getRank(rank);
set(ans - 1, -1);
return ans;
}

private void set(int idx, int val){
for(idx++; idx < bit.length; idx += (idx & -idx)){
bit[idx] += val;
}
}

private int getRank(int rank){
int N = bit.length - 1, mask = 1;
}
int startIdx = 0;