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

• 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)))
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]
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``````

• This post is deleted!

• +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?

• 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.

• 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]

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]).

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

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

• 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];
}

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]];
}
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 {
}
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;
}
``````

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

• 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.

• Short BIT solution with comments and O(nlgn) complexity where n is the number of buildings.

``````    def getSkyline(self, buildings):
def update(p, h):
while p > 0: # scope of h is towards left
bit[p] = max(bit[p], h)
p -= p & -p
def query(p):
ret = 0
while p <= len(bit): # check anything to the right that has a higher value
ret = max(ret, bit[p])
p += p & -p
return ret

ret, ends, points = [], {}, []
for i, b in enumerate(buildings):
points += ((b[0], -1, -b[2]), (b[1], 1, -b[2]))
ends[points[-2]] = points[-1]

bit = [0] * (len(points) + 1)
points.sort()
idx = {points[i]: i for i in range(len(points))} # keep sorted index

for i, p in enumerate(points):
if p[1] == -1:
end = ends[p]
update(idx[end], -p[-1]) # end idx is exclusive
h = query(i+1) # start idx is inclusive
if not ret or ret[-1][1] != h:
if ret and ret[-1][0] == p[0]:
ret[-1][1] = h
else:
ret.append([p[0], h])
return ret
``````

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