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 need to design a stack data structure that supports the usual push and pop operations, but also an increment operation that adds a given value to the bottom k elements of the stack efficiently. Which approach guarantees the most optimal time complexity for a sequence of n operations?

easy

A. Use a balanced binary search tree to store elements and increments, allowing O(log n) updates and queries.

B. Directly increment the bottom k elements on each increment call, resulting in O(n*k) time for n operations.

C. Use a lazy increment array to record increments and propagate them during pop operations, achieving O(n) total time.

D. Maintain a prefix sum array of increments and update it on each increment call, applying increments during pop.

Solution

1. Step 1: Understand the problem constraints

   The increment operation must be efficient even when called multiple times, so directly incrementing bottom k elements each time (O(n*k)) is too slow.

2. Step 2: Recognize the lazy increment pattern

   Using an auxiliary array to store increments lazily and applying them during pop operations reduces total time to O(n), as increments are propagated only once per element.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Lazy increments avoid repeated updates, achieving O(n) total time [OK]

Hint: Lazy increments reduce repeated updates to O(n) total time [OK]

Common Mistakes:

• Directly incrementing elements each time causes TLE
• Using complex data structures unnecessarily

2. You need to design a data structure that supports setting values at indices, taking snapshots of the entire array state, and retrieving values at any snapshot efficiently. Which approach best balances time and space complexity for frequent set and get operations?

easy

A. Store full copies of the array on every snapshot to allow O(1) get operations.

B. Maintain a hash map per index storing (snap_id, value) pairs and use binary search to retrieve values for get operations.

C. Use a single global hash map keyed by (index, snap_id) and perform linear search for get operations.

D. Use a segment tree to store snapshots and query values at any snapshot.

Solution

1. Step 1: Understand problem requirements

   The data structure must efficiently support set, snap, and get operations with many snapshots and updates.

2. Step 2: Evaluate approaches

   Storing full snapshots (B) uses too much space and is slow for many snaps. A global hash map with linear search (C) makes get operations slow. Segment trees (D) are complex and not optimal here. Using a hash map per index with binary search (A) allows O(1) amortized set and snap, and O(log m) get, balancing time and space efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search per index enables fast retrieval [OK]

Hint: Binary search per index enables fast retrieval [OK]

Common Mistakes:

• Thinking full snapshots are efficient for many snaps
• Using linear search for get causes slow queries

3. Consider the following buggy code snippet for flattening a multilevel doubly linked list. Which line contains the subtle bug that can cause infinite loops or incorrect list structure?

medium

A. Missing line that sets curr.child to None after splicing

B. Line where tail is found by while tail.next:

C. Line where curr.next is set to child

D. Line where tail.next is connected to curr.next

Solution

1. Step 1: Identify the role of curr.child

   After splicing the child list, curr.child must be set to None to avoid revisiting the child.

2. Step 2: Recognize missing pointer update

   The code does not set curr.child = None, causing infinite loops or incorrect traversal.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Not clearing child pointer leads to repeated processing [OK]

Hint: Always clear child pointer after splicing [OK]

Common Mistakes:

• Forgetting to clear child pointer after splicing
• Incorrectly updating prev pointers instead

4. Suppose the LFU cache must support a new operation: reuse(key) which resets the frequency of key to 1 without changing its value. Which modification to the optimal LFU cache design correctly supports this operation without breaking O(1) complexity?

hard

A. Simply set the frequency of the key to 1 in the key_val_freq map without moving it between frequency lists

B. Clear the entire cache and reinsert the key with frequency 1

C. Remove the key from its current frequency list and add it to freq=1 list, update min_freq to 1

D. Increment the frequency of the key by 1 and then reset min_freq to 1

Solution

1. Step 1: Understand reuse operation

   Reuse resets frequency to 1, so the key must move from its current frequency list to the freq=1 list.

2. Step 2: Update data structures accordingly

   Remove key from old freq list, add to freq=1 list, and update min_freq to 1 to reflect the new minimum frequency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Moving key between freq lists and updating min_freq preserves O(1) operations [OK]

Hint: Move key to freq=1 list and update min_freq [OK]

Common Mistakes:

• Not moving key between frequency lists
• Resetting frequency without updating min_freq
• Clearing cache is inefficient and breaks O(1)

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