Leetcode 1642 - Furthest Building You Can Reach

Subscribe Send me a message home page tags


Problem

You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.

You start your journey from building 0 and move to the next building by possibly using bricks or ladders.

While moving from building i to building i+1 (0-indexed),

If the current building's height is greater than or equal to the next building's height, you do not need a ladder or bricks.

If the current building's height is less than the next building's height, you can either use one ladder or (h[i+1] - h[i]) bricks.

Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.

Solution

A greedy algorithm seems to be an appropriate solution. We should use ladders to cover the largest gaps between two buildings. Therefore, we need to track the largest gaps we have seen so far when we go throught the list of buildings. A priority queue is can be used as it's the data structure desigend for this type of tasks.

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class Solution {

public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {

        // Special case. If there is no bricks and no ladders,
        // the result is the lenght of the longest non-decreasing sub list.
        if (bricks == 0 && ladders == 0) {
            size_t k = 0;

            while (k < heights.size() - 1) {
                if (heights[k] >= heights[k+1]) {
                    ++k;
                } else {
                    return k;
                }
            }
            return k;
        }

        size_t k = 0;
        int remainingBricks = bricks;
        int remainingLadders = ladders;

        // Uss a priority queue to keep the largest cost.
        // The cost is the number of bricks we need to jumpt to next building.
        priority_queue<int> q{};

        while (remainingBricks + remainingLadders > 0) {

            if (k == heights.size() - 1) {
                return k;
            }

            int cost = heights[k+1] - heights[k];

            if (cost < 0) {
                // We don't need to do anything. Just move to the next building.
                ++k;
            } else if (cost <= remainingBricks) {
                // If we have enough bricks, use them and move forward.
                remainingBricks -= cost;
                q.push(cost);
                ++k;
            } else {
                // In this case, we don't have enough bricks.

                if (q.empty()) { // we haven't used any bricks
                    if (remainingLadders > 0) {
                        --remainingLadders;
                        ++k;
                    } else {
                        // if we don't have ladders, then we cannot move forward.
                        return k;
                    }
                } else {
                    // replace the bricks with a ladder.
                    int potentialRefund = q.top();

                    if (potentialRefund <= cost && remainingLadders > 0) {
                        --remainingLadders;
                        ++k;
                    } else {
                        // We need to use a ladder to replace some bricks.
                        while (remainingLadders > 0 && cost > remainingBricks) {
                            int refund = q.top();
                            q.pop();
                            --remainingLadders;
                            remainingBricks += refund;
                        }

                        if (remainingLadders == 0 && cost > remainingBricks) {
                            return k;
                        }
                    }
                }
            }
        }
        return k;
    }
};

----- END -----

Welcome to join reddit self-learning community.
Send me a message Subscribe to blog updates

Want some fun stuff?

/static/shopping_demo.png