DSA for Interviews, From Zero

Part 12 · Lesson 47 · read

Greedy Algorithms

When the best choice right now is also the best choice overall, and how to tell.

On this page

  1. The idea: take the best option now
  2. When greedy fails
  3. Why a greedy choice is safe
  4. Assign cookies and lemonade change
  5. Jump game
  6. Traced: can we reach the end?
  7. Jump game II: fewest jumps
  8. Gas station
  9. Activity selection
  10. Practice questions (7)
  11. Make it stick
  12. What's next

The idea: take the best option now

A greedy algorithm builds an answer one step at a time. At every step it takes the option that looks best right now. It never goes back to change its mind. It does not try every choice, and it never undoes a step. That is why greedy solutions are usually short and fast. Often they are just one sort and one loop.

There is a catch. The choice that is best right now is not always best overall. Greedy only gives the right answer when the problem has the greedy-choice property. This means a choice that looks best locally (in one small step) can always lead to the best answer overall. Interview greedy problems are the ones where this is true. Your job is to notice it and to explain why.

When greedy fails

Take coin change: use the fewest coins to make an amount. The greedy habit is "take the biggest coin that fits". With everyday coins (1, 5, 10, 25) that works. With coins [1, 3, 4] and amount 6, it does not:

JavaScript
// Greedy: always take the biggest coin that fits.function greedyCoins(coins, amount) {  const sorted = [...coins].sort((a, b) => b - a);   // biggest first  let count = 0;  for (const c of sorted) {    while (amount >= c) { amount -= c; count++; }  }  return amount === 0 ? count : -1;}// Brute force: try every first coin, again and again (slow, but always right).function bestCoins(coins, amount) {  if (amount === 0) return 0;  let best = Infinity;  for (const c of coins) {    if (c <= amount) best = Math.min(best, 1 + bestCoins(coins, amount - c));  }  return best;}console.log(greedyCoins([1, 5, 10, 25], 41)); // 4   (25 + 10 + 5 + 1: greedy is right for these coins)console.log(greedyCoins([1, 3, 4], 6));       // 3   (4 + 1 + 1)console.log(bestCoins([1, 3, 4], 6));         // 2   (3 + 3)
Dry run · coins [1, 3, 4], amount 6
StrategyCoins takenCount
greedy (biggest first)4, then 1, then 13
optimal (best possible)3, then 32

Taking the 4 felt best. But it left 2, and 2 can only be made from two 1s.

A choice that is best locally is not always best overall
When greedy fails like this, the right tool is usually dynamic programming. This is a method that solves each smaller version of the problem once, remembers its answer, and builds the big answer from those. Here you would remember the fewest coins for every smaller amount. You will meet it later in the series. This coin example is its classic first problem. For now, learn this habit: before you trust a greedy idea, try to break it with a small example.

Why a greedy choice is safe

How do you show (to yourself and to an interviewer) that a greedy rule is correct? The usual way is the exchange argument. In plain words, it goes like this:

  1. Imagine some best possible answer. You do not know it yet.
  2. Suppose it is different from the greedy choice at the first step.
  3. Swap the greedy choice into it, in place of what it chose. If the answer is not worse after the swap, then there is always a best answer that starts with the greedy choice.
  4. Repeat this for the smaller problem that is left.

For the coins, the swap fails. You cannot replace a 3 with a 4 without breaking the total. For activity selection (below), the swap works. That is why that greedy rule is correct.

Assign cookies and lemonade change

Assign cookies: each child has a greed number. This is the smallest cookie size that makes the child happy. Each cookie has a size. A child gets at most one cookie. Make as many children happy as you can. The greedy rule: sort both lists. Then give each cookie, smallest first, to the least greedy child who is still waiting, if the cookie is big enough. If a small cookie cannot satisfy the least greedy child, it cannot satisfy anyone. So you can safely throw it away.

