Tasks

Greedy Techniques

Index	Task Name	Task Number	Difficulty	Link
1	Jump Game	55	Medium	Link
2	Best Time to Buy and Sell Stock	121	Easy	Link
3	Minimum Number of Arrows to Burst Balloons	452	Medium	Link
4	Task Scheduler	621	Medium	Link
5	Candy	135	Hard	Link
6	Jump Game II	45	Hard	Link
7	Non-overlapping Intervals	435	Medium	Link
8	Lemonade Change	860	Easy	Link
9	Gas Station	134	Medium	Link
10	Partition Labels	763	Medium	Link
11	Boats to Save People	881	Medium	Link
12	Minimum Number of Refueling Stops	871	Hard	Link

// 55. Jump Game

// Time: O(n) | Space: O(1)
var canJump = function(nums) {
    let max = 0;
    const targetIndex = nums.length - 1;
    for (let i = 0; i < nums.length; i++) {
        
        // Get the max point that we can reach from the current point.
        max = Math.max(max, i + nums[i]);

        // We can reach target from the current point.
        if (max >= targetIndex) {
            return true;
        }
        // The target is unreachable.
        if (max <= i && nums[i] === 0) {
            return false;
        }
    }
    return false;
};

/*
 * Gready
 * ----------------------------------
 * 1. For every point check the max point reachable.
 * 2. Return true if max is >= the target index.
 * 3. Return false if  max is <= nums[i] && nums[i] === 0.
 * ----------------------------------
 * Time: O(n) | Space: O(1)
 */

// 45. Jump Game II

// Time: O(n) | Space: O(1)
var jump = function(nums) {
    // No need to jump if we already in the target position.
    if (nums.length < 2) {
        return 0;
    }
    const target = nums.length - 1;

    let counter = 0;
    let currentJump = 0;
    let maxPossibleJump = 0;

    // Iterate over all possible indexes.
    for (let i = 0; i < target; i++) {

        // Check max jump for the current index.
        maxPossibleJump = Math.max(maxPossibleJump, i + nums[i]);

        // Current jump is finished. Need to do the next one.
        if (i === currentJump) {
            counter++;

            // Use the best possible for the next one.
            currentJump = maxPossibleJump;

            // Break if we reach the target.
            if (currentJump >= target) {
                break;
            }
        }
    }
    return counter;
};

/*
Greedy
-------------------------------
1. Iterate over.
2. Check the max jump as max(maxJump, i + nums[i]).
3. If we reach the position where we required to jump.
3.1. Update the current jump position.
3.2. Increase jumps counter.
3.3. Break if max currentJump >= target.
4. Return counter.
-------------------------------
Time: O(n) | Space: O(1)
 */

// 134. Gas Station

// Time: O(n) | Space: O(1)
var canCompleteCircuit = function(gas, cost) {
    const totalGas = gas.reduce((a, b) => a + b, 0);
    const totalCost = cost.reduce((a, b) => a + b, 0);

    // If total gas is less then total cost -> loop is imposible. Return -1.
    if (totalCost > totalGas) {
        return -1;
    }
    // Else -> loop is possible.
    let startIndex = 0;
    let currentGas = 0;
    for (let i = 0; i < gas.length; i++) {
        currentGas += gas[i] - cost[i];

        // Find the index from where the loop is possible.
        if (currentGas < 0) {
            currentGas = 0;
            startIndex = i + 1;
        }
    }
    return startIndex;
};

// 881. Boats to Save People

// Time: O(n log(n)) | Space: O(n) 
var numRescueBoats = function(people, limit) {
    let left = 0;
    let right = people.length - 1;
    let boats = 0;
    
    people.sort((a, b) => a - b);
    
    while (left <= right) {
        if (people[left] + people[right] <= limit) {
            left++;
        }
        right--;
        boats++;
    }
    return boats;
};

/*
Two Pointers
-------------------------------
1. Sort people by weight in ASC order.
2. Iterate with left and right pointers.
3. If sum of weights are <= limit -> move both pointers.
4. Else -> move only right.
5. Return result.
-------------------------------
Time: O(n log(n)) | Space: O(n) 
*/

// 871. Minimum Number of Refueling Stops

// Time: O(n log n) | Space: O(n)
var minRefuelStops = function(target, startFuel, stations) {
    // No need to re-fuel.
    if (startFuel >= target) {
        return 0;
    }
    // No way to reach target if there is no stations and start fuel is not enough.
    if (stations.length === 0) {
        return -1;
    }
    let resultStops = 0;
    let currentFuel = startFuel;
    let fuelMaxHeap = new Heap(Heap.maxComparator); 

    // To iterate through stations.
    let i = 0;

    // Iterate whie target is not reached.
    while (currentFuel < target) {
        // We can add station fuel to the heap if it is possible to reach the station. 
        if (stations[i] && stations[i][0] <= currentFuel) {
            fuelMaxHeap.add(stations[i][1]);
            i++;
        }
        // Use fuel from the heap otherwise.
        else {
            // We used all available fuel but do not reach the target.
            if (fuelMaxHeap.isEmpty()) {
                return -1;
            }
            currentFuel += fuelMaxHeap.pop();
            resultStops++;
        }
    }
    return resultStops;
};

/*
Greedy. Max Heap.
------------------------------
1. Handle corner cases (startFuel >= target; stations.length < 1).
2. Initialize max heap to keep best station fuel options on top.
3. Loop while currentFuel is less then target.
4. If station availabe and it's position is reachable -> add station fuell to the heap.
5. Else -> use fuel from the heap (and increment stops).
6. Return result number of stops. 
------------------------------
Time: O(n log n) | Space: O(n)
 */