Overview
One less understood idea among javascript engineers (unless you happen to be studying up for interviews) is the use of greedy algorithms. A greedy algorithm makes whatever choice seems best at the moment, and solves the subproblems that arise later. To use a visual metaphor, we put the result of each subproblem in a “bag” and then repeat with successively smaller subproblems. When the subproblem is empty (nothing left to do), we return the contents of the bag.
As it turns out, this strategy can lead to some very elegant solutions to practical problems. In the rest of this article, we’ll explore four seemingly different problems that have almost identical solutions (hint: they all use a greedy algorithm). In closing, we’ll take a closer look at the structure common to all four problems. Let’s dive in!
Example: coin change problem
You are given coins of different denominations and a total amount of
money. Write a function that returns the smallest set of coins that
sums to that amount.
Take a moment to consider how you’d do this before continuing… (answer is right below)
function makeChange(amount, coins, bag = []) {
if (amount === 0) return bag
let largestCoin = getLargestCoin(amount, coins)
return makeChange(amount - largestCoin, coins, bag.concat([largestCoin]))
}
function getLargestCoin(amount, coins) {
let sortedCoins = coins.sort((a, b) =\> a - b)
for (let i = sortedCoins.length - 1; i \>= 0; i--) {
if (sortedCoins[i] \<= amount) return sortedCoins[i]
}
throw new Error('no coin that divides amount')
}
console.log(
makeChange(42, [1, 5, 10, 25])
)
// [25, 10, 5, 1, 1]
We keep a “bag” of coins and recursively add coins to the bag that matches our selection criteria (pick largest coin denomination that is < amount). If the largest coin has value C, we add C to the bag and call makeChange with amount - C. This continues until the amount is 0, and the bag of coins is returned.
A quick note on the expression { ...bag, ...{ [fn(array[0])]: matches } } since there’s a lot going on there. First of all, what does { ...a, ...b } mean? This is called object spreading. Think of it as smooshing together objects a and b to create a new object. So { ...bag, ...somethingElse } will combine the object bag with object somethingElse. In this case, somethingElse is the object { [fn(array[0])]: matches } which is the new group we’re inserting into the bag.
I’ll also explain the difference between { [key]: value } and { key: value }. Those square braces signify computed properties. You can stick any expression between the square braces, and the value of that expression will become the value of the key. So for example { [1 + 1]: 2} would be the same as { 2: 2 }.
Example: groupBy
Implement the "groupBy" function which takes an array A and a function F,
and returns an object composed of keys generated from the results of
running each element of A through F. The corresponding value of each key
is an array of elements responsible for generating the key.
Take a moment to consider how you’d do this before continuing… (answer is right below)
/*
input: [6.1, 4.2, 6.3]
function: Math.floor
output: { '4': [4.2], '6': [6.1, 6.3] }
*/
function groupBy(array, fn, bag = {}) {
if (array.length === 0) return bag
let matches = array.filter(x =\> fn(x) === fn(array[0]))
let rest = array.filter(x =\> fn(x) !== fn(array[0]))
return (
groupBy(
rest,
fn,
{ ...bag, ...{ [fn(array[0])]: matches } }
)
)
}
console.log(
groupBy([6.1, 4.2, 6.3], Math.floor)
)
// { '4': [4.2], '6': [6.1, 6.3] }
Keep a “bag” of groups and recursively add groups to the bag that match our selection criteria fn(x) === fn(array[0]). Then call groupBy on the remaining elements, with the updated bag. This continues until the original array is empty, and the bag is returned.
Example: activity selection problem
Another classic problem is the activity selection problem.
Imagine you are trying to schedule a room for multiple competing events,
each having its own time requirements (start and end time). How do you
schedule the room such that you can host the maximum number of events
with no scheduling conflicts?
Take a moment to consider how you’d do this before continuing… (answer is right below)
class Appointment {
constructor(name, from, to) {
this.name = name
this.from = from
this.to = to
}
}
// push new appointments onto bag one-by-one until no more appointments are left
function getMaxAppointments(appointments, bag = []) {
if (appointments.length === 0) return bag
let selectedAppointment = appointments.sort((a, b) =\> a.to - b.to)[0] // sort from earliest end to latest end
let futureCandidates = appointments.filter(a =\> a.from \> selectedAppointment.to)
return getMaxAppointments(
futureCandidates,
bag.concat([selectedAppointment])
)
}
let a1 = new Appointment('brush teeth', 0, 2)
let a2 = new Appointment('wash face', 1, 3)
let a3 = new Appointment('make coffee', 3, 5)
let a4 = new Appointment('blowdry hair', 3, 4)
let a5 = new Appointment('take shower', 4.5, 6)
let a6 = new Appointment('eat cereal', 7, 10)
console.log(
getMaxAppointments([a1, a2, a3, a4, a5, a6]).map(a =\> a.name)
)
// ['brush teeth', 'blowdry hair', 'take shower', 'eat cereal']
Example: collect anagrams
For our final example, we’ll consider the problem of grouping anagrams.
Given an array of strings, group anagrams together.
For example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
Take a moment to consider how you’d do this before continuing… (answer is right below)
function collectAnagrams(words, bag = []) {
if (words.length === 0) return bag
let matches = words.filter(w =\> isAnagram(w, words[0]))
let rest = words.filter(w =\> !isAnagram(w, words[0]))
return collectAnagrams(
rest,
bag.concat([matches])
)
}
function stringSorter(a, b) { return a.localeCompare(b) }
function isAnagram(a, b) {
let aSorted = a.toLowerCase().split('').sort(stringSorter).join('')
let bSorted = b.toLowerCase().split('').sort(stringSorter).join('')
return aSorted === bSorted
}
let x = ['bag', 'gab', 'foo', 'abg', 'oof', 'bum']
console.log(collectAnagrams(x))
// [['bag', 'gab', 'abg'], ['foo', 'oof'], ['bum']]
The Common Structure
So what do all of these problems have in common? For every iteration through the loop, we select a subset of items from the input and add it to the bag. The remaining items feed through to the next iteration of the loop as the next input. When the input is empty, we return the bag.
The following diagram might help clarify things, using our groupBy example:
If you’re more comfortable with pseudocode, here is the pattern we used in all of the previous examples:
function bagItUp(things, bag = []) {
if (things is empty) return bag
let thingsToPutInBag = ...
let restOfThings = ...
return bagItUp(
restOfThings,
bag + thingsToPutInBag
)
}
Connect
What do you think? Have you solved similar problems at work or personal projects using greedy algorithms? Let me know in the comments below, or on twitter!
Top comments (0)