SCAN (Elevator) Algorithm
What is it? (The Analogy)
Think about how an elevator works in a tall building. When you press the button on floor 7,
the elevator does not immediately rush to your floor. Instead, it **continues in its current
direction**, picking up and dropping off people along the way. If it is going UP and is
currently at floor 4, it will stop at 5, 7, 9 (whoever pressed), reach the top, and then
reverse direction and come back down.
This is exactly the SCAN algorithm (also called the Elevator algorithm). It was
originally designed for disk scheduling — deciding the order in which a hard drive's
read/write head visits different locations on the disk. But the same idea applies beautifully
to many LLD problems: elevator systems, cab routing, printer queue optimization, and more.
The key principle is: **keep moving in one direction, serving all requests along the way,
until there are no more requests in that direction. Then reverse.** This minimizes the total
distance traveled and prevents "starvation" — the situation where a request keeps getting
skipped.
Why do we need it?
The Problem: Naive Request Handling
Imagine a pizza delivery driver who always goes to the most recently ordered address.
If new orders keep coming from the north side of town, a customer in the south might wait
forever. That is starvation.
Or consider a driver who always goes to the nearest address (Shortest Seek First). This
seems smart, but if orders cluster in one area, distant orders starve:
1// NAIVE: Always go to the nearest request (Shortest Seek First)
2// Problem: Requests far away may NEVER get served if new nearby requests keep arriving
3int serveNearest(int currentPos, List<Integer> requests) {
4 int nearest = -1;
5 int minDist = Integer.MAX_VALUE;
6 for (int req : requests) {
7 if (Math.abs(req - currentPos) < minDist) {
8 minDist = Math.abs(req - currentPos);
9 nearest = req;
10 }
11 }
12 return nearest; // Far-away requests starve!
13}The Better Way: SCAN
SCAN guarantees fairness — every request will be served within at most 2 full sweeps
of the range. It also provides predictable service times and minimizes unnecessary
back-and-forth movement.
How it works — Step by Step
- Start at the current position, moving in a chosen direction (UP or DOWN).
- Sort all pending requests.
- Move in the current direction, serving each request you encounter along the way.
- When you reach the end (no more requests in this direction, or you hit the boundary),
reverse direction.
- Continue moving in the new direction, serving requests along the way.
- Repeat until all requests are served.
Variation — LOOK Algorithm: Instead of going all the way to the boundary, the LOOK
variant reverses direction as soon as there are no more requests ahead. This is more
efficient and is what real elevators usually implement.
Let's Build It Together
Let's build an Elevator Controller for a 20-story school building. Students press buttons
on different floors, and our elevator needs to serve them efficiently.
1import java.util.*;
2
3/**
4 * ElevatorController — implements the SCAN (Elevator) Algorithm.
5 *
6 * Scenario: A school elevator in a 20-story building.
7 * Students keep pressing buttons, and we serve them fairly.
8 */
9public class ElevatorController {
10
11 private int currentFloor;
12 private boolean goingUp; // true = moving UP, false = moving DOWN
13 private int minFloor; // lowest floor (0 = ground)
14 private int maxFloor; // highest floor
15 private TreeSet<Integer> upRequests; // Floors requested while going up
16 private TreeSet<Integer> downRequests; // Floors requested while going down
17
18 public ElevatorController(int minFloor, int maxFloor) {
19 this.minFloor = minFloor;
20 this.maxFloor = maxFloor;
21 this.currentFloor = 0;
22 this.goingUp = true;
23 // TreeSet keeps floors sorted — crucial for SCAN!
24 this.upRequests = new TreeSet<>();
25 this.downRequests = new TreeSet<>();
26 }
27
28 /**
29 * A student presses a button to go to a floor.
30 * We decide which set to put it in based on whether
31 * it is ahead of us or behind us.
32 */
33 public void addRequest(int floor) {
34 if (floor > currentFloor) {
35 upRequests.add(floor);
36 } else if (floor < currentFloor) {
37 downRequests.add(floor);
38 }
39 // If floor == currentFloor, we are already there!
40 }
41
42 /**
43 * Process all current requests using the SCAN algorithm.
44 * Returns the order of floors visited.
45 */
46 public List<Integer> processRequests() {
47 List<Integer> visitOrder = new ArrayList<>();
48
49 while (!upRequests.isEmpty() || !downRequests.isEmpty()) {
50 if (goingUp) {
51 // Serve all floors ABOVE us, in ascending order
52 while (!upRequests.isEmpty()) {
53 int nextFloor = upRequests.pollFirst(); // smallest floor above us
54 currentFloor = nextFloor;
55 visitOrder.add(currentFloor);
56 }
57 // No more up requests — reverse direction!
58 goingUp = false;
59 } else {
60 // Serve all floors BELOW us, in descending order
61 while (!downRequests.isEmpty()) {
62 int nextFloor = downRequests.pollLast(); // largest floor below us
63 currentFloor = nextFloor;
64 visitOrder.add(currentFloor);
65 }
66 // No more down requests — reverse direction!
67 goingUp = true;
68 }
69 }
70
71 return visitOrder;
72 }
73
74 /**
75 * Calculate total distance traveled (in floors).
76 */
77 public static int totalDistance(int startFloor, List<Integer> visitOrder) {
78 int distance = 0;
79 int current = startFloor;
80 for (int floor : visitOrder) {
81 distance += Math.abs(floor - current);
82 current = floor;
83 }
84 return distance;
85 }
86}Using it:
1public class SchoolElevator {
2 public static void main(String[] args) {
3 ElevatorController elevator = new ElevatorController(0, 20);
4
5 // Elevator is at floor 8, going UP
6 // Students press buttons for these floors:
7 int[] requests = {3, 12, 5, 18, 1, 15, 10};
8
9 for (int floor : requests) {
10 elevator.addRequest(floor);
11 }
12
13 // Process using SCAN
14 List<Integer> order = elevator.processRequests();
15 System.out.println("Visit order: " + order);
16 System.out.println("Total floors traveled: "
17 + ElevatorController.totalDistance(8, order));
18 }
19}Now let's see a disk scheduling version, which is the classic SCAN use case:
1import java.util.*;
2
3/**
4 * DiskScheduler — SCAN algorithm for disk head movement.
5 *
6 * The disk has tracks numbered 0 to maxTrack.
7 * The head starts at a given position and serves read/write requests.
8 */
9public class DiskScheduler {
10
11 /**
12 * Given a starting position and a list of track requests,
13 * return the order tracks are visited using SCAN.
14 *
15 * @param start current head position
16 * @param requests list of requested track numbers
17 * @param goingUp initial direction (true = toward higher tracks)
18 * @param maxTrack highest track number on the disk
19 * @return ordered list of tracks visited
20 */
21 public static List<Integer> scan(int start, List<Integer> requests,
22 boolean goingUp, int maxTrack) {
23 List<Integer> result = new ArrayList<>();
24
25 // Separate requests into those ahead and those behind
26 TreeSet<Integer> ahead = new TreeSet<>();
27 TreeSet<Integer> behind = new TreeSet<>();
28
29 for (int req : requests) {
30 if (goingUp) {
31 if (req >= start) ahead.add(req);
32 else behind.add(req);
33 } else {
34 if (req <= start) behind.add(req);
35 else ahead.add(req);
36 }
37 }
38
39 // Phase 1: Serve requests in current direction
40 if (goingUp) {
41 // Serve ascending
42 for (int track : ahead) {
43 result.add(track);
44 }
45 // Phase 2: Reverse and serve descending
46 for (int track : behind.descendingSet()) {
47 result.add(track);
48 }
49 } else {
50 // Serve descending
51 for (int track : behind.descendingSet()) {
52 result.add(track);
53 }
54 // Phase 2: Reverse and serve ascending
55 for (int track : ahead) {
56 result.add(track);
57 }
58 }
59
60 return result;
61 }
62}Dry Run / Trace
Scenario: Elevator at floor 8, going UP. Requests: [3, 12, 5, 18, 1, 15, 10]
Step 1: Categorize requests
Current floor: 8, Direction: UP
Floors ABOVE 8 (upRequests): {10, 12, 15, 18} (sorted in TreeSet)
Floors BELOW 8 (downRequests): {1, 3, 5} (sorted in TreeSet)Step 2: Process UP direction first (ascending order)
Visit floor 10 | distance from 8: |10 - 8| = 2 | total: 2
Visit floor 12 | distance from 10: |12 - 10| = 2 | total: 4
Visit floor 15 | distance from 12: |15 - 12| = 3 | total: 7
Visit floor 18 | distance from 15: |18 - 15| = 3 | total: 10
No more UP requests. REVERSE direction!Step 3: Process DOWN direction (descending order)
Visit floor 5 | distance from 18: |5 - 18| = 13 | total: 23
Visit floor 3 | distance from 5: |3 - 5| = 2 | total: 25
Visit floor 1 | distance from 3: |1 - 3| = 2 | total: 27
No more DOWN requests. Done!Final result:
Visit order: [10, 12, 15, 18, 5, 3, 1]
Total distance: 27 floorsCompare with naive (serve in order received): [3, 12, 5, 18, 1, 15, 10]
8→3 (5) + 3→12 (9) + 12→5 (7) + 5→18 (13) + 18→1 (17) + 1→15 (14) + 15→10 (5) = 70SCAN traveled 27 floors vs. naive 70 floors — a 61% reduction in movement!
Time & Space Complexity
| Approach | Time | Space | Fairness |
|---|---|---|---|
| First Come First Served (FCFS) | O(N) | O(N) | Fair but wasteful |
| Shortest Seek First (SSF) | O(N^2) or O(N log N) | O(N) | Unfair (starvation) |
| SCAN (Elevator) | O(N log N) | O(N) | Fair + efficient |
- Time: O(N log N) to sort the requests, then O(N) to serve them. The sort dominates.
- Space: O(N) to store the requests.
- Key advantage: SCAN guarantees bounded wait time. In the worst case, a request waits
for at most 2 complete sweeps. No starvation.
Common Mistakes & Gotchas
- Forgetting to handle the direction reversal. The whole point of SCAN is the sweep and
reverse pattern. Without the reversal, it is just a sorted traversal.
- Not distinguishing SCAN from LOOK. SCAN goes all the way to the boundary (floor 0 or
floor 20) before reversing. LOOK reverses at the last request. Most real systems use LOOK,
which is slightly more efficient.
- Ignoring new requests that arrive during processing. In a real system, requests arrive
continuously. You need to decide: do new requests get added to the current sweep, or the
next one? (C-SCAN variant adds them to the next sweep for fairness.)
- Not handling the case where the elevator is already at a requested floor. If someone
requests floor 8 and the elevator is at floor 8, serve immediately.
- Confusing the direction of the initial sweep. Always be clear about the starting
direction. It affects which requests are served first.
Interview Tip
In LLD interviews, the Elevator problem is a classic. The interviewer is not just
looking for a working solution — they want to see that you understand the trade-offs
between different scheduling strategies. Mention FCFS (fair but slow), SSF (fast but
unfair), and SCAN (balanced). Bonus points: discuss C-SCAN (Circular SCAN) which only
serves requests in one direction, then jumps back to the start, providing more uniform
wait times. Also mention the LOOK optimization.
Quick Quiz
- Think about it: If all requests are on one side of the elevator (say all above it),
does SCAN behave any differently from simply sorting and visiting in order?
- Design question: In a building with 3 elevators, how would you extend the SCAN
algorithm? Would each elevator run its own independent SCAN, or would you coordinate them?
- Edge case: What happens if a new request arrives for a floor that the elevator just
passed? Should it be served in the current sweep (turn around) or the next sweep
(continue forward)?
Summary — Key Takeaways
- SCAN moves in one direction, serves all requests, then reverses — just like an
elevator. This minimizes back-and-forth movement.
- It prevents starvation — every request is guaranteed to be served within 2 sweeps
of the range, unlike Shortest Seek First which can starve distant requests.
- The LOOK variant (reverse at last request instead of boundary) is what real systems
use. Mention both in interviews.
- SCAN applies beyond elevators — disk scheduling, print queue optimization, cab routing,
and any system where a "head" or "agent" moves along a linear range serving requests.