Maximum Reachable Checkpoints — Problem Statement & Solution Guide
Problem Description
Given a list of checkpoints with their respective supply capacities and a team's current stock of food and water, determine the maximum number of checkpoints that can be reached with the current stock. Each checkpoint can only be resupplied once, and a checkpoint can only be traveled to if it is within the current stock's range.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximum Reachable Checkpoints"
WHY DOES IT MATTER?
The greedy + priority queue pattern is crucial for problems where you must extend a resource (fuel, time, capacity) incrementally while selecting the best available option at each step. It guarantees optimality and efficient runtime, which is essential for large datasets typical in production systems.
OPTIMIZATION CHALLENGE
The key insight is that the order of visiting checkpoints does not matter as long as you always use the largest available supply when you need to extend reach. This reduces the problem from combinatorial explosion to a simple O(n log n) sweep.
REAL-WORLD CONNECTION
Think of a delivery drone with limited battery. It can recharge at charging stations. To cover the longest distance, the drone should always choose the station that offers the most battery recharge among those it can reach, just like the algorithm picks the largest supply checkpoint.
When explaining this in an interview, emphasize the invariant: 'At any point, the set of reachable checkpoints is fixed, and we always pick the best one to extend reach.' This shows you understand why the greedy choice is safe.
COMPLEXITY AT A GLANCE
O(n log n)O(n)Core Theory — Why This Approach?
The problem reduces to a classic greedy resource‑extension scenario: you start with an initial stock (food+water) that defines a reachable range, and each checkpoint within that range can add a fixed amount of supply to extend the range further. A naive approach would try every subset of checkpoints, leading to exponential time. The optimal strategy is to always use the checkpoint that provides the maximum additional supply among those currently reachable. This can be implemented by sorting checkpoints by distance and using a max‑heap (priority queue) to store supplies of checkpoints that have become reachable. While the current stock allows reaching new checkpoints, push their supplies into the heap. When the stock is insufficient to reach the next checkpoint, pop the largest supply from the heap, add it to the stock, and continue. This greedy choice is optimal because any other choice would leave a larger supply unused, never improving the ability to reach further checkpoints.
Interview Questions on This Problem
Q1How would you solve the problem of maximizing the number of checkpoints you can visit given an initial stock and checkpoints that each provide additional supply?
I would sort checkpoints by distance, iterate through them while maintaining a max‑heap of supplies of checkpoints that are currently reachable. Whenever the current stock is insufficient to reach the next checkpoint, I pop the largest supply from the heap, add it to the stock, and increment the count. This greedy approach ensures we always extend our reach as efficiently as possible.
Q2Can you explain why a priority queue is essential in this solution?
The priority queue allows us to quickly retrieve the checkpoint with the maximum supply among those reachable at any point. Without it, we would need to scan all reachable checkpoints each time we need to extend our range, which would increase the time complexity from O(n log n) to O(n^2).
Q3What would happen if you processed checkpoints in random order instead of sorted by distance?
Processing in random order could cause the algorithm to miss reachable checkpoints because it might attempt to reach a far checkpoint before a nearer one that could have extended the range. Sorting ensures we consider checkpoints in the order they become reachable, preserving the correctness of the greedy strategy.
Examples
Input
[[10, 5], [20, 10], [30, 15]]
Output
1
Explanation: Step-by-step: with input [[10, 5], [20, 10], [30, 15]] and initial stock of 10, we can only travel to the first checkpoint because the initial stock of 10 is just enough to cover the distance to the first checkpoint and its supply capacity.
Input
[[5, 5], [10, 10], [15, 15]]
Output
3
Explanation: Step-by-step: with input [[5, 5], [10, 10], [15, 15]] and initial stock of 20, we can travel to all checkpoints because the initial stock of 20 is enough to cover the distance to all checkpoints and their supply capacities.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Optimal Approach & Strategy
Sort checkpoints by distance, iterate while maintaining a max‑heap of supplies of reachable checkpoints, and greedily pick the largest supply when the current stock is insufficient to reach the next checkpoint.
Brute Force Approach
Enumerate all subsets of checkpoints, simulate the journey for each subset, and count how many checkpoints can be visited. This is exponential in the number of checkpoints.
Verified Code Solutions
function solution(checkpoints, initialStock) {
let currentStock = initialStock;
let maxReachable = 0;
checkpoints.sort((a, b) => a[0] - b[0]);
for (let i = 0; i < checkpoints.length; i++) {
if (currentStock >= checkpoints[i][0]) {
maxReachable++;
currentStock += checkpoints[i][1];
} else {
break;
}
}
return maxReachable;
}class Solution {
public:
int solution(vector<vector<int>>& checkpoints, int initialStock) {
int currentStock = initialStock;
int maxReachable = 0;
sort(checkpoints.begin(), checkpoints.end());
for (int i = 0; i < checkpoints.size(); i++) {
if (currentStock >= checkpoints[i][0]) {
maxReachable++;
currentStock += checkpoints[i][1];
} else {
break;
}
}
return maxReachable;
}
}class Solution {
public int solution(int[][] checkpoints, int initialStock) {
int currentStock = initialStock;
int maxReachable = 0;
Arrays.sort(checkpoints, (a, b) -> a[0] - b[0]);
for (int i = 0; i < checkpoints.length; i++) {
if (currentStock >= checkpoints[i][0]) {
maxReachable++;
currentStock += checkpoints[i][1];
} else {
break;
}
}
return maxReachable;
}
}def solution(checkpoints, initial_stock):
current_stock = initial_stock
max_reachable = 0
checkpoints.sort(key=lambda x: x[0])
for i in range(len(checkpoints)):
if current_stock >= checkpoints[i][0]:
max_reachable += 1
current_stock += checkpoints[i][1]
else:
break
return max_reachablefunction solution(checkpoints, initialStock) {
let currentStock = initialStock;
let maxReachable = 0;
checkpoints.sort((a, b) => a[0] - b[0]);
for (let i = 0; i < checkpoints.length; i++) {
if (currentStock >= checkpoints[i][0]) {
maxReachable++;
currentStock += checkpoints[i][1];
} else {
break;
}
}
return maxReachable;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.