JavaScript
function findContentChildren(g, s) {      // g = how greedy each child is, s = size of each cookie  g = [...g].sort((a, b) => a - b);  s = [...s].sort((a, b) => a - b);  let child = 0;  for (const cookie of s) {                // give cookies from smallest to largest    if (child < g.length && cookie >= g[child]) child++;   // this cookie makes the least greedy waiting child happy  }  return child;}console.log(findContentChildren([1, 2, 3], [1, 1]));    // 1console.log(findContentChildren([1, 2], [1, 2, 3]));    // 2console.log(findContentChildren([10, 9, 8, 7], [5, 6, 7, 8])); // 2

Lemonade change: each customer pays with 5, 10 or 20 for a lemonade that costs 5. You must give the exact change back. You start with no money. The only real decision is a 20 bill, which needs 15 back. A 5 bill is the flexible one, because it makes change for both 10 and 20. A 10 bill helps only with a 20. So spend a 10 first, and keep the 5s:

JavaScript
function lemonadeChange(bills) {  let fives = 0, tens = 0;  for (const bill of bills) {    if (bill === 5) fives++;    else if (bill === 10) { if (fives === 0) return false; fives--; tens++; }    else {                                   // 20: change is 15, so prefer 10 + 5 (a ten is not useful for most future change)      if (tens > 0 && fives > 0) { tens--; fives--; }      else if (fives >= 3) fives -= 3;      else return false;    }  }  return true;}console.log(lemonadeChange([5, 5, 5, 10, 20])); // trueconsole.log(lemonadeChange([5, 5, 10, 10, 20])); // false

Jump game

You stand on index 0 of an array of numbers that are not negative. nums[i] is the longest jump you can make from index i. Can you reach the last index? Do not try every path. Track one number instead: the farthest index you could possibly have reached. Every index up to it is reachable, because you can always take a shorter jump. So each index you walk over can push that limit further.

JavaScript
function canJump(nums) {  let farthest = 0;                          // the farthest index we can reach so far  for (let i = 0; i < nums.length; i++) {    if (i > farthest) return false;          // index i is out of reach, so we are stuck before it    farthest = Math.max(farthest, i + nums[i]);  }  return true;}console.log(canJump([2, 3, 1, 1, 4])); // trueconsole.log(canJump([3, 2, 1, 0, 4])); // falseconsole.log(canJump([0]));             // true

Traced: can we reach the end?

step 1 / 11
Set up
farthest = 0

farthest is the highest index we know we can reach. We stand on index 0, so we can reach at least index 0.

▶let farthest = 0;2for (let i = 0; i < nums.length; i++) {3  if (i > farthest) break;4  farthest = Math.max(farthest, i + nums[i]);5}6console.log(farthest >= nums.length - 1);
Variables
nums[3, 2, 1, 0, 4]
farthest0
Console
(nothing printed yet)
Every jump from index 0 to 3 reaches at most index 3, which holds a 0. Index 4 is never within reach. · interactive

Jump game II: fewest jumps

Now we know the end can be reached, and we want the smallest number of jumps. Think of it as walking in "waves". With 0 jumps, you only cover index 0. With 1 jump, you cover the indexes up to currentEnd. While you look at the indexes inside the current wave, remember the farthest place the next jump could land. When you reach the end of the wave, you must use a jump. The next wave ends at that farthest place. This is a breadth-first search (checking everything one step away, then everything two steps away, and so on) without a queue. (A queue is a waiting line that normal breadth-first search uses to remember what to visit next. Here two numbers are enough.)

JavaScript
function jump(nums) {                       // fewest jumps to reach the last index (the end can always be reached)  let jumps = 0;  let currentEnd = 0;                        // the farthest index we can reach with 'jumps' jumps  let farthest = 0;                          // the farthest index we can reach with 'jumps + 1' jumps  for (let i = 0; i < nums.length - 1; i++) {    farthest = Math.max(farthest, i + nums[i]);    if (i === currentEnd) {                  // we have used all of the current jump's range, so we must jump again      jumps++;      currentEnd = farthest;    }  }  return jumps;}console.log(jump([2, 3, 1, 1, 4])); // 2   (0 -> 1 -> 4)console.log(jump([2, 3, 0, 1, 4])); // 2console.log(jump([1, 1, 1, 1]));    // 3
Dry run · nums = [2, 3, 1, 1, 4]
ifarthesti === currentEnd?jumpscurrentEnd
start0-00
02yes: jump12
14no12
24yes: jump24
34no24

The loop stops before the last index, because we never need to jump from it. Answer: 2 jumps (for example 0 → 1 → 4).

Gas station

The stations are on a circle. Station i gives you gas[i] fuel. The trip to the next station costs cost[i]. You start with an empty tank. Find the station where you can start and drive one full lap, or return −1. Two facts make this greedy:

  • If the total gas is less than the total cost, no start works.
  • Say you start at s, and your tank first goes below zero on the way to station i + 1. Then no station between s and i can be a good start either. Each of them would reach the failing part with no more fuel than you had, and that was not enough. So move the start to i + 1.
JavaScript
function canCompleteCircuit(gas, cost) {  let total = 0;                             // gas - cost over the whole circle  let tank = 0;                              // fuel since the candidate start  let start = 0;  for (let i = 0; i < gas.length; i++) {    const gain = gas[i] - cost[i];    total += gain;    tank += gain;    if (tank < 0) {                          // we cannot reach station i + 1 from 'start', or from any station between      start = i + 1;      tank = 0;    }  }  return total >= 0 ? start : -1;}console.log(canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2])); // 3console.log(canCompleteCircuit([2, 3, 4], [3, 4, 3]));             // -1

Activity selection

You have a list of activities. Each one has a start time and an end time. You can attend only one at a time. What is the largest number you can attend? There are three tempting rules: pick the earliest start, pick the shortest, or pick the earliest end. Only the last one is always right. Here is the exchange argument. The activity that ends first leaves the most room for everything else. Say a best schedule starts with a different activity. Swap it for the one that ends first. That one ends no later, so nothing after it clashes.

JavaScript
// Each activity is [start, end]. Pick as many non-overlapping activities as possible.function maxActivities(activities) {  const sorted = [...activities].sort((a, b) => a[1] - b[1]);   // earliest END first  let count = 0;  let lastEnd = -Infinity;  for (const [start, end] of sorted) {    if (start >= lastEnd) {                  // it fits after the last activity we chose      count++;      lastEnd = end;    }  }  return count;}const acts = [[1, 4], [3, 5], [0, 6], [5, 7], [3, 9], [5, 9], [6, 10], [8, 11], [8, 12], [2, 14], [12, 16]];console.log(maxActivities(acts)); // 4   ([1,4], [5,7], [8,11], [12,16])
The pattern to remember
Many greedy problems are just sort, then one scan. The hard part is choosing what to sort by. For scheduling, sort by end time. For cookies, sort by size. Lesson 48 uses this same idea for intervals.

Practice questions

For each one, say the greedy rule in one sentence. Then try to break it with a tiny example.

Q1Assign cookiesEasy

Each child i has a greed number g[i], and each cookie j has a size s[j]. A child is happy if they get a cookie with s[j] >= g[i]. Each child gets at most one cookie, and each cookie goes to at most one child. Return the largest number of happy children.

Example 1
Input: g = [1, 2, 3], s = [1, 1]
Output: 1
Explanation: Only the child with greed 1 can be made happy, because both cookies are size 1.
Example 2
Input: g = [1, 2], s = [1, 2, 3]
Output: 2
Explanation: Cookie 1 satisfies greed 1 and cookie 2 satisfies greed 2. Cookie 3 is left over.
Stuck? Open one hint at a time
Hint 1
Should the biggest cookie go to the child with the biggest greed? Or is that a waste?
Hint 2
Sort both lists. The least greedy child is the easiest to make happy, so serve that child first.
Show all 2 solutions with explanations
Approach 1Brute force: best-fitting cookie for each child
The idea

Go through the children from least greedy to most greedy. For each child, look through all unused cookies. Find the smallest one that is big enough, and use it.

JavaScript
function findContentChildren(g, s) {  const children = [...g].sort((a, b) => a - b);  const used = new Array(s.length).fill(false);  let happy = 0;  for (const greed of children) {    let pick = -1;    for (let j = 0; j < s.length; j++) {      if (!used[j] && s[j] >= greed && (pick === -1 || s[j] < s[pick])) pick = j;    }    if (pick !== -1) { used[pick] = true; happy++; }  }  return happy;}console.log(findContentChildren([1, 2, 3], [1, 1])); // 1console.log(findContentChildren([1, 2], [1, 2, 3])); // 2
How it works

It is correct, but the search inside the loop makes it O(n · m) after the sort.

Approach 2Greedy: two sorted lists, one pass
The idea

Sort both lists. Walk through the cookies from smallest to largest. If the current cookie makes the next waiting child happy, count that child and move to the next child. Either way, you are done with that cookie.

JavaScript
function findContentChildren(g, s) {  g = [...g].sort((a, b) => a - b);  s = [...s].sort((a, b) => a - b);  let child = 0;  for (const cookie of s) {    if (child < g.length && cookie >= g[child]) child++;  }  return child;}console.log(findContentChildren([1, 2, 3], [1, 1])); // 1console.log(findContentChildren([1, 2], [1, 2, 3])); // 2console.log(findContentChildren([], [5]));           // 0
How it works

If a cookie is too small for the least greedy waiting child, it is too small for everyone else waiting. So skipping it loses nothing. This is the exchange argument. Sorting costs O(n log n + m log m) and the scan costs O(n + m).

Which approach should you use?

Use the greedy with two sorted lists. It is shorter and faster than the search. (LeetCode 455.)

Q2Lemonade changeEasy

Each lemonade costs 5. Customers pay in order with a 5, 10 or 20 bill, and you must give the exact change. You start with no money. Return whether you can serve every customer.

Example 1
Input: [5, 5, 5, 10, 20]
Output: true
Explanation: The 10 takes one 5 as change. The 20 takes the 10 and one 5 as change.
Example 2
Input: [5, 5, 10, 10, 20]
Output: false
Explanation: After the two 10s you hold no 5s and two 10s. The 20 needs 15 back, and 10 + 5 or 5 + 5 + 5 is not possible without 5s.
Stuck? Open one hint at a time
Hint 1
Only the 20 bill needs a choice. What can you use to make 15 in change?
Hint 2
Which is more useful to keep, a 5 or a 10?
Show all 2 solutions with explanations
Approach 1Backtracking over both ways to give change
The idea

For a 20, try giving 10 + 5. Then try giving 5 + 5 + 5 as a separate case. The answer is true if either choice lets you serve the rest of the customers.

JavaScript
function lemonadeChange(bills) {  function go(i, fives, tens) {    if (i === bills.length) return true;    const b = bills[i];    if (b === 5) return go(i + 1, fives + 1, tens);    if (b === 10) return fives > 0 && go(i + 1, fives - 1, tens + 1);    return (tens > 0 && fives > 0 && go(i + 1, fives - 1, tens - 1)) ||           (fives >= 3 && go(i + 1, fives - 3, tens));  }  return go(0, 0, 0);}console.log(lemonadeChange([5, 5, 5, 10, 20]));  // trueconsole.log(lemonadeChange([5, 5, 10, 10, 20])); // false
How it works

It is always correct. But it can split into two cases at every 20, so in the worst case the work doubles each time (exponential).

Approach 2Greedy: keep the fives
The idea

Count the 5s and 10s. For a 20, prefer 10 + 5. Use three 5s only if you cannot do that.

JavaScript
function lemonadeChange(bills) {  let fives = 0, tens = 0;  for (const bill of bills) {    if (bill === 5) fives++;    else if (bill === 10) {      if (fives === 0) return false;      fives--; tens++;    } else if (tens > 0 && fives > 0) { tens--; fives--; }    else if (fives >= 3) fives -= 3;    else return false;  }  return true;}console.log(lemonadeChange([5, 5, 5, 10, 20]));  // trueconsole.log(lemonadeChange([5, 5, 10, 10, 20])); // falseconsole.log(lemonadeChange([10]));               // false
How it works

A 5 can help with both a 10 and a 20. A 10 helps only with a 20. So using the 10 first never hurts. It takes one pass, with O(n) time and O(1) space.

Which approach should you use?

Use the greedy. You can explain why it works in one sentence. (LeetCode 860.)

Q3Jump gameMedium

You start at index 0. nums[i] is the most steps you can jump forward from index i. Return whether you can reach the last index.

Example 1
Input: [2, 3, 1, 1, 4]
Output: true
Explanation: Jump 1 step to index 1. Then jump 3 steps to the end.
Example 2
Input: [3, 2, 1, 0, 4]
Output: false
Explanation: Every path ends on index 3, and its jump length is 0.
Stuck? Open one hint at a time
Hint 1
If you can reach index i, you can reach every index before it too. Which single number tells you everything you can reach?
Show all 3 solutions with explanations
Approach 1Dynamic programming from the front
The idea

Mark each index as reachable or not. For every reachable index, mark all the indexes it can jump to.

JavaScript
function canJump(nums) {  const reach = new Array(nums.length).fill(false);  reach[0] = true;  for (let i = 0; i < nums.length; i++) {    if (!reach[i]) continue;    for (let j = i + 1; j <= i + nums[i] && j < nums.length; j++) reach[j] = true;  }  return reach[nums.length - 1];}console.log(canJump([2, 3, 1, 1, 4])); // trueconsole.log(canJump([3, 2, 1, 0, 4])); // false
How it works

It takes O(n²) time, because a big jump marks many indexes.

Approach 2Greedy: the farthest reachable index
The idea

Walk from left to right and keep farthest. If you stand at an index beyond it, you are stuck.

JavaScript
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;}console.log(canJump([2, 3, 1, 1, 4])); // trueconsole.log(canJump([3, 2, 1, 0, 4])); // falseconsole.log(canJump([0]));             // true
How it works

It takes O(n) time and O(1) space. Anything up to farthest can be reached, because a jump can always be shorter than its maximum.

Approach 3Greedy backwards: move the goal
The idea

Let goal be the last index. Go from the right. If index i can reach goal, then i becomes the new goal. At the end, ask: is index 0 the goal?

JavaScript
function canJump(nums) {  let goal = nums.length - 1;  for (let i = nums.length - 2; i >= 0; i--) {    if (i + nums[i] >= goal) goal = i;  }  return goal === 0;}console.log(canJump([2, 3, 1, 1, 4])); // trueconsole.log(canJump([3, 2, 1, 0, 4])); // false
How it works

It is also O(n). It is the same idea, seen from the other end.

Which approach should you use?

Use the forward greedy first. It is what the traced run above shows. (LeetCode 55.)

Q4Jump game IIMedium

The setup is the same as the last question, but the last index can always be reached. Return the fewest jumps needed to reach it.

Example 1
Input: [2, 3, 1, 1, 4]
Output: 2
Explanation: Jump from 0 to 1, then from 1 to 4.
Example 2
Input: [2, 3, 0, 1, 4]
Output: 2
Explanation: Same route: 0 to 1 to 4.
Stuck? Open one hint at a time
Hint 1
Think in waves. First, everything you can reach with 1 jump. Then everything you can reach with 2 jumps. And so on.
Hint 2
While you scan one wave, track how far the next wave could reach.
Show all 2 solutions with explanations
Approach 1Dynamic programming
The idea

dp[i] is the fewest jumps needed to reach index i. For each i, update every index it can jump to if the new way is better.

JavaScript
function jump(nums) {  const n = nums.length;  const dp = new Array(n).fill(Infinity);  dp[0] = 0;  for (let i = 0; i < n; i++) {    for (let j = i + 1; j <= i + nums[i] && j < n; j++) dp[j] = Math.min(dp[j], dp[i] + 1);  }  return dp[n - 1];}console.log(jump([2, 3, 1, 1, 4])); // 2console.log(jump([2, 3, 0, 1, 4])); // 2
How it works

It takes O(n²) time. That is fine for small inputs, but too slow when there are very many items (for example 10⁵).

Approach 2Greedy waves (a hidden breadth-first search)
The idea

Keep currentEnd (the last index you can reach with the jumps so far) and farthest (how far one more jump could go). When you reach currentEnd, add one jump and set currentEnd = farthest.

JavaScript
function jump(nums) {  let jumps = 0, currentEnd = 0, farthest = 0;  for (let i = 0; i < nums.length - 1; i++) {    farthest = Math.max(farthest, i + nums[i]);    if (i === currentEnd) {      jumps++;      currentEnd = farthest;    }  }  return jumps;}console.log(jump([2, 3, 1, 1, 4])); // 2console.log(jump([2, 3, 0, 1, 4])); // 2console.log(jump([0]));             // 0
How it works

It takes O(n) time and O(1) space. Each wave is one "level" of breadth-first search. So the number of waves needed to include the last index is the fewest jumps. This depends on the promise that the end can be reached.

Which approach should you use?

Use the waves greedy. Explain it as a breadth-first search without a queue. (LeetCode 45.)

Q5Gas stationMedium

There are n stations on a circle. Station i has gas[i] fuel, and driving to station i + 1 costs cost[i]. You start with an empty tank at one station. Return the index of the start that lets you drive once around the circle clockwise. Return −1 if no start works. If an answer exists, it is the only one.

Example 1
Input: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Output: 3
Explanation: Start at station 3 with 4 gas. Arrive at station 4 with 4 − 1 + 5 = 8, and so on around the circle.
Example 2
Input: gas = [2, 3, 4], cost = [3, 4, 3]
Output: -1
Explanation: The total gas (9) is less than the total cost (10).
Stuck? Open one hint at a time
Hint 1
If the total gas is less than the total cost, can any start work?
Hint 2
Say you start at s and run out of fuel before station i + 1. Could any station between s and i work as a start?
Show all 2 solutions with explanations
Approach 1Try every starting station
The idea

For each start, pretend to drive a full lap and check that the tank never goes below 0.

JavaScript
function canCompleteCircuit(gas, cost) {  const n = gas.length;  for (let start = 0; start < n; start++) {    let tank = 0, ok = true;    for (let k = 0; k < n; k++) {      const i = (start + k) % n;      tank += gas[i] - cost[i];      if (tank < 0) { ok = false; break; }    }    if (ok) return start;  }  return -1;}console.log(canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2])); // 3console.log(canCompleteCircuit([2, 3, 4], [3, 4, 3]));             // -1
How it works

O(n²).

Approach 2Greedy single pass
The idea

Track the tank since the possible start, and also the grand total. When the tank goes below zero at station i, the possible start moves to i + 1 and the tank resets to 0. At the end, if the grand total is not negative, the possible start is the answer.

JavaScript
function canCompleteCircuit(gas, cost) {  let total = 0, tank = 0, start = 0;  for (let i = 0; i < gas.length; i++) {    const gain = gas[i] - cost[i];    total += gain;    tank += gain;    if (tank < 0) { start = i + 1; tank = 0; }  }  return total >= 0 ? start : -1;}console.log(canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2])); // 3console.log(canCompleteCircuit([2, 3, 4], [3, 4, 3]));             // -1console.log(canCompleteCircuit([5], [4]));                         // 0
How it works

Every stretch that failed is skipped for good, because no start inside it could have done better. If the grand total is at least 0, the extra fuel after the last possible start covers the shortage of all the stretches before it. So the last possible start works. It takes O(n) time and O(1) space.

Which approach should you use?

Use the single pass. Be ready to explain why it is safe to skip all stations between the failed start and the place where it failed. (LeetCode 134.)

Q6Best time to buy and sell stock IIMedium

You get the price of a stock on each day. You can buy and sell as many times as you like, but you can hold at most one share at a time. Return the biggest profit you can make.

Example 1
Input: [7, 1, 5, 3, 6, 4]
Output: 7
Explanation: Buy at 1 and sell at 5 (+4). Then buy at 3 and sell at 6 (+3).
Example 2
Input: [1, 2, 3, 4, 5]
Output: 4
Explanation: Buy at 1 and sell at 5. This gives the same profit as taking each daily rise.
Stuck? Open one hint at a time
Hint 1
You can trade as many times as you like, but you can hold at most one share. Is a long climb worth more than all its daily steps added up?
Show all 2 solutions with explanations
Approach 1Dynamic programming with two situations
The idea

Track the best profit while you hold a share, and the best profit while you do not. Update both every day.

JavaScript
function maxProfit(prices) {  let hold = -Infinity;     // best profit while we hold a share  let cash = 0;             // best profit while we hold nothing  for (const p of prices) {    hold = Math.max(hold, cash - p);    cash = Math.max(cash, hold + p);  }  return cash;}console.log(maxProfit([7, 1, 5, 3, 6, 4])); // 7console.log(maxProfit([1, 2, 3, 4, 5]));    // 4console.log(maxProfit([7, 6, 4, 3, 1]));    // 0
How it works

It takes O(n) time and O(1) space. It is a good, safe answer. Harder stock questions, with a fee or a waiting period, use the same shape.

Approach 2Greedy: collect every rise
The idea

A climb from a to d through b and c is worth exactly the sum of its daily rises. So add every rise between one day and the next.

JavaScript
function maxProfit(prices) {  let profit = 0;  for (let i = 1; i < prices.length; i++) {    if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];  }  return profit;}console.log(maxProfit([7, 1, 5, 3, 6, 4])); // 7console.log(maxProfit([1, 2, 3, 4, 5]));    // 4console.log(maxProfit([7, 6, 4, 3, 1]));    // 0
How it works

You may sell and buy again on the same day (it changes nothing). So splitting a long climb into daily trades earns the same profit. You never trade on falling days. It takes O(n) time and O(1) space.

Which approach should you use?

The greedy is the shortest. The dynamic programming one still works if the interviewer adds new rules. (LeetCode 122.)

Q7Partition labelsMedium

Split the string into as many pieces as possible, so that each letter appears in at most one piece. Return the lengths of the pieces, in order.

Example 1
Input: s = "ababcbacadefegdehijhklij"
Output: [9, 7, 8]
Explanation: The pieces are "ababcbaca", "defegde" and "hijhklij". No letter appears in two pieces.
Example 2
Input: s = "eccbbbbdec"
Output: [10]
Explanation: The letter e appears at both ends, so the whole string is one piece.
Stuck? Open one hint at a time
Hint 1
If a piece has a letter, it must also have the last place where that letter appears.
Hint 2
Remember the last index of each letter. Move the end of the current piece further whenever a letter needs it.
Show all 3 solutions with explanations
Approach 1Rescan with lastIndexOf
The idea

Start a piece at start. Set its end to the last index of the first letter. Then walk through the piece. Move the end further whenever a letter's last index is further.

JavaScript
function partitionLabels(s) {  const result = [];  let start = 0;  while (start < s.length) {    let end = s.lastIndexOf(s[start]);    for (let i = start; i <= end; i++) end = Math.max(end, s.lastIndexOf(s[i]));    result.push(end - start + 1);    start = end + 1;  }  return result;}console.log(partitionLabels("ababcbacadefegdehijhklij")); // [9, 7, 8]console.log(partitionLabels("eccbbbbdec"));               // [10]
How it works

It is correct, but each lastIndexOf scans the string, so the worst case is O(n²).

Approach 2Greedy with a last-index table
The idea

First, do one pass to save the last index of every letter. Then do a second pass that tracks the end of the current piece. When the index reaches the end, close the piece.

JavaScript
function partitionLabels(s) {  const last = new Map();  for (let i = 0; i < s.length; i++) last.set(s[i], i);  const result = [];  let start = 0, end = 0;  for (let i = 0; i < s.length; i++) {    end = Math.max(end, last.get(s[i]));    if (i === end) {      result.push(end - start + 1);      start = i + 1;    }  }  return result;}console.log(partitionLabels("ababcbacadefegdehijhklij")); // [9, 7, 8]console.log(partitionLabels("eccbbbbdec"));               // [10]console.log(partitionLabels("a"));                         // [1]
How it works

To make as many pieces as possible, close each piece at the first moment you can. That is the greedy rule. It takes O(n) time and O(1) space, because the table holds at most 26 letters (the problem uses only lowercase English letters).

Approach 3Merge the span of each letter
The idea

Each letter covers a span, from its first index to its last index. The pieces are the groups you get when you merge spans that overlap. This is a preview of the next lesson.

JavaScript
function partitionLabels(s) {  const first = new Map(), last = new Map();  for (let i = 0; i < s.length; i++) {    if (!first.has(s[i])) first.set(s[i], i);    last.set(s[i], i);  }  const spans = [...first.keys()].map((ch) => [first.get(ch), last.get(ch)]).sort((a, b) => a[0] - b[0]);  const result = [];  let [start, end] = spans[0];  for (const [a, b] of spans.slice(1)) {    if (a > end) { result.push(end - start + 1); start = a; end = b; }    else end = Math.max(end, b);  }  result.push(end - start + 1);  return result;}console.log(partitionLabels("ababcbacadefegdehijhklij")); // [9, 7, 8]console.log(partitionLabels("eccbbbbdec"));               // [10]
How it works

It is correct and leads nicely into merging intervals, but it does more work than the greedy.

Which approach should you use?

Use the last-index table. (LeetCode 763.)

Make it stick

Make it stick — close this page, then
  1. Explain the greedy-choice property, and show with coins [1, 3, 4] that it can fail.
  2. Explain an exchange argument in your own words.
  3. Say why activity selection sorts by end time and not by start time.
  4. Say how jump game II is like a breadth-first search without a queue.

Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.

What's next

Lesson 48 takes the habit "sort by the right key, then scan" and uses it on a family of problems about intervals (ranges such as 1 to 5). You will merge them, insert into them, and remove the fewest overlapping ones.

Practise on LeetCode

Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.

Published by Jainik · Last updated · How these lessons are made

Keep learning

Related series