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. Consider the following code snippet implementing the optimal approach to copy a list with random pointers. Given the input list:
Node1(val=1) -> Node2(val=2) -> Node3(val=3), where Node1.random = Node3, Node2.random = Node1, Node3.random = null.
After Step 2 (assigning random pointers), what is the value of copy_curr.random.val when copy_curr points to the copied node of Node2?

easy

A. None (null)

B. 3

C. 1

D. 2

Solution

1. Step 1: Trace Step 1 (interleaving nodes)

   Original list: 1 -> 2 -> 3 becomes 1 -> 1' -> 2 -> 2' -> 3 -> 3'.

2. Step 2: Trace Step 2 (assign random pointers)

   Node2.random = Node1, so copied Node2 (2') random = Node1.next = 1'. Thus, copy_curr.random.val = 1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   copy_curr.random points to copied Node1 with val=1 [OK]

Hint: Copied node's random points to original.random.next [OK]

Common Mistakes:

• Confusing original and copied nodes when assigning random pointers
• Off-by-one errors in stepping through interleaved list
• Assuming random pointer points to original node's val

2. What is the time complexity of the checkOut operation in the optimal UndergroundSystem implementation that uses a linked list for check-ins, assuming n is the number of active check-ins at the time of checkout?

medium

A. O(1) because the linked list head always points to the correct check-in node

B. O(n) due to updating route data hash map entries

C. O(log n) because the linked list is sorted by check-in time

D. O(n) because it may need to traverse the linked list to find the matching check-in node

Solution

1. Step 1: Identify linked list traversal

   The checkOut method traverses the linked list from head to find the node with matching id, which can take up to O(n) time.

2. Step 2: Analyze route data update

   Updating the hash map for route data is O(1) average, so it does not dominate complexity.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Traversal over n nodes dominates, so O(n) time [OK]

Hint: Linked list traversal dominates checkOut time [OK]

Common Mistakes:

• Assuming O(1) because head is used directly

3. Examine the following buggy remove method from the optimized Insert Delete GetRandom O(1) with duplicates data structure. Which line contains the subtle bug that can cause incorrect behavior or runtime errors?

def remove(self, val: int) -> bool:
    if val not in self.idx_map or not self.idx_map[val]:
        return false
    remove_idx = self.idx_map[val].pop()
    last_val = self.nums[-1]
    self.nums[remove_idx] = last_val
    self.idx_map[last_val].add(remove_idx)
    # BUG: missing discard of old index for last_val
    self.nums.pop()
    if not self.idx_map[val]:
        del self.idx_map[val]
    return true

medium

A. Missing line to discard old index of last_val from idx_map[last_val]

B. Line adding remove_idx to idx_map[last_val] (self.idx_map[last_val].add(remove_idx))

C. Line popping remove_idx from idx_map[val] (remove_idx = self.idx_map[val].pop())

D. Line removing the last element from nums (self.nums.pop())

Solution

1. Step 1: Understand index updates during removal

   When swapping last_val into remove_idx, we must update idx_map[last_val] by adding remove_idx and discarding the old index (len(nums)-1).

2. Step 2: Identify missing discard

   The code adds remove_idx to idx_map[last_val] but does not discard the old index, causing stale indices and incorrect removals later.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing discard leads to incorrect index tracking [OK]

Hint: Always discard old indices after swapping during removal [OK]

Common Mistakes:

• Forgetting to discard old index after swap
• Removing wrong element from idx_map
• Incorrect pop from idx_map[val]

4. Suppose the data stream allows duplicate numbers to be removed after insertion, requiring support for removeNum(num). Which modification to the balanced two heaps approach is necessary to maintain correct median retrieval?

hard

A. Use a balanced binary search tree instead of heaps to allow efficient removals.

B. Ignore removals and only add numbers, as removals break the heap structure.

C. Rebuild both heaps from scratch after every removal to maintain heap properties.

D. Add a delayed deletion map to mark elements for lazy removal and prune heaps during addNum and findMedian.

Solution

1. Step 1: Understand removal challenges

   Heaps do not support efficient arbitrary removals, so direct removal breaks heap properties.

2. Step 2: Use lazy deletion

   Maintain a delayed deletion map to mark elements for removal and prune them lazily during heap operations, preserving heap structure and efficiency.

3. Step 3: Avoid costly rebuilds

   Rebuilding heaps on every removal is inefficient; ignoring removals is incorrect.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Lazy deletion with pruning maintains correctness and efficiency [OK]

Hint: Lazy deletion map enables efficient removals in heaps [OK]

Common Mistakes:

• Rebuilding heaps on every removal
• Ignoring removals breaks correctness

5. Suppose the SnapshotArray is extended to support negative indices and very large index ranges, but only a small subset of indices are ever set. Which modification best maintains efficient space and time complexity for set, snap, and get operations?

hard

A. Use a hash map keyed by index storing per-index snapshot lists with binary search for get.

B. Use a balanced binary search tree per index to store snapshots and perform get queries.

C. Store full snapshots of the entire array on each snap to simplify get operations.

D. Use a large fixed-size array indexed by offset to handle negative indices.

Solution

1. Step 1: Consider negative and large indices

   Fixed-size arrays (A) are infeasible due to large or negative indices causing huge memory usage.

2. Step 2: Evaluate sparse storage

   Using a hash map keyed by index (D) stores only set indices, maintaining space efficiency and enabling binary search for fast get.

3. Step 3: Compare alternatives

   Full snapshots (C) waste space; balanced trees (B) add complexity without clear benefit over binary search on lists.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Hash map per index supports sparse, negative indices efficiently [OK]

Hint: Hash map per index handles sparse and negative indices efficiently [OK]

Common Mistakes:

• Using large arrays wastes memory
• Full snapshots explode space usage