218. The Skyline Problem #

Problem #

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of “key points” (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

• The number of buildings in any input list is guaranteed to be in the range [0, 10000].
• The input list is already sorted in ascending order by the left x position Li.
• The output list must be sorted by the x position.
• There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]

Summary #

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now, suppose you are given the locations and heights of all the buildings shown in a cityscape photo (Figure A). Write a program to output the skyline formed by these buildings (Figure B).

The geometric information of each building is represented by a triplet [Li, Ri, Hi], where Li and Ri are the x-coordinates of the left and right edges of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles on an absolutely flat surface at height 0.

For example, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ].

The output is a list of “key points” (red dots in Figure B) in the format [ [x1,y1], [x2, y2], [x3, y3], … ], which uniquely defines the skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is only used to mark the termination of the skyline and always has height zero. In addition, the ground between any two adjacent buildings should be considered part of the skyline contour.

For example, the skyline in Figure B should be represented as: [ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

• The number of buildings in any input list is guaranteed to be in the range [0, 10000].
• The input list is already sorted in ascending order by the left x-coordinate Li.
• The output list must be sorted by the x position.
• There must be no consecutive horizontal lines of the same height in the output skyline. For example, […[2 3], [4 5], [7 5], [11 5], [12 7]…] is not a correct answer; the three lines of height 5 should be merged into one in the final output as: […[2 3], [4 5], [12 7], …]

Solution Ideas #

• Given a two-dimensional array, each subarray represents the information of a high-rise building. The information of a building contains 3 values: the building’s starting coordinate, ending coordinate, and height. The task is to find the boundary points of these buildings and output the height information of these boundary points.

• This problem can be solved with a Binary Indexed Tree. To obtain the skyline, we need to find the lines along the outer edges of overlapping intervals between buildings; in other words, we need to maintain the maximum value within each interval. There are 2 issues to solve.

  1. How to maintain the maximum value. When the right boundary of a tall building disappears, among the remaining smaller buildings we still need to choose the maximum value as the skyline. There may be many remaining overlapping smaller buildings, so how a Binary Indexed Tree maintains the maximum value over intervals is the key to solving this kind of problem.
  2. How to maintain the turning points of the skyline. Some buildings do not completely overlap; partial overlap causes turning points in the skyline, such as the red turning points marked in the figure above. How can a Binary Indexed Tree maintain these points?

• First solve the first problem (maintaining the maximum value). A Binary Indexed Tree has only 2 operations: Add() and Query(). From the explanation above about these 2 operations, we can see that neither operation can satisfy our needs. The Add() operation can be changed to maintain max() within an interval. However, max() is easy to obtain but difficult to “remove”. For example, in the figure above, the maximum value in the interval [3,7] is 15. According to the definition of a Binary Indexed Tree, the maximum value in the interval [3,12] is still 15. Observing the figure above, we can see that the maximum value in the interval [5,12] is actually 12. How can a Binary Indexed Tree maintain this kind of maximum value? Since the maximum value is difficult to “remove”, we need to consider how to make the maximum value “arrive later”. The solution is to change the meaning of the Query() operation from a prefix meaning to a suffix meaning. Query(i) originally queries the interval [1,i]; now the query interval becomes \([i,+\infty)\) . For example: the maximum value in the interval [i,j] is \(max_{i...j}\) , and the result of Query(j+1) will not include \(max_{i...j}\) , because its query interval is \([j+1,+\infty)\) . After this change, we can effectively avoid the influence of preceding tall buildings on the accumulated max() value of later buildings. The specific approach is to sort all intervals on the x-axis in ascending order by x value, then traverse the intervals from left to right. The meaning of the Add() operation is to add the maximum value of the suffix interval represented by each interval’s right boundary. This way, there is no need to consider the problem of “removing” the maximum value. Careful readers may have another question: can we traverse intervals from right to left and keep the meaning of Query() as a prefix interval? This is feasible and can solve the first problem (maintaining the maximum value). However, this approach will encounter trouble when solving the second problem (maintaining turning points).

• Next solve the second problem (maintaining turning points). If we use Query() with prefix meaning, at a single point i, in addition to considering intervals ending at this point, we also need to consider intervals starting at this single point i. If we use Query() with suffix meaning, there is no such problem; in the interval \([i+1,+\infty)\) , we do not need to consider intervals ending at the single point i. The Binary Indexed Tree implementation for this problem is shown in Solution 1 below.

• This problem can also be solved with a segment tree. With a segment tree, there is no need to care about the situation where “one building blocks another”. Since building coordinates are discrete, first discretize the two coordinates of each building on the X-axis. As in Problem 699, the width of a building is an interval, but during discretization, the right boundary of the building’s width needs to be decremented by one; otherwise, querying an interval will include two points and lead to an incorrect result. For example, the first building is [1,3) with height 10, and the second building is [3,6) with height 20. If the first building includes the right boundary 3, querying [1,3] gives a result of 20, because the point [3,3] will be queried on top of the second building. Therefore, the right boundary of each building should be decremented by one. However, each building’s right boundary also needs to be included in the query, because the final query result needs to include these boundaries. After sorting the discretized data, update each interval according to the building information. Finally, when collecting the results, check each interval in order. If the height of the current interval is the same as the previous interval, it counts as buildings of equal height. When the height differs from the previous height, it is considered an edge of the skyline and should be added to the final output array.

• Similar segment tree problems include: Problem 715, Problem 732, and Problem 699. Problem 715 is interval update to a fixed value (not increment/decrement). Problem 218 can be solved with a sweep line. Problems 732 and 699 are similar and are also Tetris-like problems, but in Problem 732 the Tetris blocks can “break apart”.

• Solving this problem with a segment tree has somewhat high time complexity, so a sweep line can be used. The idea of a sweep line is very simple: use vertical lines perpendicular to the X-axis and sweep from the far left to the far right, scanning each building boundary. When entering the left boundary of a building, if there is no point higher than the highest point of this left boundary, record this highest point as a keyPoint, with the state being entering. If we scan the left boundary of a building and there is a higher height, do not record it, because it is not part of the skyline; it is blocked by another building behind it. When scanning the right boundary of a building, if it is the highest point, record its state as leaving, and at this time also record the second-highest point. During the sweep line process, dynamically maintain the heights of buildings, while maintaining the highest height and the second-highest height. In fact, we only need to maintain the highest height, because when a leaving state occurs, after removing the current highest height, the highest among the remaining heights is the second-highest height. The pseudocode is as follows:

    // Sweep line pseudocode
    events = {{x: L , height: H , type: entering},
              {x: R , height: H , type: leaving}}
    event.SortByX()
    ds = new DS()
      
    for e in events:
        if entering(e):
            if e.height > ds.max(): ans += [e.height]
            ds.add(e.height)
        if leaving(e):
            ds.remove(e.height)
            if e.height > ds.max(): ans += [ds.max()]
  

• Data structures that can be used for dynamic insertion and finding the maximum include max heaps and binary search trees. A max heap finds the maximum in O(1) and inserts in O(log n), but remove_by_key requires O(n) time complexity and needs to be implemented manually. For a binary search tree, finding max, adding, and deleting elements are all O(log n) time complexity.

• Several issues also need attention when sorting: if building boundaries are equal and the state is entering, then sort by height from high to low; if building boundaries are equal and the state is leaving, then sort height from low to high.

Code #

package leetcode

import (
	"sort"

	"github.com/halfrost/leetcode-go/template"
)

// Solution 1 Binary Indexed Tree, time complexity O(n log n)
const LEFTSIDE = 1
const RIGHTSIDE = 2

type Point struct {
	xAxis int
	side  int
	index int
}

func getSkyline(buildings [][]int) [][]int {
	res := [][]int{}
	if len(buildings) == 0 {
		return res
	}
	allPoints, bit := make([]Point, 0), BinaryIndexedTree{}
	// [x-axis (value), [1 (left) | 2 (right)], index (building number)]
	for i, b := range buildings {
		allPoints = append(allPoints, Point{xAxis: b[0], side: LEFTSIDE, index: i})
		allPoints = append(allPoints, Point{xAxis: b[1], side: RIGHTSIDE, index: i})
	}
	sort.Slice(allPoints, func(i, j int) bool {
		if allPoints[i].xAxis == allPoints[j].xAxis {
			return allPoints[i].side < allPoints[j].side
		}
		return allPoints[i].xAxis < allPoints[j].xAxis
	})
	bit.Init(len(allPoints))
	kth := make(map[Point]int)
	for i := 0; i < len(allPoints); i++ {
		kth[allPoints[i]] = i
	}
	for i := 0; i < len(allPoints); i++ {
		pt := allPoints[i]
		if pt.side == LEFTSIDE {
			bit.Add(kth[Point{xAxis: buildings[pt.index][1], side: RIGHTSIDE, index: pt.index}], buildings[pt.index][2])
		}
		currHeight := bit.Query(kth[pt] + 1)
		if len(res) == 0 || res[len(res)-1][1] != currHeight {
			if len(res) > 0 && res[len(res)-1][0] == pt.xAxis {
				res[len(res)-1][1] = currHeight
			} else {
				res = append(res, []int{pt.xAxis, currHeight})
			}
		}
	}
	return res
}

type BinaryIndexedTree struct {
	tree     []int
	capacity int
}

// Init define
func (bit *BinaryIndexedTree) Init(capacity int) {
	bit.tree, bit.capacity = make([]int, capacity+1), capacity
}

// Add define
func (bit *BinaryIndexedTree) Add(index int, val int) {
	for ; index > 0; index -= index & -index {
		bit.tree[index] = max(bit.tree[index], val)
	}
}

// Query define
func (bit *BinaryIndexedTree) Query(index int) int {
	sum := 0
	for ; index <= bit.capacity; index += index & -index {
		sum = max(sum, bit.tree[index])
	}
	return sum
}

// Solution 2 Segment Tree, time complexity O(n log n)
func getSkyline1(buildings [][]int) [][]int {
	st, ans, lastHeight, check := template.SegmentTree{}, [][]int{}, 0, false
	posMap, pos := discretization218(buildings)
	tmp := make([]int, len(posMap))
	st.Init(tmp, func(i, j int) int {
		return max(i, j)
	})
	for _, b := range buildings {
		st.UpdateLazy(posMap[b[0]], posMap[b[1]-1], b[2])
	}
	for i := 0; i < len(pos); i++ {
		h := st.QueryLazy(posMap[pos[i]], posMap[pos[i]])
		if check == false && h != 0 {
			ans = append(ans, []int{pos[i], h})
			check = true
		} else if i > 0 && h != lastHeight {
			ans = append(ans, []int{pos[i], h})
		}
		lastHeight = h
	}
	return ans
}

func discretization218(positions [][]int) (map[int]int, []int) {
	tmpMap, posArray, posMap := map[int]int{}, []int{}, map[int]int{}
	for _, pos := range positions {
		tmpMap[pos[0]]++
		tmpMap[pos[1]-1]++
		tmpMap[pos[1]]++
	}
	for k := range tmpMap {
		posArray = append(posArray, k)
	}
	sort.Ints(posArray)
	for i, pos := range posArray {
		posMap[pos] = i
	}
	return posMap, posArray
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

// Solution 3 Sweep Line, time complexity O(n log n)
func getSkyline2(buildings [][]int) [][]int {
	size := len(buildings)
	es := make([]E, 0)
	for i, b := range buildings {
		l := b[0]
		r := b[1]
		h := b[2]
		// 1-- enter
		el := NewE(i, l, h, 0)
		es = append(es, el)
		// 0 -- leave
		er := NewE(i, r, h, 1)
		es = append(es, er)
	}
	skyline := make([][]int, 0)
	sort.Slice(es, func(i, j int) bool {
		if es[i].X == es[j].X {
			if es[i].T == es[j].T {
				if es[i].T == 0 {
					return es[i].H > es[j].H
				}
				return es[i].H < es[j].H
			}
			return es[i].T < es[j].T
		}
		return es[i].X < es[j].X
	})
	pq := NewIndexMaxPQ(size)
	for _, e := range es {
		curH := pq.Front()
		if e.T == 0 {
			if e.H > curH {
				skyline = append(skyline, []int{e.X, e.H})
			}
			pq.Enque(e.N, e.H)
		} else {
			pq.Remove(e.N)
			h := pq.Front()
			if curH > h {
				skyline = append(skyline, []int{e.X, h})
			}
		}
	}
	return skyline
}

// Sweep line pseudocode
// events = {{x: L , height: H , type: entering},
// 		  {x: R , height: H , type: leaving}}
// event.SortByX()
// ds = new DS()

// for e in events:
// 	if entering(e):
// 		if e.height > ds.max(): ans += [e.height]
// 		ds.add(e.height)
// 	if leaving(e):
// 		ds.remove(e.height)
// 		if e.height > ds.max(): ans += [ds.max()]

// E define
type E struct { // Define an event
	N int // number
	X int // x coordinate
	H int // height
	T int // type  0-enter 1-leave
}

// NewE define
func NewE(n, x, h, t int) E {
	return E{
		N: n,
		X: x,
		H: h,
		T: t,
	}
}

// IndexMaxPQ define
type IndexMaxPQ struct {
	items []int
	pq    []int
	qp    []int
	total int
}

// NewIndexMaxPQ define
func NewIndexMaxPQ(n int) IndexMaxPQ {
	qp := make([]int, n)
	for i := 0; i < n; i++ {
		qp[i] = -1
	}
	return IndexMaxPQ{
		items: make([]int, n),
		pq:    make([]int, n+1),
		qp:    qp,
	}
}

// Enque define
func (q *IndexMaxPQ) Enque(key, val int) {
	q.total++
	q.items[key] = val
	q.pq[q.total] = key
	q.qp[key] = q.total
	q.swim(q.total)
}

// Front define
func (q *IndexMaxPQ) Front() int {
	if q.total < 1 {
		return 0
	}
	return q.items[q.pq[1]]
}

// Remove define
func (q *IndexMaxPQ) Remove(key int) {
	rank := q.qp[key]
	q.exch(rank, q.total)
	q.total--
	q.qp[key] = -1
	q.sink(rank)
}

func (q *IndexMaxPQ) sink(n int) {
	for 2*n <= q.total {
		k := 2 * n
		if k < q.total && q.less(k, k+1) {
			k++
		}
		if q.less(k, n) {
			break
		}
		q.exch(k, n)
		n = k
	}
}

func (q *IndexMaxPQ) swim(n int) {
	for n > 1 {
		k := n / 2
		if q.less(n, k) {
			break
		}
		q.exch(n, k)
		n = k
	}
}

func (q *IndexMaxPQ) exch(i, j int) {
	q.pq[i], q.pq[j] = q.pq[j], q.pq[i]
	q.qp[q.pq[i]] = i
	q.qp[q.pq[j]] = j
}

func (q *IndexMaxPQ) less(i, j int) bool {
	return q.items[q.pq[i]] < q.items[q.pq[j]]
}