My O(nlogn) solution using Binary Indexed Tree(BIT)/Fenwick Tree


  • 7
    M

    we can use Binary Indexed Tree(BIT)/Fenwick Tree to solve this problem, the (Value and (Value xor (Value - 1))), O(nlogn) Solution:

    class Solution:
    # @param {integer[][]} buildings
    # @return {integer[][]}
    def CalcBit(self,Value):
        return (Value & (Value ^(Value -1)))
    def Add(self,R,H):
        while R > 0:
            self.TreeCount[R] = max(self.TreeCount[R],H)
            R -= self.CalcBit(R)
    def Find(self,L):
        Ret = 0
        while L <= self.INT_MAX:
            Ret =max(self.TreeCount[L],Ret)
            L += self.CalcBit(L)
        return Ret
    def getSkyline(self, buildings):
        Ret = []
        High_Now = 0
        TB = []
        for x in range(len(buildings)):
            TB.append([buildings[x][0],1,x])
            TB.append([buildings[x][1],2,x])
        TB.sort()
        Dict = {}
        ToT = 0
        for Num in TB:
            if Num[0] not in Dict:
                ToT += 1
                Dict[Num[0]] = ToT
        self.INT_MAX = ToT + 10
        self.TreeCount = [0 for x in range(self.INT_MAX+1)]
        for Num in TB:
            if Num[1] == 1:
                L = buildings[Num[2]][0]
                R = buildings[Num[2]][1]
                H = buildings[Num[2]][2]
                self.Add(Dict[R],H)
            else:
                L = buildings[Num[2]][1]
            Temp = self.Find(Dict[L]+1)
            if Temp != High_Now:
                if (len(Ret)>0)and(Ret[-1][0] == L):
                    Ret[-1][1] = max(Ret[-1][1],Temp)
                else:
                    Ret.append([L,Temp])
                High_Now = Temp
        return Ret

  • 0
    W
    This post is deleted!

  • 0
    C

    +1 for posting solution using a unique data structure. I haven't studied Fenwick trees before. Do you have pointers to any good resources/tutorials on this?


  • 1

  • 0
    J

    So Clever! Amazing solution! Could you add more explanation for your solution? I feel it's hard to understand although I could implement Binary Search Tree and solved several problems by it. Thank you sooo much to provide your code.


  • 0
    P

    Took a while for me to get to understand the code.

    for Num in TB:
    if Num[0] not in Dict:
    ToT += 1
    Dict[Num[0]] = ToT

    After sorting the points, we are indexing the points to be used in Fenwick tree.

    if Num[1] == 1:
    L = buildings[Num[2]][0]
    R = buildings[Num[2]][1]
    H = buildings[Num[2]][2]
    self.Add(Dict[R],H)

    If we encounter a point which is the start point of a building, we check for its the building's end point and propagate the max height towards its Parent in Fenwick tree. That is to look for all the points to the left of the scan line from the current point. (Since the Parent point is the cumulative keeper of all the points from index 0 to that point)

    Temp = self.Find(Dict[L]+1)
    if Temp != High_Now:
    Now find the max height to the right of the current point. Buildings after the current buildings scan line. To say, if the current point is overshadowed by any other building's end point)

    if it is not over-shadowed, then append it to the result.
    Ret.append([L,Temp]).


  • 0
    J

    @markxyb this solution is brilliant but why no one upvote it?


  • 0

    Inspiring solution! But I think the runtime complexity is O(nlogN) not O(nlogn), where N is the max index (INT_MAX).


  • 0
    D

    Rewrite in Java with explanations in comments

        public List<int[]> getSkyline(int[][] buildings) {
            List<int[]> ret = new ArrayList<>();
            if (buildings.length==0) return ret;
            
            List<int[]> points = new ArrayList<>();
            
            for (int i=0;i<buildings.length;i++) {
                int[] b = buildings[i];
                points.add(new int[]{b[0], 1, i});
                points.add(new int[]{b[1], 2, i});
            }
            
            Collections.sort(points, (a,b)->a[0]==b[0]?a[1]-b[1]: a[0]-b[0]);
            // binary indexed tree
            // stores the max height for each segment, bit[i] is the max height of segment between point i-1 and i
            int[] bit = new int[points.size()+1];
            
            Map<Integer, Integer> index = new HashMap<>();
            for (int i=0;i<points.size();i++) {
                index.putIfAbsent(points.get(i)[0], i);
            }
            
            int prevHeight = -1;
            
            for (int i=0;i<points.size();i++) {
                int[] pt = points.get(i);
                if (pt[1]==1) {
                    // start of a building
                    // put height in scope, scope ends when building end
                    int[] building=buildings[pt[2]];
                    add(bit, index.get(building[1]), building[2]);
                }
                int cur = find(bit, index.get(pt[0])+1);
                if (cur!=prevHeight) {
                    if (ret.size()>0 && ret.get(ret.size()-1)[0]==pt[0]) {
                        ret.get(ret.size()-1)[1] = Math.max(cur, ret.get(ret.size()-1)[1]);
                    } else {
                        ret.add(new int[]{pt[0], cur});    
                    }
                    prevHeight=cur;
                }
            }
            
            return ret;
        }
        
        void add(int[] bit, int i, int h) {
            while (i>0) {
                bit[i]=Math.max(bit[i], h);
                i-=(i&-i);
            }
        }
        int find(int[] bit, int i) {
            int h=0;
            while (i<bit.length) {
                h=Math.max(h, bit[i]);
                i+=(i&-i);
            }
            return h;
        }
    

  • 0
    G

    @feyhi INT_MAX = ToT + 10, where ToT is count of unique L and unique R, so it is nlogn


  • 0
    L

    Indeed, using Binary Index Tree to solve it is interesting, but the code is poorly written, should add more comments and use variables with self-explained names.


Log in to reply
 

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