Greedy Algorithms

Select the maximum number of non-overlapping activities. Greedy: sort by finish time and always pick the earliest finishing activity.

function activitySelection(start, finish) {
    const n = start.length;
    const activities = start.map((s, i) => [s, finish[i]])
        .sort((a, b) => a[1] - b[1]);
    const result = [activities[0]];
    let lastEnd = activities[0][1];
    for (let i = 1; i < n; i++) {
        if (activities[i][0] >= lastEnd) {
            result.push(activities[i]);
            lastEnd = activities[i][1];
        }
    }
    return result;
}

Time: O(n log n) for sorting  |  Space: O(n)

Unlike 0/1 knapsack, you can take fractions of items. Greedy: sort by value/weight ratio and take items greedily.

function fractionalKnapsack(items, capacity) {
    items.sort((a, b) => b.value/b.weight - a.value/a.weight);
    let totalValue = 0;
    for (const item of items) {
        if (capacity >= item.weight) {
            totalValue += item.value;
            capacity -= item.weight;
        } else {
            totalValue += (capacity / item.weight) * item.value;
            break;
        }
    }
    return totalValue;
}

Time: O(n log n)  |  Greedy works here because we can take fractions.

Given jobs with deadlines and profits, schedule jobs to maximize profit. Each job takes one unit of time. Greedy: sort by profit descending and assign to the latest available slot before deadline.

function jobSequencing(jobs) {
    jobs.sort((a, b) => b.profit - a.profit);
    const maxDeadline = Math.max(...jobs.map(j => j.deadline));
    const slots = new Array(maxDeadline).fill(null);
    let totalProfit = 0;
    for (const job of jobs) {
        for (let t = job.deadline - 1; t >= 0; t--) {
            if (slots[t] === null) {
                slots[t] = job.id;
                totalProfit += job.profit;
                break;
            }
        }
    }
    return { slots, totalProfit };
}

Time: O(n²) or O(n log n) with union-find

Huffman Coding is a greedy algorithm for lossless data compression. It assigns shorter codes to more frequent characters using a priority queue (min-heap).

// Algorithm:
// 1. Count frequency of each character
// 2. Create a leaf node for each character
// 3. While more than one node in the queue:
//    a. Extract two nodes with lowest frequency
//    b. Create a new internal node with their sum
//    c. Insert the new node back
// 4. The remaining node is the root

// Example: "aabbbcccc"
// c:4, b:3, a:2
// Tree assigns: c=0, b=10, a=11
// Compressed: fewer bits than fixed-length encoding

Time: O(n log n) with heap  |  Produces optimal prefix codes.

For standard coin denominations (e.g., 1, 5, 10, 25), greedy works: always pick the largest coin that fits.

function minCoinsGreedy(coins, amount) {
    coins.sort((a, b) => b - a); // sort descending
    let count = 0;
    const used = [];
    for (const coin of coins) {
        while (amount >= coin) {
            amount -= coin;
            used.push(coin);
            count++;
        }
    }
    return { count, used };
}
// minCoinsGreedy([1, 5, 10, 25], 63)
// => { count: 6, used: [25, 25, 10, 1, 1, 1] }

Note: Greedy fails for arbitrary denominations (e.g., [1, 3, 4] for amount 6). Use DP for those cases.

Given meeting start and end times, find the maximum number of meetings in one room. Same as activity selection: sort by end time and greedily pick non-overlapping meetings.

function maxMeetings(start, end) {
    const meetings = start.map((s, i) => ({s, e: end[i], idx: i + 1}));
    meetings.sort((a, b) => a.e - b.e);
    const result = [meetings[0].idx];
    let lastEnd = meetings[0].e;
    for (let i = 1; i < meetings.length; i++) {
        if (meetings[i].s > lastEnd) {
            result.push(meetings[i].idx);
            lastEnd = meetings[i].e;
        }
    }
    return result;
}

Time: O(n log n)  |  Space: O(n)

