The Skyline Problem

🎯

The Skyline Problem

hardMIXEDGoogleAmazonFacebook

Imagine you are looking at a city skyline formed by several buildings. You want to capture the silhouette of the skyline as seen from a distance, which is a classic problem in computer graphics and urban planning.

💡 This problem involves merging overlapping intervals and tracking maximum heights dynamically. Beginners often struggle because it combines sorting, data structures like heaps, and careful event processing, which can be conceptually challenging.

📋

Problem Statement

Given a list of buildings, each represented as a triplet [left, right, height], where left and right are x-coordinates of the building's edges and height is the building's height, output the skyline formed by these buildings. The skyline is a list of 'key points' in the format [x, height] that uniquely defines the outer contour of the silhouette formed by the buildings when viewed from a distance. The key points should be sorted by their x-coordinate, and consecutive points should not have the same height.

1 ≤ number of buildings ≤ 10^50 ≤ left < right ≤ 2 * 10^91 ≤ height ≤ 10^9

💡

Example

Input"[[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]"

Output[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

The skyline rises to 10 at x=2, then to 15 at x=3, drops to 12 at x=7, falls to 0 at x=12, rises again to 10 at x=15, drops to 8 at x=20, and finally falls to 0 at x=24.

• Single building → skyline is just two points: start height and end zero
• Buildings with same start and end but different heights → taller building dominates
• Buildings that do not overlap → skyline is concatenation of individual buildings
• Buildings with zero height (invalid input) → should be ignored or treated as no building

⚠️

Common Mistakes

Not sorting edges correctly (start edges before end edges at same x)

Incorrect skyline with missing or extra points

✅ Sort edges by x, and if tie, start edges (negative height) before end edges (positive height)

Not removing inactive heights from the heap

Heap top does not reflect current tallest building, causing wrong skyline points

✅ Use a count map to track active heights and remove from heap when count is zero

Adding redundant points with same height consecutively

Skyline has unnecessary points, failing problem requirements

✅ Add a key point only when the height changes from the previous point

Using brute force for large inputs

Time limit exceeded or memory overflow

✅ Use sweep line or divide and conquer approaches for efficiency

Incorrectly merging skylines in divide and conquer

Overlapping intervals not handled properly, skyline shape is wrong

✅ Carefully compare x-coordinates and heights, and handle equal x cases correctly

🧠

Brute Force (Height Map Simulation)

💡 This approach exists to build intuition by simulating the skyline on a coordinate axis directly. It is simple but inefficient, helping beginners understand the problem's spatial nature before optimizing.

Intuition

Mark the height of every building on a large array representing the x-axis, then scan this array to find changes in height which form the skyline.

Algorithm

1. Find the maximum right coordinate among all buildings to determine the length of the height array.
2. Initialize an array of zeros representing heights at each x-coordinate.
3. For each building, update the height array between its left and right edges to the building's height if it is taller than the current height.
4. Traverse the height array to identify points where the height changes and add these as key points to the skyline.

💡 The main challenge is realizing that the skyline changes only at points where the height changes, which can be found by scanning the height array.

</>

Code

def getSkyline(buildings):
    if not buildings:
        return []
    max_right = max(b[1] for b in buildings)
    height = [0] * (max_right + 1)
    for left, right, h in buildings:
        for i in range(left, right):
            height[i] = max(height[i], h)
    result = []
    prev = 0
    for x in range(max_right + 1):
        if height[x] != prev:
            result.append([x, height[x]])
            prev = height[x]
    return result

# Example usage
if __name__ == '__main__':
    buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
    print(getSkyline(buildings))

Line Notes

max_right = max(b[1] for b in buildings)Finds the maximum x-coordinate to size the height array

height = [0] * (max_right + 1)Initializes height array with zeros representing ground level

for i in range(left, right):Updates height for every x-coordinate covered by the building

if height[x] != prev:Detects a change in height to add a key point to the skyline

import java.util.*;
public class SkylineBruteForce {
    public static List<int[]> getSkyline(int[][] buildings) {
        if (buildings == null || buildings.length == 0) return new ArrayList<>();
        int maxRight = 0;
        for (int[] b : buildings) maxRight = Math.max(maxRight, b[1]);
        int[] height = new int[maxRight + 1];
        for (int[] b : buildings) {
            for (int i = b[0]; i < b[1]; i++) {
                height[i] = Math.max(height[i], b[2]);
            }
        }
        List<int[]> result = new ArrayList<>();
        int prev = 0;
        for (int i = 0; i <= maxRight; i++) {
            if (height[i] != prev) {
                result.add(new int[]{i, height[i]});
                prev = height[i];
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[][] buildings = {{2,9,10},{3,7,15},{5,12,12},{15,20,10},{19,24,8}};
        List<int[]> skyline = getSkyline(buildings);
        for (int[] point : skyline) {
            System.out.print("[" + point[0] + "," + point[1] + "] ");
        }
    }
}

Line Notes

int maxRight = 0;Initialize maxRight to find the furthest building edge

for (int i = b[0]; i < b[1]; i++)Update height array for each x-coordinate covered by building

if (height[i] != prev)Detect height changes to record skyline key points

result.add(new int[]{i, height[i]});Add the key point to the result list

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int,int>> getSkyline(vector<vector<int>>& buildings) {
    if (buildings.empty()) return {};
    int maxRight = 0;
    for (auto& b : buildings) maxRight = max(maxRight, b[1]);
    vector<int> height(maxRight + 1, 0);
    for (auto& b : buildings) {
        for (int i = b[0]; i < b[1]; ++i) {
            height[i] = max(height[i], b[2]);
        }
    }
    vector<pair<int,int>> result;
    int prev = 0;
    for (int i = 0; i <= maxRight; ++i) {
        if (height[i] != prev) {
            result.emplace_back(i, height[i]);
            prev = height[i];
        }
    }
    return result;
}

int main() {
    vector<vector<int>> buildings = {{2,9,10},{3,7,15},{5,12,12},{15,20,10},{19,24,8}};
    auto skyline = getSkyline(buildings);
    for (auto& p : skyline) {
        cout << "[" << p.first << "," << p.second << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

int maxRight = 0;Find the maximum right boundary to size the height vector

for (int i = b[0]; i < b[1]; ++i)Update height for each x-coordinate covered by building

if (height[i] != prev)Detect height changes to add skyline points

result.emplace_back(i, height[i]);Add the key point to the result vector

function getSkyline(buildings) {
    if (!buildings || buildings.length === 0) return [];
    let maxRight = 0;
    for (const b of buildings) maxRight = Math.max(maxRight, b[1]);
    const height = new Array(maxRight + 1).fill(0);
    for (const [left, right, h] of buildings) {
        for (let i = left; i < right; i++) {
            height[i] = Math.max(height[i], h);
        }
    }
    const result = [];
    let prev = 0;
    for (let i = 0; i <= maxRight; i++) {
        if (height[i] !== prev) {
            result.push([i, height[i]]);
            prev = height[i];
        }
    }
    return result;
}

// Example usage
const buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]];
console.log(getSkyline(buildings));

Line Notes

let maxRight = 0;Initialize maxRight to find the furthest building edge

for (let i = left; i < right; i++)Update height array for each x-coordinate covered by building

if (height[i] !== prev)Detect height changes to add key points

result.push([i, height[i]]);Add the key point to the result array

⏱

Complexity

TimeO(n * maxRight)

SpaceO(maxRight)

We create an array of size maxRight and update heights for each building segment, leading to potentially very large time and space usage.

💡 For n=5 and maxRight=24, this is manageable, but for n=10^5 and maxRight=10^9, this approach is infeasible.

Interview Verdict: TLE / Not practical for large inputs

This approach is too slow and memory-heavy for large inputs but is useful to understand the problem's spatial nature before optimizing.

🧠

Sweep Line with Sorting and Max Heap

💡 This approach introduces the sweep line technique and a max heap to efficiently track the current tallest building, which is a common pattern in interval and skyline problems.

Intuition

Process building edges in sorted order, adding building heights when entering and removing when leaving, using a max heap to track the current tallest building at each point.

Algorithm

1. Create a list of all building edges: start edges with negative height, end edges with positive height.
2. Sort the edges by x-coordinate; if tie, start edges before end edges, taller buildings first.
3. Use a max heap to keep track of active building heights.
4. Traverse the edges, adding heights on start edges and removing on end edges, recording key points when the max height changes.

💡 The key insight is to treat building edges as events and use a data structure to quickly find the current tallest building.

</>

Code

import heapq

def getSkyline(buildings):
    edges = []
    for L, R, H in buildings:
        edges.append((L, -H))  # start edge
        edges.append((R, H))   # end edge
    edges.sort(key=lambda x: (x[0], x[1]))
    result = []
    heap = [0]
    prev = 0
    import collections
    count = collections.Counter()
    count[0] = 1
    for x, h in edges:
        if h < 0:  # start edge
            heapq.heappush(heap, h)
            count[-h] += 1
        else:  # end edge
            count[h] -= 1
            while heap and count[-heap[0]] == 0:
                heapq.heappop(heap)
        curr = -heap[0]
        if curr != prev:
            result.append([x, curr])
            prev = curr
    return result

# Example usage
if __name__ == '__main__':
    buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
    print(getSkyline(buildings))

Line Notes

edges.append((L, -H))Mark start edges with negative height to distinguish from end edges

edges.sort(key=lambda x: (x[0], x[1]))Sort edges by x, ensuring start edges come before end edges at same x

heap = [0]Initialize max heap with ground level height 0

while heap and count[-heap[0]] == 0:Remove heights from heap that are no longer active

import java.util.*;
public class SkylineSweepLine {
    public static List<int[]> getSkyline(int[][] buildings) {
        List<int[]> edges = new ArrayList<>();
        for (int[] b : buildings) {
            edges.add(new int[]{b[0], -b[2]});
            edges.add(new int[]{b[1], b[2]});
        }
        edges.sort((a,b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        List<int[]> result = new ArrayList<>();
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        Map<Integer, Integer> count = new HashMap<>();
        heap.add(0);
        count.put(0, 1);
        int prev = 0;
        for (int[] e : edges) {
            int x = e[0], h = e[1];
            if (h < 0) {
                heap.add(-h);
                count.put(-h, count.getOrDefault(-h, 0) + 1);
            } else {
                count.put(h, count.get(h) - 1);
                while (!heap.isEmpty() && count.getOrDefault(heap.peek(), 0) == 0) {
                    heap.poll();
                }
            }
            int curr = heap.peek();
            if (curr != prev) {
                result.add(new int[]{x, curr});
                prev = curr;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[][] buildings = {{2,9,10},{3,7,15},{5,12,12},{15,20,10},{19,24,8}};
        List<int[]> skyline = getSkyline(buildings);
        for (int[] p : skyline) {
            System.out.print("[" + p[0] + "," + p[1] + "] ");
        }
    }
}

Line Notes

edges.add(new int[]{b[0], -b[2]});Add start edges with negative height to distinguish

edges.sort((a,b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);Sort edges by x, start edges before end edges

while (!heap.isEmpty() && count.getOrDefault(heap.peek(), 0) == 0)Remove inactive heights from heap

if (curr != prev)Add key point when max height changes

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_map>
using namespace std;

vector<pair<int,int>> getSkyline(vector<vector<int>>& buildings) {
    vector<pair<int,int>> edges;
    for (auto& b : buildings) {
        edges.emplace_back(b[0], -b[2]);
        edges.emplace_back(b[1], b[2]);
    }
    sort(edges.begin(), edges.end(), [](auto& a, auto& b) {
        if (a.first != b.first) return a.first < b.first;
        return a.second < b.second;
    });
    priority_queue<int> heap;
    unordered_map<int,int> count;
    heap.push(0);
    count[0] = 1;
    vector<pair<int,int>> result;
    int prev = 0;
    for (auto& e : edges) {
        int x = e.first, h = e.second;
        if (h < 0) {
            heap.push(-h);
            count[-h]++;
        } else {
            count[h]--;
            while (!heap.empty() && count[heap.top()] == 0) {
                heap.pop();
            }
        }
        int curr = heap.top();
        if (curr != prev) {
            result.emplace_back(x, curr);
            prev = curr;
        }
    }
    return result;
}

int main() {
    vector<vector<int>> buildings = {{2,9,10},{3,7,15},{5,12,12},{15,20,10},{19,24,8}};
    auto skyline = getSkyline(buildings);
    for (auto& p : skyline) {
        cout << "[" << p.first << "," << p.second << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

edges.emplace_back(b[0], -b[2]);Add start edges with negative height for sorting

sort(edges.begin(), edges.end(), ...Sort edges by x, start edges before end edges

while (!heap.empty() && count[heap.top()] == 0)Remove heights no longer active from heap

if (curr != prev)Add key point when max height changes

function getSkyline(buildings) {
    const edges = [];
    for (const [L, R, H] of buildings) {
        edges.push([L, -H]);
        edges.push([R, H]);
    }
    edges.sort((a,b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);
    const heap = [0];
    const count = new Map();
    count.set(0, 1);
    const result = [];
    let prev = 0;
    function heapPush(h) {
        heap.push(h);
        heap.sort((a,b) => b - a);
    }
    function heapPop() {
        return heap.shift();
    }
    for (const [x, h] of edges) {
        if (h < 0) {
            heapPush(-h);
            count.set(-h, (count.get(-h) || 0) + 1);
        } else {
            count.set(h, count.get(h) - 1);
            while (heap.length && count.get(heap[0]) === 0) {
                heapPop();
            }
        }
        const curr = heap[0];
        if (curr !== prev) {
            result.push([x, curr]);
            prev = curr;
        }
    }
    return result;
}

// Example usage
const buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]];
console.log(getSkyline(buildings));

Line Notes

edges.push([L, -H]);Mark start edges with negative height for sorting

edges.sort((a,b) => ...Sort edges by x, start edges before end edges

while (heap.length && count.get(heap[0]) === 0)Remove inactive heights from heap

if (curr !== prev)Add key point when max height changes

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Sorting edges takes O(n log n), and each building edge is processed with heap operations costing O(log n).

💡 For n=10^5, this approach is efficient enough to run within time limits.

Interview Verdict: Accepted / Standard solution

This is the go-to approach for interviews, balancing clarity and efficiency.

🧠

Divide and Conquer

💡 This approach uses recursion to merge skylines of subproblems, teaching how to combine solutions and handle complex merges, a useful technique for many interval problems.

Intuition

Divide the list of buildings into two halves, recursively find the skyline for each half, then merge the two skylines into one.

Algorithm

1. If the list has one building, return its skyline as two points: start height and end zero.
2. Recursively compute skylines for left and right halves.
3. Merge the two skylines by iterating through both, comparing x-coordinates and heights, and adding key points when height changes.
4. Return the merged skyline.

💡 The merge step is the trickiest, requiring careful handling of overlapping intervals and height comparisons.

</>

Code

def mergeSkylines(left, right):
    h1 = h2 = 0
    i = j = 0
    merged = []
    while i < len(left) and j < len(right):
        if left[i][0] < right[j][0]:
            x, h1 = left[i]
            i += 1
        elif right[j][0] < left[i][0]:
            x, h2 = right[j]
            j += 1
        else:
            x = left[i][0]
            h1 = left[i][1]
            h2 = right[j][1]
            i += 1
            j += 1
        maxH = max(h1, h2)
        if not merged or merged[-1][1] != maxH:
            merged.append([x, maxH])
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

def getSkyline(buildings):
    if not buildings:
        return []
    if len(buildings) == 1:
        L, R, H = buildings[0]
        return [[L, H], [R, 0]]
    mid = len(buildings) // 2
    left = getSkyline(buildings[:mid])
    right = getSkyline(buildings[mid:])
    return mergeSkylines(left, right)

# Example usage
if __name__ == '__main__':
    buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
    print(getSkyline(buildings))

Line Notes

if len(buildings) == 1:Base case returns the skyline for a single building

while i < len(left) and j < len(right):Merge two skylines by comparing x-coordinates

maxH = max(h1, h2)Determine the current max height at this x-coordinate

if not merged or merged[-1][1] != maxH:Add key point only if height changes

import java.util.*;
public class SkylineDivideConquer {
    public static List<int[]> mergeSkylines(List<int[]> left, List<int[]> right) {
        int h1 = 0, h2 = 0, i = 0, j = 0;
        List<int[]> merged = new ArrayList<>();
        while (i < left.size() && j < right.size()) {
            int x = 0;
            if (left.get(i)[0] < right.get(j)[0]) {
                x = left.get(i)[0];
                h1 = left.get(i)[1];
                i++;
            } else if (right.get(j)[0] < left.get(i)[0]) {
                x = right.get(j)[0];
                h2 = right.get(j)[1];
                j++;
            } else {
                x = left.get(i)[0];
                h1 = left.get(i)[1];
                h2 = right.get(j)[1];
                i++;
                j++;
            }
            int maxH = Math.max(h1, h2);
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] != maxH) {
                merged.add(new int[]{x, maxH});
            }
        }
        while (i < left.size()) merged.add(left.get(i++));
        while (j < right.size()) merged.add(right.get(j++));
        return merged;
    }
    public static List<int[]> getSkyline(int[][] buildings) {
        if (buildings == null || buildings.length == 0) return new ArrayList<>();
        return getSkylineHelper(buildings, 0, buildings.length - 1);
    }
    private static List<int[]> getSkylineHelper(int[][] buildings, int left, int right) {
        if (left == right) {
            List<int[]> res = new ArrayList<>();
            res.add(new int[]{buildings[left][0], buildings[left][2]});
            res.add(new int[]{buildings[left][1], 0});
            return res;
        }
        int mid = (left + right) / 2;
        List<int[]> leftSky = getSkylineHelper(buildings, left, mid);
        List<int[]> rightSky = getSkylineHelper(buildings, mid + 1, right);
        return mergeSkylines(leftSky, rightSky);
    }
    public static void main(String[] args) {
        int[][] buildings = {{2,9,10},{3,7,15},{5,12,12},{15,20,10},{19,24,8}};
        List<int[]> skyline = getSkyline(buildings);
        for (int[] p : skyline) {
            System.out.print("[" + p[0] + "," + p[1] + "] ");
        }
    }
}

Line Notes

if (left == right)Base case returns skyline for one building

while (i < left.size() && j < right.size())Merge two skylines by comparing x-coordinates

int maxH = Math.max(h1, h2);Calculate max height at current x

if (merged.isEmpty() || merged.get(merged.size() - 1)[1] != maxH)Add key point only if height changes

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int,int>> mergeSkylines(const vector<pair<int,int>>& left, const vector<pair<int,int>>& right) {
    int h1 = 0, h2 = 0, i = 0, j = 0;
    vector<pair<int,int>> merged;
    while (i < (int)left.size() && j < (int)right.size()) {
        int x = 0;
        if (left[i].first < right[j].first) {
            x = left[i].first;
            h1 = left[i].second;
            i++;
        } else if (right[j].first < left[i].first) {
            x = right[j].first;
            h2 = right[j].second;
            j++;
        } else {
            x = left[i].first;
            h1 = left[i].second;
            h2 = right[j].second;
            i++;
            j++;
        }
        int maxH = max(h1, h2);
        if (merged.empty() || merged.back().second != maxH) {
            merged.emplace_back(x, maxH);
        }
    }
    while (i < (int)left.size()) merged.push_back(left[i++]);
    while (j < (int)right.size()) merged.push_back(right[j++]);
    return merged;
}

vector<pair<int,int>> getSkylineHelper(const vector<vector<int>>& buildings, int left, int right) {
    if (left == right) {
        return {{buildings[left][0], buildings[left][2]}, {buildings[left][1], 0}};
    }
    int mid = (left + right) / 2;
    auto leftSky = getSkylineHelper(buildings, left, mid);
    auto rightSky = getSkylineHelper(buildings, mid + 1, right);
    return mergeSkylines(leftSky, rightSky);
}

vector<pair<int,int>> getSkyline(vector<vector<int>>& buildings) {
    if (buildings.empty()) return {};
    return getSkylineHelper(buildings, 0, buildings.size() - 1);
}

int main() {
    vector<vector<int>> buildings = {{2,9,10},{3,7,15},{5,12,12},{15,20,10},{19,24,8}};
    auto skyline = getSkyline(buildings);
    for (auto& p : skyline) {
        cout << "[" << p.first << "," << p.second << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

if (left == right)Base case returns skyline for one building

while (i < (int)left.size() && j < (int)right.size())Merge two skylines by comparing x-coordinates

int maxH = max(h1, h2);Calculate max height at current x

if (merged.empty() || merged.back().second != maxH)Add key point only if height changes

function mergeSkylines(left, right) {
    let h1 = 0, h2 = 0, i = 0, j = 0;
    const merged = [];
    while (i < left.length && j < right.length) {
        let x = 0;
        if (left[i][0] < right[j][0]) {
            x = left[i][0];
            h1 = left[i][1];
            i++;
        } else if (right[j][0] < left[i][0]) {
            x = right[j][0];
            h2 = right[j][1];
            j++;
        } else {
            x = left[i][0];
            h1 = left[i][1];
            h2 = right[j][1];
            i++;
            j++;
        }
        const maxH = Math.max(h1, h2);
        if (merged.length === 0 || merged[merged.length - 1][1] !== maxH) {
            merged.push([x, maxH]);
        }
    }
    while (i < left.length) merged.push(left[i++]);
    while (j < right.length) merged.push(right[j++]);
    return merged;
}

function getSkyline(buildings) {
    if (!buildings.length) return [];
    if (buildings.length === 1) {
        const [L, R, H] = buildings[0];
        return [[L, H], [R, 0]];
    }
    const mid = Math.floor(buildings.length / 2);
    const left = getSkyline(buildings.slice(0, mid));
    const right = getSkyline(buildings.slice(mid));
    return mergeSkylines(left, right);
}

// Example usage
const buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]];
console.log(getSkyline(buildings));

Line Notes

if (buildings.length === 1)Base case returns skyline for one building

while (i < left.length && j < right.length)Merge two skylines by comparing x-coordinates

const maxH = Math.max(h1, h2);Calculate max height at current x

if (merged.length === 0 || merged[merged.length - 1][1] !== maxH)Add key point only if height changes

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Divide and conquer splits the problem and merges skylines in O(n log n) time, similar to merge sort.

💡 This approach is efficient and elegant, but the merge step requires careful implementation.

Interview Verdict: Accepted / Elegant alternative

Good to know as an alternative approach, especially to demonstrate divide and conquer skills.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the sweep line approach is the best balance of clarity and efficiency and should be your primary solution.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n * maxRight)	O(maxRight)	No	Yes	Mention only - never code due to inefficiency
2. Sweep Line with Max Heap	O(n log n)	O(n)	No	Yes	Code this approach for optimal solution
3. Divide and Conquer	O(n log n)	O(n)	Possible (deep recursion)	Yes	Good alternative to discuss or code if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to grasp the problem, then learn the sweep line and divide and conquer approaches for efficiency and elegance.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding of the problem space.Introduce the sweep line approach with a max heap as the optimal solution.Optionally discuss the divide and conquer method to show mastery.Write clean, tested code for the chosen approach.Test with edge cases and explain your reasoning.

Time Allocation

Clarify: 5min → Approach: 10min → Code: 15min → Test: 5min. Total ~35min

What the Interviewer Tests

The interviewer tests your ability to handle interval merging, efficient data structures, sorting, and edge cases. They also assess your communication and problem-solving approach.

Common Follow-ups

• How would you handle buildings with the same start or end points?
• Can you optimize the heap operations further?
• How would you modify the solution if buildings could be removed dynamically?

💡 These follow-ups test your understanding of sorting stability, data structure optimizations, and dynamic updates.

🔍

Pattern Recognition

When to Use

1) Problem involves intervals/buildings with start and end points; 2) Need to find combined outline or max height; 3) Overlapping intervals affect output; 4) Output is a list of key points or changes.

Signature Phrases

buildings represented as [left, right, height]output the skyline formed by these buildings

NOT This Pattern When

Problems that only require sorting intervals without height tracking or that do not require merging outlines.

Similar Problems

The Maximum Histogram Area - both involve heights and intervalsMerge Intervals - merging overlapping intervals is a core conceptMeeting Rooms II - managing overlapping intervals with heaps

Practice

1. You are given a string of digits and a target integer. You need to insert binary operators (+, -, *) between the digits to form expressions that evaluate to the target. Which algorithmic approach guarantees finding all valid expressions?

easy

A. Backtracking with enumeration of all possible operator insertions and operand splits

B. Greedy algorithm that inserts operators based on local evaluation to reach the target quickly

C. Dynamic programming that stores intermediate results for sub-expressions without operator insertion

D. Divide and conquer by splitting the string into halves and solving independently

Solution

1. Step 1: Understand problem requirements

   The problem requires generating all valid expressions by inserting operators between digits to match a target value, which demands exploring all combinations.

2. Step 2: Identify suitable algorithm

   Backtracking with enumeration systematically tries all splits and operator insertions, guaranteeing all solutions are found. Greedy or divide and conquer approaches fail to explore all combinations, and DP without operator insertion does not apply.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking enumerates all expressions [OK]

Hint: All expressions require exploring all splits and operators [OK]

Common Mistakes:

• Thinking greedy can find all expressions
• Assuming DP without operator insertion suffices

2. Consider the following Python code snippet implementing the optimal backtracking solution for Expression Add Operators. Given input num = "123" and target = 6, what is the final list of expressions returned by the function?

easy

A. ["1+2+3", "1*2*3"]

B. ["1+2+3", "1*2*3", "12-6"]

C. ["1+2+3", "1*2*3", "1+23"]

D. ["1+2+3", "1*2*3", "1-2+3"]

Solution

1. Step 1: Trace backtrack calls for num="123", target=6

   At index 0, path starts with "1". Then operators +, -, * are tried with "2" and "3". Valid expressions that evaluate to 6 are "1+2+3" and "1*2*3".

2. Step 2: Verify no other expressions equal 6

   Expressions like "12-6" or "1+23" do not evaluate to 6. "1-2+3" equals 2, so not included.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only "1+2+3" and "1*2*3" sum to 6 [OK]

Hint: Trace small input carefully to confirm valid expressions [OK]

Common Mistakes:

• Including invalid expressions with wrong evaluation
• Missing multiplication precedence

3. You are given an array representing the heights of adjacent bars in a histogram. The task is to find the largest rectangular area that can be formed within the bounds of the histogram bars. Which algorithmic approach guarantees an optimal O(n) time solution for this problem?

easy

A. Greedy approach selecting the tallest bar and expanding outwards

B. Brute force nested loops checking all possible rectangles

C. Dynamic programming with memoization of subproblems

D. Single pass stack-based approach that tracks indices of bars

Solution

1. Step 1: Understand problem constraints and requirements

   The problem requires finding the largest rectangle in a histogram efficiently, which involves checking contiguous bars and their heights.

2. Step 2: Identify optimal approach using stack

   The single pass stack-based approach uses a stack to keep track of indices of bars in ascending order, allowing calculation of maximal rectangle areas in O(n) time by popping bars when a smaller height is encountered.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Stack approach is known optimal for largest rectangle in histogram [OK]

Hint: Stack-based approach achieves O(n) time [OK]

Common Mistakes:

• Assuming brute force is efficient enough
• Confusing this with a DP problem
• Thinking greedy expansion from tallest bar suffices

4. You are given an array representing the elevation map where the width of each bar is 1. You need to find how much water can be trapped after raining. Which approach guarantees an optimal solution with linear time and constant space complexity?

easy

A. Use nested loops to find the maximum height to the left and right of each bar and calculate trapped water accordingly.

B. Use two pointers starting from both ends, moving inward, updating left_max and right_max, and accumulating trapped water based on comparisons.

C. Use dynamic programming with a 2D table storing water trapped between every pair of bars.

D. Use a greedy approach that always traps water at the current lowest bar without considering future bars.

Solution

1. Step 1: Understand problem constraints

   The problem requires calculating trapped water efficiently with minimal space.

2. Step 2: Evaluate approaches

   Nested loops (brute force) are O(n²), DP with 2D table is inefficient, greedy fails on complex cases. The two-pointer approach uses O(n) time and O(1) space by moving pointers inward and updating max heights.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer approach is known optimal for trapping rain water [OK]

Hint: Two pointers with max updates -> optimal O(n) time, O(1) space [OK]

Common Mistakes:

• Confusing greedy with two-pointer approach
• Assuming DP with 2D table is needed
• Believing brute force is acceptable for large inputs

5. Suppose the problem is modified so that envelopes can be reused multiple times in the nesting sequence. Which of the following algorithmic changes correctly adapts the solution to this variant?

hard

A. Keep the sorting step, but replace LIS with a dynamic programming approach that allows repeated elements by using <= comparisons.

B. Use the same sorting and LIS with binary search approach, but allow bisect_right instead of bisect_left to handle duplicates.

C. Sort envelopes by width ascending and height descending, then use a DP approach similar to unbounded knapsack allowing reuse.

D. Remove sorting and use a greedy approach to pick envelopes repeatedly based on height only.

Solution

1. Step 1: Understand reuse impact

   Allowing reuse breaks LIS assumptions since elements can be repeated multiple times.

2. Step 2: Adapt algorithm

   Sorting still helps, but LIS must be replaced by a DP approach similar to unbounded knapsack that allows multiple uses of the same envelope.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP with reuse and sorting is correct adaptation [OK]

Hint: Reuse means LIS no longer applies; use unbounded knapsack DP [OK]

Common Mistakes:

• Trying to fix LIS with bisect_right
• Using <= in LIS but still only one use per envelope
• Ignoring sorting or using greedy