Java Binary Indexed Tree Solution


  • 2
    J

    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];
                    add(map.get(r), h);
                } 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 {
                        list.add(new int[]{l, tmp});
                        curhigh = tmp;
                    }
                }
            }
            return list;
        }
    }

  • 0
    Y

    I think you can directly delete the last one in result when you deal with many different height correspond to the same point.Do that your code will more cleaner.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.