Leetcode 1642: Furthest Building You Can Reach
You are given an array
heights representing the heights of buildings, along with a certain number of bricks and ladders. Your task is to determine the furthest building you can reach by optimally using bricks and ladders.Problem
Approach
Steps
Complexity
Input: You are given an array `heights` of length `n`, where each element represents the height of a building. You are also given two integers: `bricks` (the number of bricks available) and `ladders` (the number of ladders available).
Example: heights = [7, 12, 6, 9, 5, 17, 21, 4, 18], bricks = 15, ladders = 3
Constraints:
• 1 <= heights.length <= 10^5
• 1 <= heights[i] <= 10^6
• 0 <= bricks <= 10^9
• 0 <= ladders <= heights.length
Output: Return the furthest building index (0-indexed) you can reach using the given ladders and bricks optimally.
Example: 4
Constraints:
• Return -1 if you cannot move beyond the first building.
Goal: To move from building to building, using bricks and ladders optimally for the height differences.
Steps:
• 1. Calculate the height difference between each consecutive building.
• 2. Use ladders for the largest height differences first.
• 3. Use bricks for the remaining height differences.
• 4. Stop when you run out of bricks or ladders, and return the furthest building index.
Goal: Ensure you handle up to the maximum constraints efficiently.
Steps:
• The input array can have up to 100,000 elements.
• The number of bricks and ladders can be large, so optimize for performance.
Assumptions:
• Assume the height array is non-empty.
• Assume the number of ladders is non-negative and within the bounds of the array length.
• Input: heights = [5, 3, 8, 7, 10, 15, 13], bricks = 8, ladders = 2
• Explanation: You can move from building 0 to building 4 by optimally using bricks for the height difference between buildings 1 and 2 and using a ladder for the difference between buildings 3 and 4.
Approach: We need to use ladders first for the largest height differences, and use bricks for the smaller ones, to maximize the furthest building we can reach.
Observations:
• Ladders should be used for the largest height differences to save bricks.
• Bricks should be used for smaller height differences when ladders are exhausted.
• Use a priority queue to manage the height differences and decide where to use bricks or ladders.
Steps:
• 1. Calculate the height differences between each building pair.
• 2. Maintain a priority queue to store the largest height differences.
• 3. Start from the first building and move towards the last, using ladders and bricks based on the height differences.
Empty Inputs:
• The input heights array is empty.
Large Inputs:
• Ensure the solution handles large arrays and large numbers of bricks and ladders efficiently.
Special Values:
• When there are no height differences, no bricks or ladders are needed.
Constraints:
• Ensure that the solution works within the provided constraints.
int furthestBuilding(vector<int>& h, int bri, int lad) {
int n = h.size();
vector<int> bc(n - 1, 0);
for(int i = 0; i < n - 1; i++) {
bc[i] = h[i + 1] - h[i] < 0 ? 0: h[i + 1] - h[i];
// cout << bc[i] << " ";
}
// cout << "\n";
priority_queue<int, vector<int>, greater<int>> pq;
int i = 0, sum = 0;
for(; i < n - 1; i++) {
if(bc[i] == 0) continue;
if(pq.size() < lad) {
pq.push(bc[i]);
} else {
pq.push(bc[i]);
if(sum + pq.top() <= bri)
sum += pq.top();
else return i;
pq.pop();
}
}
// cout << sum << " " << bri << " " << i;
return n - 1;
// Use ladders first
// when ladders are over
// check are them could be replaced with bricks
// if yes, continue to assigning released ladder
// else return where it had overflown
}
1 : Function Definition
int furthestBuilding(vector<int>& h, int bri, int lad) {
The function starts by defining the function signature and initializing the variables for the number of buildings (h), bricks (bri), and ladders (lad).
2 : Variable Initialization
int n = h.size();
The size of the building heights array is stored in the variable 'n' to be used for iteration.
3 : Array Initialization
vector<int> bc(n - 1, 0);
An array 'bc' is initialized to store the differences in heights between consecutive buildings.
4 : Loop
for(int i = 0; i < n - 1; i++) {
A loop starts from the first building to calculate the height difference between each consecutive building.
5 : Height Difference Calculation
bc[i] = h[i + 1] - h[i] < 0 ? 0: h[i + 1] - h[i];
The height difference is calculated and stored in the 'bc' array. If the difference is negative, it is set to 0.
6 : Priority Queue Initialization
priority_queue<int, vector<int>, greater<int>> pq;
A priority queue 'pq' is initialized to manage the smallest height differences when traversing buildings.
7 : Variable Initialization
int i = 0, sum = 0;
Two variables 'i' (for the current building index) and 'sum' (to track the total bricks used) are initialized.
8 : Loop
for(; i < n - 1; i++) {
A loop starts to iterate over each building to check if the height difference can be covered with the available resources.
9 : Check if Height Difference is Zero
if(bc[i] == 0) continue;
If the height difference between buildings is zero, no resources are needed, and the loop continues.
10 : Check Ladder Availability
if(pq.size() < lad) {
If there are still ladders available, push the current height difference into the priority queue.
11 : Push to Priority Queue
pq.push(bc[i]);
Push the current building height difference into the priority queue.
12 : Else Block
} else {
If no ladders are available, the program uses bricks to cover the building gap.
13 : Push to Priority Queue Again
pq.push(bc[i]);
Push the current building height difference into the priority queue.
14 : Check if Bricks are Sufficient
if(sum + pq.top() <= bri)
Check if the total sum of bricks used so far and the top of the priority queue (smallest height difference) is less than or equal to the available bricks.
15 : Update Brick Usage
sum += pq.top();
If bricks are sufficient, add the current smallest height difference to the sum of bricks used.
16 : Return if Bricks are Insufficient
else return i;
If the current height difference cannot be covered with the available bricks, return the current building index.
17 : Pop from Priority Queue
pq.pop();
Remove the smallest height difference from the priority queue.
18 : Return Result
return n - 1;
Return the index of the furthest building that can be reached using the available ladders and bricks.
Best Case: O(n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The worst case occurs when we need to process all the height differences and manage the priority queue.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is primarily determined by the space used for the priority queue.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus