Algorithms & Coding Interviews · Greedy, DP & Bits

Greedy

Greedy algorithms commit to the locally best choice and never look back: one pass, simple code, when they're correct. Learn the common greedy shapes, how to justify a greedy choice in an interview, how to spot when greedy fails, and watch Kadane, Jump Game and Gas Station animated.

🧮 Algorithms & Coding Interviews● Intermediate⏱ 8 min read▶ 3 interactive🛠️ 4 exercises

🎯 What you'll learn

Common greedy shapes: reset, reach, sort-and-sweep, balance
Exchange and stays-ahead arguments
Counterexamples that call for DP instead
Six LeetCode problems with animated walkthroughs

📚 Before you start

Part 1The Pattern

A greedy algorithm builds a solution by making the locally best choice at each step and never reconsidering it. When it works, it's the simplest and fastest solution: usually one pass, or a sort plus one pass. The hard part is knowing when it works. Greedy is correct only if a locally optimal choice can always be extended to a globally optimal solution, and in interviews you're expected to justify that with a short argument, or to recognize that the problem needs dynamic programming instead.

Greedy keeps the farthest reachable index while scanning

1Typical Greedy Shapes

Shape	Example	Greedy rule
running value, reset when it stops helping	Maximum Subarray (Kadane), stock profit	extend or restart
farthest reach	Jump Game I/II	keep the max index reachable so far
sort, then sweep	intervals, meeting rooms, assign cookies	earliest end first / smallest that fits
balance / deficit	Gas Station, Lemonade Change	if the running balance goes negative, restart after it
last occurrence	Partition Labels	extend the current part to the last occurrence of every letter in it
smallest available	Hand of Straights, task scheduling	always start from the smallest remaining item

2Templates

typescript

function maxSubarrayTemplate(nums: number[]): number {
  let best = nums[0], cur = nums[0];
  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]);
    best = Math.max(best, cur);
  }
  return best;
}

function canReachEnd(nums: number[]): boolean {
  let reach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > reach) return false;
    reach = Math.max(reach, i + nums[i]);
  }
  return true;
}

python

def max_subarray_template(nums):          # Kadane: extend or restart, keep the best
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)             # a negative running sum only hurts → restart
        best = max(best, cur)
    return best

def can_reach_end(nums):                  # track the farthest reachable index
    reach = 0
    for i, step in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + step)
    return True

3Proving a Greedy Choice (Briefly)

Interviewers accept a compact argument. Two standard ones:

Exchange argument: take any optimal solution that differs from the greedy one at the first choice; swap in the greedy choice and show the solution is no worse. (Used for "earliest end first" in interval scheduling.)
Stays ahead: show that after every step, the greedy solution is at least as good as any other on some measure (e.g. Jump Game: greedy reach is never smaller than any strategy's reach).

4When Greedy Fails

Coin change with coins [1, 3, 4] and amount 6: greedy takes 4 + 1 + 1 = 3 coins, but 3 + 3 = 2 coins is optimal. Whenever an early choice can block a better combination later, you need dynamic programming (02-dynamic_programming_fundamentals). A useful habit: before committing to greedy, try to construct a small counterexample.

⚠️ Common Pitfalls

Assuming greedy works without a counterexample check (coin change, 0/1 knapsack).
Sorting by the wrong key (start vs end, value vs value/weight ratio).
Initializing Kadane with 0 when all numbers can be negative (start from nums[0]).
Off-by-one in reach checks: you're stuck when the current index is greater than the reach.
Not stating the justification ("why is this choice safe?").

📋 Quick Reference

text

Kadane: cur = max(x, cur + x); best = max(best, cur)
Jump Game: if i > reach: fail; reach = max(reach, i + a[i])
Gas Station: if total < 0 → -1; reset start when the tank goes negative
Justify: exchange argument or "stays ahead"; else → DP

Part 2Interview Problems

Six problems where a local rule provably leads to the global optimum: Kadane, farthest reach, balance resets, last occurrences and smallest-first grouping.

1Maximum Subarray (LeetCode 53)

🟠 Medium. Return the largest sum of a non-empty contiguous subarray.

text

[-2,1,-3,4,-1,2,1,-5,4] → 6   ([4,-1,2,1])

Approach. Kadane's algorithm: the best subarray ending at i either extends the best one ending at i − 1 or starts fresh at i, whichever is larger. A negative running sum can only hurt what follows, so drop it.

Complexity. O(n) time, O(1) space.

typescript

function maxSubArray(nums: number[]): number {
  let best = nums[0], cur = nums[0];
  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]);
    best = Math.max(best, cur);
  }
  return best;
}

python

def max_sub_array(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

2Jump Game (LeetCode 55)

🟠 Medium. nums[i] is the maximum jump length from index i. Can you reach the last index from index 0?

text

[2,3,1,1,4] → true · [3,2,1,0,4] → false

Approach. Scan left to right keeping the farthest reachable index. If you ever stand on an index beyond it, you're stuck.

Complexity. O(n) time, O(1) space.

typescript

function canJump(nums: number[]): boolean {
  let reach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > reach) return false;
    reach = Math.max(reach, i + nums[i]);
  }
  return true;
}

python

