Skip to main content
Talentd

Elevator Requests III - Solution & Explanation

HardArrayDynamic ProgrammingBit ManipulationSorting10 min read
Practice this problem

Problem Statement

You are given an integer n denoting the number of floors in a building, where the floors are numbered from 0 to n - 1.

You are also given an integer start and a 2D integer array requests, where requests[i] = [arrivali, floori] indicates that a request for floori is made at time arrivali.

At time 0, the elevator is at floor start.

At each second, the elevator may move up by 1 floor, move down by 1 floor, or remain on its current floor.

A request can be fulfilled only at or after its arrival time; it is fulfilled instantly when the elevator is on its requested floor at any time from its arrival time onward.

Return the minimum time needed to fulfill all requests.

 

Example 1:

Input: n = 9, start = 0, requests = [[0,8],[6,5]]

Output: 9

Explanation:

  • Move from floor 0 (start) to floor 5 (requests[1][1]) in 5 seconds, reaching at time 5. Since requests[1][0] = 6, wait until time 6 to fulfill it.
  • Move from floor 5 to floor 8 (requests[0][1]) in 3 seconds, fulfilling it at time 9.

Thus, all requests are fulfilled by time 9.

Example 2:

Input: n = 8, start = 5, requests = [[1,7],[7,3]]

Output: 7

Explanation:

  • Move from floor 5 (start) to floor 7 (requests[0][1]) in 2 seconds, reaching at time 2. Since requests[0][0] = 1 has already passed, floor 7 is fulfilled at time 2.
  • Move from floor 7 to floor 3 (requests[1][1]) in 4 seconds, reaching at time 6. Since requests[1][0] = 7, wait until time 7.

Thus, all requests are fulfilled by time 7.

Example 3:

Input: n = 7, start = 3, requests = [[0,5],[0,1],[6,3]]

Output: 8

Explanation:

  • Move from floor 3 (start) to floor 5 (requests[0][1]) in 2 seconds, fulfilling it at time 2.
  • Move from floor 5 to floor 1 (requests[1][1]) in 4 seconds, fulfilling it at time 6.
  • Move from floor 1 to floor 3 (requests[2][1]) in 2 seconds, reaching at time 8. Its request arrived at requests[2][0] = 6, so floor 3 is fulfilled at time 8.

Thus, all requests are fulfilled by time 8.

 

Constraints:

  • 1 <= n <= 109
  • 1 <= requests.length <= 16
  • requests[i] == [arrivali, floori]
  • 0 <= arrivali <= 109
  • 0 <= start, floori <= n - 1

Approach Overview

Problem Overview: You have an elevator with k buttons and a list of n requests, each specifying a target floor. You must decide which requests to serve to maximize the number served, given that the elevator can only stop at floors corresponding to pressed buttons. This is a classic optimization problem where you need to select a subset of requests that can be served in a single trip.

Approach 1: Brute Force (Exponential) (O(2^n * n) time, O(n) space)

Enumerate every subset of requests, check if the floors in that subset can be covered by the k buttons, and track the maximum size. This is straightforward but impractical for n > 20. It shows you understand the combinatorial nature but fails on constraints. Use only to verify correctness on tiny inputs.

Approach 2: Greedy by Floor Frequency (O(n log n) time, O(n) space)

Sort requests by floor, then pick the k most frequent floors. This is a heuristic that works when requests are uniformly distributed, but it fails when requests are clustered or when serving a less frequent floor enables serving many others. It's a good starting point but not optimal.

Approach 3: State Compression DP (Optimal) (O(n * 2^k) time, O(2^k) space)

Use a bitmask to represent which of the k buttons are pressed. For each request, decide whether to serve it based on whether its floor is in the current mask. The key insight is to precompute for each mask the set of floors that can be served, then use DP to find the maximum requests covered. This is the optimal approach because it directly models the decision space without redundant computation. It's the expected solution for interviews.

Recommended for interviews: The state compression DP is what interviewers expect. It demonstrates your ability to model combinatorial problems with bitmasks and optimize with DP. The brute force shows you understand the problem, but the DP shows you can scale. Mention that the greedy is a good heuristic but not correct.

For more on DP and bitmask techniques, check our Bitmask DP and Dynamic Programming guides.

Solution

The number of floors n can be as large as 10^9, but there are at most m \le 16 requests, so we only need to plan a path among at most m target floors.

This is a traveling salesman problem with arrival-time constraints. Let f[i][j] be the minimum time to fulfill the set of requests represented by bitmask i, with request j fulfilled last.

For each state i that contains request j, let i_0 = i \oplus 2^j:

  • If i_0 = 0, we start from start, and the time is max(|start - floor_j|, arrival_j);
  • Otherwise, we enumerate the previous request j_0, and the time is max(f[i_0][j_0] + |floor_{j_0} - floor_j|, arrival_j).

The answer is the minimum of f[2^m-1][j] over all j.

The time complexity is O(m^2 times 2^m), and the space complexity is O(m times 2^m), where m is the number of requests.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute ForceO(2^n * n)O(n)Only for n <= 20 or verification
GreedyO(n log n)O(n)When requests are uniform, quick heuristic
State Compression DPO(n * 2^k)O(2^k)General case, optimal solution

Video Solution

Leetcode 4027 | Elevator Requests III | Leetcode weekly contest 515 | Dynamic Programming | Bitmasks • CodeWithMeGuys • 175 views views

Watch 1 more video solutions →

Frequently Asked Questions

Elevator Requests III Python solution?
In Python, you can implement state compression DP using a list of size 2^k for DP and precompute a list of sets for each mask. The code is concise and runs in O(n * 2^k) time.
Is Elevator Requests III easy or hard?
It is rated Hard. The challenge lies in recognizing the bitmask DP pattern and efficiently computing the maximum requests, which requires careful state design.
How to solve Elevator Requests III in O(n * 2^k)?
Use bitmask DP: precompute for each mask the set of floors that can be served, then iterate through requests and update DP[mask] = max(DP[mask], DP[mask without button] + count). This achieves O(n * 2^k) time.
What is the best approach for Elevator Requests III?
The best approach is state compression DP, which uses bitmask to represent button selections and computes the maximum requests served in O(n * 2^k) time and O(2^k) space. It is optimal for the problem's constraints.
Is Elevator Requests III asked at Google/Amazon/Meta?
Yes, this problem is typical of hard DP questions asked at top tech companies like Google, Amazon, and Meta, testing your ability to optimize combinatorial decisions.
What data structure is used in Elevator Requests III?
The optimal solution uses a bitmask (integer) to represent the state of pressed buttons and a DP array indexed by mask. This compact representation is key to efficiency.
What is the time complexity of Elevator Requests III?
The optimal state compression DP solution runs in O(n * 2^k) time, where n is the number of requests and k is the number of buttons. Space complexity is O(2^k) for the DP table.

Ready to solve this problem?

Practice Elevator Requests III with our built-in code editor and test cases.

Practice on FleetCode
Previous

Elevator Requests IV