# Java Binary Indexed Tree Solution

• Thanks for @markxyb , I learnt from the python BIT solution and create this Java version.

There is one point critical here :
when sort the [x, i/o, idx] array, for entries with same 'x' value, put 'in' before 'out'

My understand of the BIT solution:

1. Sort [x, i/o, idx] from left to right, and deal them one by one
i. If this is an 'in'(left) bound, use the related right to set hight for left points according to BIT; Then find the highest after 'in'.
ii. If this is an 'out'(right) bound, find the highest after 'out'.
2. Use HashMap to reduce lost of space and time: If the range of x_min to x_max is too large with lots of useless points (points without x_bound on it), use HashMap could reduce the space and also the time used for BIT.
3. There must be a value VAL between any (2^n+k1) and (2^n+k2) (0<=k1<k2<=2^n), which:
i. (2^n+k1) can reach VAL by adding its last bit and change value continuously
ii. (2^n+k2) can reach VAL by reducing its last bit and change value continuously
``````public class Solution {
private int[] biTree;

private void add(int r, int h) { // here r is in the reduced array
while (r > 0) {
biTree[r] = Math.max(biTree[r], h);
r -= r & (-r);
}
}

private int find(int l) { // here l is in the reduced array
int ret = 0;
while (l < biTree.length) {
ret = Math.max(ret, biTree[l]);
l += l & (-l);
}
return ret;
}

public List<int[]> getSkyline(int[][] buildings) {
List<int[]> list = new ArrayList<int[]>();

int[][] xidx = new int[buildings.length * 2][3]; // array of [x, i/o, idx]
for (int i = 0; i < buildings.length; i++) {
xidx[2 * i] = new int[] {buildings[i][0], 1, i}; // in
xidx[2 * i + 1] = new int[] {buildings[i][1], 2, i}; // out
}

Arrays.sort(xidx, (a,b) -> {
if (a[0] != b[0])
return a[0] - b[0]; // sort from left to right
else return a[1] - b[1]; // in before out; otherwise, <out, 0> will be add to the list and cause problem
});

HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int num = 0;
for (int[] x : xidx) {
map.put(x[0], ++num); // map of (x : number), to reduce space usage
}
biTree = new int[num + 1];

int l, r, h;
int curhigh = 0; // start hight
for (int[] x : xidx) {
if (x[1] == 1) { // left side of a building
l = buildings[x[2]][0];
r = buildings[x[2]][1];
h = buildings[x[2]][2];
} else {
l = buildings[x[2]][1]; // assign r to l, to find hight after the building end
}

int tmp = find(map.get(l) + 1); // find the highest after

if (tmp != curhigh) {
int size = list.size();
if (size > 0 && list.get(size - 1)[0] == l) { // 2 hight with the same x
curhigh = list.get(size - 1)[1] = Math.max(tmp, list.get(size - 1)[1]);
} else {