# Elevator

Course: [Low-Level Design](https://www.devtutorials.ai/learn/system-design/lld) · Section: LLD Case Studies
Source: https://www.devtutorials.ai/learn/system-design/lld/case-studies/elevator

> Design an elevator that serves floors fairly: time in steps, a set of requests, and the elevator algorithm, tested step by step.

Think about the lift in a tall office building at 9 a.m. People on many floors are pressing buttons. The lift must decide where to go next, again and again. If it decides badly, someone on floor 8 waits forever.

In this case study, you will design an elevator system for QuickBite’s new office tower. The system will manage floor requests, lift movement, stops, and the order in which requests are handled.

**In simple words:** we will build a lift that moves one floor per step and serves floors in a fair order, and prove it with hidden tests.

## What You Will Learn

In this case study, you will:

1. Model time as steps, so behaviour can be tested exactly.
2. Store requests so that pressing twice is one stop.
3. Use the elevator algorithm: keep going one way, then turn.
4. See why nearest-first is unfair.
5. Build the elevator in the sandbox and pass the hidden tests.

Elevator questions are really about **choosing the next step** from a state. Write the rule down in plain words first ("keep going while anyone is waiting that way"), then code it.

## Step 1: Agree on the Requirements

Before any code, write down what the system must do. In an interview, say these out loud and ask if they are right.

### What It Must Do

- One lift, floors 0 and up.
- `press(floor)` adds a request; pressing the same floor twice is one request.
- Each `step()` moves exactly one floor, or does nothing when there are no requests.
- The lift keeps moving in its direction while there are requests that way, then turns around.
- When idle, it starts towards the nearest request.
- It records each floor where the doors open.

### What We Leave Out

- Several lifts (we sketch a dispatcher, but the lab uses one).
- Door timers, weight limits and emergency stops.
- Up and down call buttons as separate requests.

Leaving things out on purpose is not lazy. It keeps the design small enough to finish, and you can say how you would add them later.

## Step 2: Find the Classes

A simple trick: underline the **nouns** in the requirements. Most of them become classes. The **verbs** become methods.

| Class | Its one job |
|---|---|
| Elevator | Knows its floor, direction and requests; moves one step at a time |
| Request set | The floors still to visit, without repeats |
| Dispatcher | With many lifts: decides which lift answers a call |

<LldDiagram caption="The class diagram for this design." code={"classDiagram\n  class Elevator {\n    +floor: number\n    +stops: number[]\n    -direction: Direction\n    -requests: Set\n    +press(floor) void\n    +step() void\n    +idle: boolean\n  }\n  class Dispatcher {\n    -lifts: Elevator[]\n    +call(floor) Elevator\n  }\n  Dispatcher --> Elevator : sends"} />

## Step 3: Build the Key Parts

### Time in Steps

A real elevator moves continuously. A program that is easy to test moves in **steps**: each call to `step()` moves one floor. Tests then know exactly where the lift is.

Step through three calls to `step("up")`. After them the lift is on floor 3, every time:

Here is the same idea in code:

```ts runnable title="Time moves in steps, so tests are exact"
class Lift {
  floor = 0;
  step(direction: "up" | "down"): void {
    this.floor += direction === "up" ? 1 : -1;
  }
}

const lift = new Lift();
lift.step("up");
lift.step("up");
lift.step("up");
console.log("floor", lift.floor);
```

Expected output:

```text
floor 3
```

### Requests

People inside press floor buttons. People outside call the lift. Both just mean "please stop at this floor". A `Set` stores them, so pressing twice does not create two stops.

Step through three presses: 5, 2, then 5 again. The set ends up holding just 2 and 5, and `has(5)` is true:

Here is the same idea in code:

```ts runnable title="Requests in a Set: pressing twice is one request"
const requests = new Set<number>();
requests.add(5);
requests.add(2);
requests.add(5); // pressed again: still one request

console.log([...requests].sort((a, b) => a - b));
console.log("has 5?", requests.has(5));
```

Expected output:

```text
[
  2,
  5
]
has 5? true
```

### Which Way Next?

The key rule: **keep going in the same direction while anyone is waiting that way.** Only turn around when nobody is.

A helper `hasRequestsAhead(floor, direction, requests)` looks at every waiting floor, not just the next one. With floors 1 and 6 waiting:

```ts runnable title="Is anyone waiting further in this direction?"
function hasRequestsAhead(floor: number, direction: "up" | "down", requests: Set<number>): boolean {
  for (const f of requests) {
    if (direction === "up" && f > floor) return true;
    if (direction === "down" && f < floor) return true;
  }
  return false;
}

const waiting = new Set([1, 6]);
console.log(hasRequestsAhead(3, "up", waiting));   // 6 is above
console.log(hasRequestsAhead(7, "up", waiting));   // nothing above 7
console.log(hasRequestsAhead(7, "down", waiting)); // 6 and 1 are below
```

Expected output:

```text
true
false
true
```

### Why Not Just Go to the Nearest Floor?

Going to the nearest request sounds clever. But it zig-zags, and someone at the far end can wait for a very long time.

The chart traces both rules from floor 3 with calls 4, 1, 6 and 2. Nearest-first goes **4 2 1 6**. The elevator algorithm goes **4 6 2 1**:

Step through the elevator algorithm one stop at a time:

Here is the same idea in code:

```ts runnable title="Nearest-first zig-zags; the elevator algorithm does not"
// Nearest-first: always go to the closest request.
function nearestFirst(start: number, requests: number[]): number[] {
  const left = [...requests];
  const order: number[] = [];
  let at = start;
  while (left.length) {
    left.sort((a, b) => Math.abs(a - at) - Math.abs(b - at));
    at = left.shift()!;
    order.push(at);
  }
  return order;
}

// Elevator algorithm: everything above in order, then everything below.
function sweepUp(start: number, requests: number[]): number[] {
  const up = requests.filter((f) => f >= start).sort((a, b) => a - b);
  const down = requests.filter((f) => f < start).sort((a, b) => b - a);
  return [...up, ...down];
}

const calls = [4, 1, 6, 2];
console.log("nearest first:", nearestFirst(3, calls).join(" "));
console.log("elevator:     ", sweepUp(3, calls).join(" "));
```

Expected output:

```text
nearest first: 4 2 1 6
elevator:      4 6 2 1
```

The elevator algorithm (also called **SCAN**) serves everyone on the way up, then everyone on the way down. Nobody waits forever.

**Easy way to remember:** an elevator is like a bus on a straight road. It does not turn around for every new passenger. It drives to the end of the route, then comes back.

### More Than One Lift

A building with several lifts adds a **dispatcher**: a class that decides which lift answers a call. A simple rule is "the closest idle lift".

Step through two calls with three lifts. A is on floor 2 but busy, B is idle on floor 9, and C is idle on floor 0. A call from floor 3 gets **C**; a call from floor 8 gets **B**:

Here is the same idea in code:

```ts runnable title="Choosing between two lifts"
type Lift = { name: string; floor: number; busy: boolean };

// Prefer an idle lift; among those, the closest one.
function choose(lifts: Lift[], callFloor: number): string {
  const idle = lifts.filter((l) => !l.busy);
  const pool = idle.length > 0 ? idle : lifts;
  pool.sort((a, b) => Math.abs(a.floor - callFloor) - Math.abs(b.floor - callFloor));
  return pool[0].name;
}

const lifts: Lift[] = [
  { name: "A", floor: 2, busy: true },
  { name: "B", floor: 9, busy: false },
  { name: "C", floor: 0, busy: false },
];
console.log(choose(lifts, 3));
console.log(choose(lifts, 8));
```

Expected output:

```text
C
B
```

Keep the dispatcher separate from the lift. The lift knows how to move and stop. The dispatcher knows which lift to send. Mixing them gives one class with two reasons to change.

## Lab: Build It

Build the `Elevator` class. The hidden tests press buttons, call `step()` many times, and check the order of stops.

1. Keep the requests in a `Set` and a direction of `up`, `down` or `none`.
2. In `step()`: when idle, head towards the nearest request; turn around when nothing is ahead; move one floor; stop if this floor was requested.
3. Make `idle` true when no requests are left.

Open the lab in the sandbox. Run the tests after each step. A failing test names the situation that broke, not the test code.

## Predict the Output

<CsPredict id="lift-1" code={"var requests = new SortedSet<int> { 6, 1, 4 };\nint at = 2;\nvar up = requests.Where(f => f > at);\nvar down = requests.Where(f => f < at).Reverse();\nConsole.WriteLine(string.Join(\",\", up.Concat(down)));"} expected={"4,6,1"} why="SortedSet keeps 1, 4, 6 in order. Floors above 2 are 4 and 6, in order. Floors below are just 1. Up first, then down." />

## Common Mistakes

| Mistake | Wrong | Correct | Why it happens |
|---|---|---|---|
| Zig-zagging | Always going to the nearest request. | Keep going while anyone is waiting that way. | Nearest-first looks efficient in small tests. |
| Duplicate stops | An array of presses: [5, 5]. | A Set of floors. | Arrays are the default list. |
| Teleporting | floor = target in one step. | Move one floor per step. | It is the shortest code. |
| Turning too early | Turning when the next request is behind, even with one ahead. | Turn only when nothing is ahead. | Checking only the next request, not all of them. |
| Lift chooses itself | Each lift grabs calls it hears. | A dispatcher assigns calls. | It works fine with one lift. |

## Practice

## What to Remember

- Move in **steps**, so tests are exact.
- Requests live in a **Set**.
- **Keep going** in one direction while anyone is waiting that way, then turn.
- Nearest-first is **unfair**; the elevator algorithm is not.
- With many lifts, a **dispatcher** chooses which one goes.

## Further Reading

These are the sources used to check this case study:

- [Wikipedia: Elevator algorithm](https://en.wikipedia.org/wiki/Elevator_algorithm): the SCAN strategy.
- [MDN: Set](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set): storing requests without repeats.
- [TypeScript Handbook: Classes](https://www.typescriptlang.org/docs/handbook/2/classes.html): getters and private fields.

Next: **LRU Cache**. You will build a cache that forgets the least recently used item first.