Find the minimum number of platforms needed at a railway station so no train waits. Sort arrivals and departures separately and use the two-pointer technique.

function minPlatforms(arrivals, departures) {
    arrivals.sort((a, b) => a - b);
    departures.sort((a, b) => a - b);
    let platforms = 0, maxPlatforms = 0;
    let i = 0, j = 0;
    while (i < arrivals.length) {
        if (arrivals[i] <= departures[j]) {
            platforms++;
            i++;
        } else {
            platforms--;
            j++;
        }
        maxPlatforms = Math.max(maxPlatforms, platforms);
    }
    return maxPlatforms;
}
// minPlatforms([900,940,950,1100], [910,1200,1120,1130]) => 3

Time: O(n log n)  |  Space: O(1)

Given an array where each element is the max jump length, determine if you can reach the last index. Greedy: track the farthest reachable position.

function canJump(nums) {
    let farthest = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i > farthest) return false;
        farthest = Math.max(farthest, i + nums[i]);
    }
    return true;
}
// canJump([2,3,1,1,4]) => true
// canJump([3,2,1,0,4]) => false

Time: O(n)  |  Space: O(1)

There are n gas stations in a circle. Find the starting station index to complete the circuit, or return -1. Greedy: if total gas ≥ total cost, a solution exists. Track the current deficit to find the start.

function canCompleteCircuit(gas, cost) {
    let totalSurplus = 0, currentSurplus = 0, start = 0;
    for (let i = 0; i < gas.length; i++) {
        totalSurplus += gas[i] - cost[i];
        currentSurplus += gas[i] - cost[i];
        if (currentSurplus < 0) {
            start = i + 1;
            currentSurplus = 0;
        }
    }
    return totalSurplus >= 0 ? start : -1;
}
// canCompleteCircuit([1,2,3,4,5], [3,4,5,1,2]) => 3

Time: O(n)  |  Space: O(1)

Greedily extend your reach: track current reach and next farthest reach. Each time you exhaust current reach, increment jump count and advance to next farthest.

function jump(nums) {
    let jumps = 0, currEnd = 0, farthest = 0;
    for (let i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i === currEnd) { // reached current boundary
            jumps++;
            currEnd = farthest;
        }
    }
    return jumps;
}
// Input: [2,3,1,1,4]   => Output: 2  (0->1->4 or 0->4 or ... min=2 jumps)
// Input: [2,3,0,1,4]   => Output: 2
// Input: [1,2,3]       => Output: 2  (0->1->2)

Time: O(n)  |  Space: O(1)

Sort meetings by start time. Use a min-heap of end times. For each meeting, if it starts after the earliest ending meeting's end, reuse that room. Otherwise, add a room.

function minMeetingRooms(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    const endTimes = []; // simulated min-heap
    for (const [start, end] of intervals) {
        endTimes.sort((a, b) => a - b);
        if (endTimes.length && endTimes[0] <= start) {
            endTimes.shift(); // reuse room
        }
        endTimes.push(end); // allocate room
    }
    return endTimes.length;
}
// Input: [[0,30],[5,10],[15,20]]  => Output: 2
// Input: [[7,10],[2,4]]           => Output: 1 (no overlap)
// Input: [[1,5],[2,6],[3,7]]      => Output: 3 (all overlap)

Time: O(n log n)  |  Space: O(n)

Sort by end position. A single arrow can burst all balloons whose start ≤ current arrow position. Shoot at the end of the first balloon and skip all that overlap.

function findMinArrowShots(points) {
    points.sort((a, b) => a[1] - b[1]); // sort by end position
    let arrows = 1, arrowPos = points[0][1];
    for (let i = 1; i < points.length; i++) {
        if (points[i][0] > arrowPos) { // balloon starts after last arrow
            arrows++;
            arrowPos = points[i][1]; // shoot at end of this balloon
        }
    }
    return arrows;
}
// Input: [[10,16],[2,8],[1,6],[7,12]]   => Output: 2
// Input: [[1,2],[3,4],[5,6],[7,8]]      => Output: 4
// Input: [[1,2],[2,3],[3,4],[4,5]]      => Output: 2