def can_jump(nums):
    reach = 0
    for i, step in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + step)
    return True

3Jump Game II (LeetCode 45)

🟠 Medium. Return the minimum number of jumps to reach the last index (always reachable).

text

[2,3,1,1,4] → 2   (0 → 1 → 4)

Approach. BFS by levels without a queue: the current jump covers indices up to end; while scanning them, track the farthest index the next jump could reach. When you pass end, take a jump and set end to that farthest reach.

Complexity. O(n) time, O(1) space.

typescript

function jump(nums: number[]): number {
  let jumps = 0, end = 0, farthest = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
    if (i === end) { jumps++; end = farthest; }
  }
  return jumps;
}

python

def jump(nums):
    jumps = end = farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == end:                   # current jump's range is exhausted
            jumps += 1
            end = farthest
    return jumps

4Gas Station (LeetCode 134)

🟠 Medium. Stations on a circle have gas[i]; driving to the next costs cost[i]. Return the starting station for a full loop, or −1.

text

gas = [1,2,3,4,5], cost = [3,4,5,1,2] → 3

Approach. If total gas < total cost, it's impossible. Otherwise scan once with a running tank; whenever the tank goes negative at station i, no station from the current start through i can work (they'd arrive with even less), so restart from i + 1.

Complexity. O(n) time, O(1) space.

typescript

function canCompleteCircuit(gas: number[], cost: number[]): number {
  let total = 0, tank = 0, start = 0;
  for (let i = 0; i < gas.length; i++) {
    total += gas[i] - cost[i];
    tank += gas[i] - cost[i];
    if (tank < 0) { start = i + 1; tank = 0; }
  }
  return total < 0 ? -1 : start;
}

python

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    start = tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start, tank = i + 1, 0
    return start

5Partition Labels (LeetCode 763)

🟠 Medium. Split s into as many parts as possible so each letter appears in at most one part. Return the part sizes.

text

"ababcbacadefegdehijhklij" → [9,7,8]

Approach. Record the last index of every letter. Scan, extending the current part's end to the last occurrence of each letter seen; when the index reaches the end, close the part.

Complexity. O(n) time, O(26) space.

typescript

function partitionLabels(s: string): number[] {
  const last = new Map<string, number>();
  for (let i = 0; i < s.length; i++) last.set(s[i], i);
  const sizes: number[] = [];
  let start = 0, end = 0;
  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, last.get(s[i])!);
    if (i === end) { sizes.push(end - start + 1); start = i + 1; }
  }
  return sizes;
}

python

def partition_labels(s):
    last = {c: i for i, c in enumerate(s)}
    sizes, start, end = [], 0, 0
    for i, c in enumerate(s):
        end = max(end, last[c])
        if i == end:
            sizes.append(end - start + 1)
            start = i + 1
    return sizes

6Hand of Straights (LeetCode 846)

🟠 Medium. Can the cards be split into groups of groupSize consecutive values?

text

[1,2,3,6,2,3,4,7,8], groupSize 3 → true   ([1,2,3],[2,3,4],[6,7,8])

Approach. The smallest remaining card must start a group (nothing smaller can cover it). Count cards, iterate values in sorted order, and for each value with remaining count c, consume c copies of the next groupSize − 1 consecutive values; fail if any is short.

Complexity. O(n log n) time for sorting the distinct values.

typescript

function isNStraightHand(hand: number[], groupSize: number): boolean {
  if (hand.length % groupSize) return false;
  const count = new Map<number, number>();
  for (const x of hand) count.set(x, (count.get(x) ?? 0) + 1);
  for (const x of [...count.keys()].sort((a, b) => a - b)) {
    const c = count.get(x)!;
    if (c === 0) continue;
    for (let v = x; v < x + groupSize; v++) {
      if ((count.get(v) ?? 0) < c) return false;
      count.set(v, count.get(v)! - c);
    }
  }
  return true;
}

python

def is_n_straight_hand(hand, group_size):
    if len(hand) % group_size:
        return False
    count = {}
    for x in hand:
        count[x] = count.get(x, 0) + 1
    for x in sorted(count):
        c = count[x]
        if c == 0:
            continue
        for v in range(x, x + group_size):
            if count.get(v, 0) < c:
                return False
            count[v] -= c
    return True

🧠 Key takeaways

Greedy = locally best choice, never revisited; usually O(n) or O(n log n).
Justify it: exchange argument or stays ahead; otherwise suspect DP.
Shapes: Kadane reset, farthest reach, sort + sweep, running balance, last occurrence.
Always try a small counterexample (coin change [1,3,4] → 6) before committing.

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

algo_greedy_exercise_1.py

TS PY

algo_greedy_exercise_2.py

TS PY

✅ Check yourself

Answer the questions — feedback is instant.

1. Why does Kadane restart when cur + x < x?

Drop the drag.

2. Greedy coin change fails for coins [1,3,4], amount 6 because…

Needs DP.

3. Jump Game: when are you stuck?

Zeros are fine if you can jump over.

4. Gas Station restarts after station i because…

They'd arrive with even less gas.

Source: algo_greedy_theory_1.md, algo_greedy_theory_2.md · generated by tools/build_lessons.py