Furthest Building You Can Reach Algorithm - JavaScript

Question

I'm trying to create a solution for the problem below in JavaScript.

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.

Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Explanation: Starting at building 0, you can follow these steps:
- Go to building 1 without using ladders nor bricks since 4 >= 2.
- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7.
- Go to building 3 without using ladders nor bricks since 7 >= 6.
- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9.
It is impossible to go beyond building 4 because you do not have any more bricks or ladders.

My naive solution:

var furthestBuilding = function(heights, bricks, ladders) {
    let pos = 0;
    
    while(pos < heights.length) {
        if(pos === heights.length - 1)  break;
        if(heights[pos+1] > heights[pos]) {
            const distance = heights[pos+1] - heights[pos];
            if(distance <= bricks)  bricks -= distance;
            else if(ladders > 0)    ladders--;
            else    break;
        }
        pos++;
    }
    
    return pos;
};

It does return the expected result for the example above. However, it fails for the input below.

heights = [1,5,1,2,3,4,10000]
bricks = 4
ladders = 1

My output is 3, but the solution should be 5.

Input that crashes for the recursive solution.

heights = [253710,459585,71981,223232,977918,148680,123527,250812,260416,554767,473621,88538,966794,644116,865416,590993,550004,374573,105036,568303,460987,24602,757598,519047,263800,315868,963895,266638,598245,713310,489802,364169,742274,973483,807739,253747,564636,472387,598445,675408,626061,527760,922748,244691,41163,108095,953208,54400,191957,182321,801110,526756,11220,560896,782344,565351,570890,931781,511665,108738,357367,853555,674526,388790,686349,554731,102668,335287,461231,496065,489980,525209,693696,140598,784402,564477,743153,156379,370768,94810,121932,338323,972441,553422,865236,627884,673412,16147,858309,802780,150410,657225,761430,916149,644587,364929,661236,207648,507409,209803,663553,296241,51843,758342,448408,310536,733500,390516,580506,313748,729366,961156,766804,752158,713426,946971,433800,611365,806559,950149,831368,871881,132092,644626,150762,487527,365094,316637,684249,740162,605893,272845,416251,905202,984909,602362,424697,686193,566240,159584,600277,767037,211677,441897,586509,965864,393340,497044,881539,145921,159055,866123,603476,657682,284714,85306,470415,534245,641462,472616,159434,421500,843442,634366,625668,444943,657933,129173,914540,215272,598415,457087,437568,490742,172811,212016,435680,599042,789308,279873,689943,369130,618428,524390,877649,118759,60586,37618,20797,492854,946585,583767,944693,62988,358292,708659,23496,966718,557539,131703,358231,215464,771609,375770,855917,147866,543477,786910,760512,468183,542081,373398,979543,126508,361409,842847,872593,746682,893518,457222,978730,161753,697245,205997,363180,807952,795175,808090,462585,658667,186220,858457,923762,700792,294201,584816,514737,261038,327627,205592,221896,444108,979369,129394,44001,790354,353917,72772,330118,360651,635275,849492,966042,843108,158554,406317,995111,147752,121006,486157,678653,217657,4288,573547,820817,164534,921608,308037,373838,385901,343399,813472,58859,346176,68090,539503,322652,958331,832724,585003,75794,228299,31211,302603,601041,362034,300803,347024,650585,172193,876895,603734,165956,796982,786231,738823,562729,158032,364908,988395,775023,671485,424571,572157,623273,772919,914302,661979,920229,614760,934156,511607,889533,382154,82654,973121,549095,639792,412821,305216,74071,571794,969979,932469,335153,898442,938912,729489,872970,874332,8390,345366,901364,245104,315592,895028,533836,427909,737421,161915,510434,768573,179267,237370,562023,650593,869876,544314,464374,701215,789191,746271,871247,385836,788092,890101,286938,367130,635751,295576,607054,913206,556383,512305,253121,461980,951444,192012,897432,140517,842228,924286,268918,765459,344159,347853,592899,247814,379693,421908,295638,672994,774285,78096,886320,998456,10915,581642,549650,905526,186991,586693,320053,829130,465779,191060,238711,415584,273709,35854,55818,305798,667280,334370,121051,665390,230729,51662,904228,971349,7088,567705,265941,380847,760602,280222,351148,518112,609328,381795,46766,301829,886537,338310,130937,813816,446885,126867,578861,996302,56516,316900,648733,457604,903338,974707,336231,878687,776626,583241,353383,591761,438716,892530,231901,959454,915103,50735,453313,519651,940657,68380,38339,339705,19207,844122,483005,582959,592635,870233,208322,862826,598864,989646,583679,219396,371194,111781,493739,313465,383867,545219,171577,761747,992356,973874,497603,976481,136374,138311,918066,787696,929197,589326,801358,944697,28038,211029,752621,210197,491050,939207,254024,145811,767376,922553,796100,15858,899164,950319,728378,563113,532136,705190,290216,359946,214594,327241,641000,385347,786200,700340,576438,227606,498337,451637,425192,286305,472053,335562,587556,683468,290205,997253,868480,320419,392391,128015,674737,410783,136490,46713,154232,574917,904387,99900,490640,268209,994867,135705,390652,412028,404195,490553,184029,624391,836288,619242,570500,367786,908994,934572,226481,281181,469810,376226,354931,55711,43299,487568,853741,556475,842100,133451,371270,820314,735709,859169,992745,981261,506744,573542,544798,335063,71332,345306,551165,522500,148531,323820,525891,571989,109699,540927,391815,383139,528328,941384,577084,148432,537377,589708,613443,589827,688798,501198,304829,719726,181892,891384,237429,447803,49953,555945,69576,765896,194628,866362,533750,798399,369884,258270,964160,796047,420697,486470,781692,825420,689886,392317,278581,151823,184594,295461,723312,604322,248126,43623,91154,600821,55136,709242,990838,263827,564093,735641,174057,932157,750399,807534,338221,830644,171022,156968,351523,814982,403402,975555,955973,400091,523040,382185,577810,257717,544345,243199,509472,450948,839442,387377,553239,145202,822954,478559,487143,514465,587609,575770,547307,386320,410846,81519,599793,874316,730403,913822,800625,96868,913119,843783,699,767204,432828,496436,348230,767865,455134,266270,324004,863226,758456,66451,431182,641607,514915,522399,164590,335706,829719,724524,981933,812770,192582,880771,71867,704720,691726,761694,868674,964177,287148,124076,155241,535262,856554,108951,453851,597675,592745,32413,774791,750298,66826,876820,567338,699491,336474,60148,776819,430070,546456,564666,776689,886534,68830,749993,157504,933346,39836,417088,481438,30183,515310,764031,876787,321614,765291,466180,941767,877507,658149,60699,413225,849839,376668,689777,491763,712459,5768,608757,161358,554199,132368,464770,89566,309794,430979,979239,62376,354441,582188,947427,569030,430121,826059,562654,461350,901008,191328,484599,615686,859104,366550,140695,229053,282037,289028,296120,883539,980557,365526,143257,658629,730361,683520,101817,442395,50455,199765,137552,653983,47041,102020,308470,523274,447051,345263,967056,525031,506873,170405,995568,977216,83193,279492,376521,946443,847471,845107,321145,866307,523882,135730,824806,927733,605908,580895,177233,443804,914175,905847,661407,483093,518439,789231,66585,447439,14824,861841,89137,913636,194682,166773,212398,259259,160638,435374,941416,140851,311224,54813,155003,595354,742575,668942,77310,96783,217826,211522,116834,391751,922905,730508,225636,265187,995541,329461,244649,951125,322487,140958,608238,511144,410963,335698,228967,487748,382037,261094,363854,557078,539851,519352,364988,444038,284404,730251,828294,608545,188095,466810,46659,673970,142329,93794,167913,30119,116528,592075,810599,14144,445947,51745,236481,878706,838520,310352,112640,612690,663852,546444,818881,868195,573845,390221,254379]
bricks = 33671263
ladders = 108