Time: O(n log n)  |  Space: O(1)

Custom sort: compare two numbers a and b by checking which concatenation (ab vs ba) is larger. Use string comparison.

function largestNumber(nums) {
    const sorted = nums.map(String).sort((a, b) => {
        return (b + a).localeCompare(a + b); // or compare (b+a) vs (a+b)
    });
    // Edge case: all zeros
    if (sorted[0] === '0') return '0';
    return sorted.join('');
}
// Input: [10,2]        => Output: "210"   (210 > 102)
// Input: [3,30,34,5,9] => Output: "9534330"
// Input: [0,0]         => Output: "0"

Time: O(n log n × m) where m is average digit length  |  Space: O(n)

Sort events by end day. Use a greedy approach: for each available day, attend the event ending earliest (use a min-heap of end times).

function maxEvents(events) {
    events.sort((a, b) => a[0] - b[0]); // sort by start day
    const endHeap = []; // min-heap of end days
    let day = 0, count = 0, i = 0;
    const n = events.length;
    while (i < n || endHeap.length) {
        if (!endHeap.length) day = events[i][0]; // jump to next event start
        // Add all events that start on or before today
        while (i < n && events[i][0] <= day) {
            endHeap.push(events[i][1]);
            endHeap.sort((a, b) => a - b);
            i++;
        }
        // Attend earliest-ending available event
        while (endHeap.length && endHeap[0] < day) endHeap.shift(); // expired
        if (endHeap.length) { endHeap.shift(); count++; }
        day++;
    }
    return count;
}
// Input: [[1,2],[2,3],[3,4]]    => Output: 3
// Input: [[1,4],[4,4],[2,2],[3,4],[1,1]] => Output: 4

Time: O(n log n)  |  Space: O(n)

Sort both children's greed factors and cookie sizes. Use a two-pointer greedy: give the smallest sufficient cookie to the least greedy child.

function findContentChildren(g, s) {
    g.sort((a, b) => a - b); // greed factors
    s.sort((a, b) => a - b); // cookie sizes
    let child = 0, cookie = 0;
    while (child < g.length && cookie < s.length) {
        if (s[cookie] >= g[child]) child++; // cookie satisfies child
        cookie++; // try next cookie either way
    }
    return child; // number of satisfied children
}
// Input: g=[1,2,3], s=[1,1]    => Output: 1
// Input: g=[1,2], s=[1,2,3]    => Output: 2
// Input: g=[10,9,8], s=[1,2]   => Output: 0

Time: O(n log n + m log m)  |  Space: O(1)

Sort workers by ratio (wage/quality). For each worker considered as the highest-paid (sets the ratio), sum the k smallest qualities. Use a max-heap to maintain the k smallest.

function mincostToHireWorkers(quality, wage, k) {
    const workers = quality.map((q, i) => [wage[i] / q, q]); // [ratio, quality]
    workers.sort((a, b) => a[0] - b[0]); // sort by ratio
    let totalQ = 0, minCost = Infinity;
    const maxHeap = []; // track k smallest qualities
    for (const [ratio, q] of workers) {
        maxHeap.push(q);
        maxHeap.sort((a, b) => b - a); // max at front
        totalQ += q;
        if (maxHeap.length > k) totalQ -= maxHeap.shift(); // remove largest quality
        if (maxHeap.length === k) minCost = Math.min(minCost, ratio * totalQ);
    }
    return minCost;
}
// Input: quality=[10,20,5], wage=[70,50,30], k=2  => Output: 105.00

Time: O(n log n)  |  Space: O(k)

Convert taps to intervals, then apply the jump game greedy: find the farthest point reachable from any position in the current window.

