Skip to content
Tutorials Center
My learning

Topics

Lesson 204 of 225 ยท Advanced Topics

Celebrity Problem and Skyline

Two classic interview problems in Python: find the celebrity with O(n) elimination, and compute the city skyline with a sweep line and a max-heap.

Some problems are famous because they teach a technique in a small package. This lesson covers two of them. The celebrity problem shows how to eliminate candidates so that each question rules one person out, turning an obvious O(n^2) search into O(n). The skyline problem shows the sweep line: process events in sorted order while keeping a data structure of what is currently "active".

You will use arrays, heaps, sorting and a little two-pointer thinking. If the heap idea is new, read Heaps first.

The celebrity problem

At a party of n people, a celebrity is someone who is known by everyone else but knows nobody. You may ask only one kind of question: knows(a, b), "does a know b?". How do you find the celebrity (or find that there is none) with as few questions as possible?

Facts about a celebrity c:

  • knows(x, c) is true for every x != c.
  • knows(c, x) is false for every x != c.
  • There is at most one celebrity. Two celebrities would have to know each other and not know each other.

Brute force

Test each person against everyone: about 2n questions per person, so O(n^2) in total. We can do much better.

Elimination: one question removes one person

Look at any pair (a, b) and ask knows(a, b):

  • If true, a knows somebody, so a cannot be the celebrity. Throw a away.
  • If false, b is not known by a, so b cannot be the celebrity (everyone must know the celebrity). Throw b away.

Either way, one person leaves the candidate pool. After n - 1 questions, one candidate remains. That candidate is the only possible celebrity; a final pass of at most 2(n - 1) questions verifies them.

flowchart TD
    A["candidate = 0"] --> B["for i = 1 .. n-1"]
    B --> C{"knows(candidate, i)?"}
    C -->|"yes"| D["candidate = i<br/>old candidate knows someone"]
    C -->|"no"| E["keep candidate<br/>i is not known by candidate"]
    D --> B
    E --> B
    B -->|"loop ends"| F["verify the candidate<br/>against everyone"]

A single left-to-right scan keeps one candidate; each question drops one person.

Python Finding the celebrity in O(n) questions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counting questions: the first loop asks n - 1, the verification asks at most 2(n - 1), so the total is at most 3(n - 1), i.e. O(n) time and O(1) space. The verification pass is not optional: elimination only finds the only possible celebrity, and the person may still fail the checks.

Another view: a stack

You can also push everybody on a stack, repeatedly pop two people and push back whichever one survives the question. It is the same elimination, written as n - 1 rounds. The scan above is shorter and uses constant memory.

When the graph is given

If you already have the full matrix, there is an even simpler O(n) idea: the celebrity is the only node with in-degree n - 1 and out-degree 0 in the "knows" graph. Counting degrees from a matrix is O(n^2) to read the whole matrix, so the question-based method wins when each knows call is costly.

The skyline problem

You are given rectangular buildings as (left, right, height) triples, all standing on the ground. When you view them from far away, the outline forms a skyline. Output the skyline as a list of key points (x, height): each point is where the outline changes to a new height, listed left to right. The skyline ends with a point of height 0.

For buildings (2, 9, 10), (3, 7, 15), (5, 12, 12) and (15, 20, 10), the skyline begins (2, 10), (3, 15), (7, 12), (12, 0), ...

flowchart LR
    E["events sorted by x"] --> H["max-heap of active<br/>building heights"]
    H --> C{"max height changed?"}
    C -->|"yes"| K["emit key point (x, new max)"]
    C -->|"no"| N["next event"]
    K --> N

Sweep from left to right; whenever the tallest active building changes, record a key point.

The sweep line idea

Convert each building into two events: at left a building starts with some height, and at right it ends. Sort all events by x. As you sweep, keep the heights of the buildings currently covering the sweep position. The skyline height at any x is the maximum of those heights. Whenever that maximum changes, you output a key point.

A max-heap gives the maximum quickly. Python only has a min-heap, so push negative heights. Removing a building when it ends is awkward for a heap, so use lazy deletion: leave the finished building inside the heap and only discard it when it reaches the top and its right end is not after the current x.

Python Skyline with a heap and lazy deletion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Walk through the first output: at x=2 the tallest is 10, at x=3 the 15 building starts, at x=7 it ends and 12 becomes the tallest, at x=12 nothing is left (height 0), at x=15 a new 10 begins, at x=19 height 10 is still the max (8 does not change it, so no point), at x=20 the 10 ends and 8 remains, and at x=24 the skyline returns to 0.

Handling ties correctly

The classic bugs are about equal coordinates. This implementation processes all buildings with left <= x before reading the height, and drops everything with right <= x before reading it. That means at a shared edge the ending building is removed and the starting one added in the same step, and the "emit only if the height changed" check prevents duplicate key points such as two consecutive points of the same height.

Complexity

Each building is pushed once and popped at most once, at O(log n) each, and sorting costs O(n log n). The total is O(n log n) time and O(n) space. A divide and conquer solution that merges two skylines (like merge sort) reaches the same O(n log n) without a heap.

Spotting these patterns

  • Elimination works when one query can rule out at least one candidate no matter how it is answered. Compare "find the majority element" with Boyer-Moore voting.
  • Sweep line turns a 2D geometry or interval question into a 1D scan over sorted events. The same pattern solves "maximum overlapping meetings", "rectangle union area" and interval scheduling variants.
  • A heap with lazy deletion is a practical replacement for a structure that supports removing arbitrary elements.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the celebrity problem, what does knows(a, b) == True tell you?

    A celebrity knows nobody, so as soon as a knows someone, a is eliminated. If knows(a, b) is False, b is eliminated instead.
  2. 2. Why is a verification pass needed after the elimination scan?

    Elimination leaves one candidate, but that person may still not be known by everyone or may know someone, so we must check.
  3. 3. Why does the skyline algorithm use lazy deletion with a heap?

    A binary heap gives O(log n) access to the maximum, but not cheap removal of arbitrary items. Expired entries are simply ignored until they surface.
  4. 4. What is the time complexity of the sweep-line skyline solution for n buildings?

    Sorting the events costs O(n log n) and each building is pushed and popped once at O(log n) each.

Summary

  • Celebrity: scan once keeping a candidate; knows(candidate, i) true means the candidate is replaced by i. Then verify the final candidate. O(n) questions, O(1) space.
  • At most one celebrity can exist, so the verification either confirms or rejects the lone candidate.
  • Skyline: sort the x-coordinates where something starts or ends, keep a max-heap of (height, right), drop expired buildings from the top, and emit a key point only when the maximum height changes.
  • Handle ties by adding all starts and removing all ends at the same x before reading the height.
  • Both problems are templates: elimination and sweep line show up in many other interview questions.

Next: Project: Autocomplete Engine, where you combine tries and ranking into a working feature.