You can use recursion to try bricks and ladders at each step. — stark, Nov 18 '20 at 17:55
do you have a webpage for this problem or do you have a result of the last task? — Nina Scholz, Nov 18 '20 at 20:58

Dave · Answer 1 · 2020-11-19T01:17:01.283

Let's say an "ascent" is a height that is either the first in our list or greater than the previous height, and that the magnitude of an ascent is the delta.

Use a min_heap to represent ascents via ladder. Keep track of bricks_left and ladders_left, initialized to your inputs.

We will maintain the following as we parse the heights array. The ladders will be used for the steepest ascents we've seen up to the number possible, and the bricks will be used for all other ascents.

I.e., as long as ladders_left > 0, we add new ascents to the min_heap and subtract one from ladders_left.

If ladder_left = 0, we compare the ascent to the top of our min heap. If the smaller of the two is <= bricks_left we can continue, otherwise we're done.

Assuming we can continue:

if the smaller of the two is the new ascent, subtract it from bricks_left and continue.
If the smaller of the two is the top of the min_heap, remove it, add the new ascent to the min_heap, and subtract the former top of the min_heap from bricks_left.

-- edit -- The above algorithm is O(log(ladders) * (ascents - ladders)). If we start with not very many ladders and don't like the complexity of a min_heap for some reason, we can sove this in O(ladders * (ascents - ladders)) by replacing the min_heap with an array, and finding the min by scanning the array when we need to.

@myTest532myTest532 Just implement a heap. One of many links on how to do it: https://blog.bitsrc.io/implementing-heaps-in-javascript-c3fbf1cb2e65 — Dave, Nov 18 '20 at 23:12
@myTest532myTest532 Or maybe a library.https://openbase.io/packages/top-javascript-heap-libraries — Dave, Nov 18 '20 at 23:15

Nina Scholz · Answer 2 · 2020-11-19T14:09:44.143

Approach by using all ladders first and replace the ladders with the smallest delta first to save bricks.

/**
 * @param {number[]} heights
 * @param {number} bricks
 * @param {number} ladders
 * @return {number}
 */
var furthestBuilding = function (heights, bricks = 0, ladders = 0) {

    function insert(array, value) {
        // part for searching the index, taken from
        // https://stackoverflow.com/a/21822316/1447675
        var low = 0,
            high = array.length;

        while (low < high) {
            const mid = (low + high) >>> 1;
            if (array[mid] < value) low = mid + 1;
            else high = mid;
        }
        array.splice(low, 0, value);
    }

    const ladderSizes = [];

    for (let i = 0, l = heights.length - 1; i < l; i++) {
        const delta = heights[i + 1] - heights[i];

        if (delta <= 0) continue;

        if (ladders) {
            insert(ladderSizes, delta);
            ladders--;
            continue;
        }

        const small = ladderSizes[0];
        if (small <= delta && bricks >= small) {
            bricks -= ladderSizes.shift();
            insert(ladderSizes, delta);
            continue;
        }

        if (bricks >= delta) {
            bricks -= delta;
            continue;
        }
        return i;
    }
    return heights.length - 1;
};        

console.log(furthestBuilding([4, 2, 7, 6, 9, 14, 12], 5, 1));
console.log(furthestBuilding([1, 5, 1, 2, 3, 4, 10000], 4, 1));

Thanks. It crashes for a big input (time limit exceed). I just added a new input test — myTest532 myTest532, Nov 18 '20 at 19:28

Furthest Building You Can Reach Algorithm - JavaScript

2 Answers2