function minTaps(n, ranges) {
    const maxReach = new Array(n + 1).fill(0);
    for (let i = 0; i <= n; i++) {
        const left  = Math.max(0, i - ranges[i]);
        const right = Math.min(n, i + ranges[i]);
        maxReach[left] = Math.max(maxReach[left], right);
    }
    let taps = 0, currEnd = 0, farthest = 0;
    for (let i = 0; i <= n; i++) {
        if (i > farthest) return -1; // garden can't be watered
        farthest = Math.max(farthest, maxReach[i]);
        if (i === currEnd && i < n) { taps++; currEnd = farthest; }
    }
    return taps;
}
// Input: n=5, ranges=[3,4,1,1,0,0]  => Output: 1  (tap 0 or 1 covers all)
// Input: n=7, ranges=[1,2,1,0,2,1,0,1] => Output: 3

Time: O(n)  |  Space: O(n)

To minimize the makespan (max completion time), assign tasks in non-increasing order of processing time to processors using the Longest Processing Time (LPT) rule.

function assignTasks(tasks, workers) {
    tasks.sort((a, b) => b - a); // sort descending
    const loads = new Array(workers).fill(0);
    for (const task of tasks) {
        loads.sort((a, b) => a - b); // assign to least loaded worker
        loads[0] += task;
    }
    return Math.max(...loads); // makespan
}
// Input: tasks=[3,2,3,2], workers=2   => Output: 5  (3+2=5 each)
// Input: tasks=[1,2,4,8], workers=2   => Output: 9  (8+1=9 vs 4+2=6)

Time: O(n log n)  |  Space: O(workers)

Track the minimum buy price (adjusted for fee). For each day, if selling now is profitable (price > minBuy), take the profit. Update minBuy greedily.

function maxProfitWithFee(prices, fee) {
    let cash = 0; // profit when not holding stock
    let hold = -prices[0]; // profit when holding stock
    for (let i = 1; i < prices.length; i++) {
        cash = Math.max(cash, hold + prices[i] - fee); // sell today
        hold = Math.max(hold, cash - prices[i]);        // buy today
    }
    return cash;
}
// Input: prices=[1,3,2,8,4,9], fee=2   => Output: 8
//   (buy@1 sell@8 fee=2 => profit=5; buy@4 sell@9 fee=2 => profit=3; total=8)
// Input: prices=[1,3,7,5,10,3], fee=3  => Output: 6

Time: O(n)  |  Space: O(1)

Give everyone 1 candy. Pass left-to-right: if rating[i] > rating[i-1], give one more than leftNeighbor. Pass right-to-left: if rating[i] > rating[i+1], ensure right side also satisfied.

function candy(ratings) {
    const n = ratings.length;
    const candies = new Array(n).fill(1);
    // Left pass
    for (let i = 1; i < n; i++) {
        if (ratings[i] > ratings[i-1]) candies[i] = candies[i-1] + 1;
    }
    // Right pass
    for (let i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i+1]) candies[i] = Math.max(candies[i], candies[i+1] + 1);
    }
    return candies.reduce((a, b) => a + b, 0);
}
// Input: [1,0,2]       => Output: 5  ([2,1,2])
// Input: [1,2,2]       => Output: 4  ([1,2,1])
// Input: [1,3,2,2,1]   => Output: 7  ([1,3,1,2,1])

Time: O(n)  |  Space: O(n)

Compute value-to-weight ratio for each item. Sort by ratio descending. Take as much as possible from the highest-ratio item (fractions allowed).

function fractionalKnapsack(capacity, weights, values) {
    const items = values.map((v, i) => [v / weights[i], weights[i], v]);
    items.sort((a, b) => b[0] - a[0]); // sort by ratio descending
    let totalValue = 0;
    for (const [ratio, w, v] of items) {
        if (capacity >= w) {
            totalValue += v;
            capacity -= w;
        } else {
            totalValue += ratio * capacity; // take fraction
            break;
        }
    }
    return totalValue;
}
// Input: capacity=50, weights=[10,20,30], values=[60,100,120]
// Output: 240.0  (all of item 1 and 2, then 2/3 of item 3)

Time: O(n log n)  |  Space: O(n)