Hamropedia

DSA · Topic 15 of 18 · DP & Advanced Topics

Greedy

Take the best-looking move now — but only if you can explain why it can never hurt later.

By Manoj Kumar Thapa

AI Software Engineer ·

8 problems · O(n), or O(n log n) with sorting time, O(1) space

Step 1 Understand it

Remember it by

Take the best-looking move now — but only if you can explain why it can never hurt later.

Watch it happen

AnimationGreedy: make the locally best choice, and know why it is safe
Read the animation as text
  1. Find the contiguous stretch with the biggest sum. Walk once, keeping a running sum of the current stretch.
  2. Start with -2: running = -2, best = -2.
  3. The running sum before 1 was negative — carrying it can only drag 1 down. Drop it and start fresh at 1: running = 1. New best: 1.
  4. Add -3: running = -2. Best stays 1.
  5. The running sum before 4 was negative — carrying it can only drag 4 down. Drop it and start fresh at 4: running = 4. New best: 4.
  6. Add -1: running = 3. Best stays 4.
  7. Add 2: running = 5. New best: 5.
  8. Add 1: running = 6. New best: 6.
  9. Add -5: running = 1. Best stays 6.
  10. Add 4: running = 5. Best stays 6.
  11. Answer: 6, from [4, -1, 2, 1]. The greedy rule — "a negative running sum never helps, drop it" — gives O(n) instead of checking every stretch.

The idea

A greedy algorithm makes the locally best choice at each step and never goes back. It's fast and simple, but only correct when you can argue that the local choice is always part of some best answer.

Picture it

flowchart LR
  X["next number x"] --> Q{"is the running sum<br/>negative?"}
  Q -->|"yes"| R["drop it: start fresh at x"]
  Q -->|"no"| K["add x to it"]
  R & K --> B["best = max(best, running sum)"] --> X
Kadane's rule: a negative running sum can only drag down what comes next, so throw it away.

Analogy

Paying £0.80 with the fewest UK coins: take the biggest coin that fits (50p, 20p, 10p). It works for UK coins.

Where the analogy breaks

With coins of 1, 3 and 4, making 6 greedily gives 4 + 1 + 1 (three coins) but 3 + 3 uses two. Greedy needs a reason it's safe; otherwise use DP.

More detail

What it is

A Greedy algorithm is like a person who always grabs the biggest piece of cake available RIGHT NOW, without thinking about tomorrow. At every single step, a Greedy algorithm makes the most optimal, locally 'best' choice possible, hoping that all these small optimal choices suddenly magically combine into the global best solution! It's much faster than Dynamic Programming because it refuses to look backward or reconsider.

When to use it

  • When making a localized optimal choice guarantees a global optimal outcome (The Greedy Choice Property).
  • When the problem asks for the 'minimum', 'maximum', or 'longest' and involves jumping, intervals, or making a series of absolute choices.

How it works

Greedy algorithms don't have a strict universal template because the 'greedy choice' entirely depends on the problem. Usually, it involves **sorting** the data first (e.g., sorting by cost, or end time), and then looping through it once, greedily taking the best option at that exact moment while keeping a running tally.

Example walkthrough

Input: Jump Game: nums = [2,3,1,1,4]. Can you reach the end?

  1. Set your 'Goal' to the absolute last index (index 4).
  2. Look strictly at the index before it (Index 3). Can Index 3 jump to the Goal? (nums[3] = 1. 3+1 = 4. Yes!).
  3. Greedy choice: Move the Goal post closer to index 3! We now only need to reach 3.
  4. Index 2 can reach 3! Goal is now 2.
  5. Index 1 can reach 2! Goal is now 1.
  6. Index 0 can reach 1! Goal is now 0. We made it!

Result: true

Related patterns

  • Intervals: Interval problems almost always rely on sorting and then a Greedy pass to merge them.

Step 2 Recognise it

Words that signal it

  • 'Maximum subarray' (Kadane)
  • 'Can you reach the end?', 'minimum jumps'
  • Scheduling: pick by earliest end or largest gain
  • A running total that should be reset when it turns bad (gas station)

Don't confuse it with

  • Dynamic Programming: Try to break greedy with a small counter-example. If you can, it's DP.
  • Sliding Window: Kadane looks like a window, but it decides 'restart or continue' from the running sum alone — no left pointer to manage.

Gut check

Is there one obvious best move each step, and can I prove it's always safe? → greedy.

How to recognise it in an interview

The problem talks about 'Jumping max distance', 'Minimizing coin usage', or 'Scheduling the most activities'.

Step 3 The template

The general shape. Adapt it to each problem rather than learning one solution per problem.

python
def solve(nums):
    best = ...                       # the answer so far
    running = ...                    # the state you carry (sum, farthest reach, fuel)
    for x in nums:
        running = ...                # make the locally best choice
        best = ...                   # keep the best seen
    return best
The same template in Java
text
class Solution {
    public boolean canJump(int[] nums) {
        // Start the goalpost at the absolute ending index
        int goal = nums.length - 1;
        
        // Work backwards greedily
        for (int i = nums.length - 2; i >= 0; i--) {
            if (i + nums[i] >= goal) {
                goal = i; // Move the goalpost closer!
            }
        }
        
        // If the goalpost successfully reached the start, we win.
        return goal == 0;
    }
}
TimeO(n), or O(n log n) with sorting
SpaceO(1)

Common mistakes

  • Using greedy without testing a counter-example.
  • Kadane: starting best at 0, which is wrong when every number is negative.
  • Jump Game: forgetting to stop when the current index is beyond the farthest reach.
  • Forgetting to Sort the input data before making greedy decisions.

Step 4 Watch it run

Two problems, traced step by step exactly as the code runs.

Easy example: Maximum Subarray (Kadane)

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

xdecisionrunning sumbest
-2keep the running sum-2-2
1running sum was negative → drop it, start fresh11
-3keep the running sum-21
4running sum was negative → drop it, start fresh44
-1keep the running sum34
2keep the running sum55
1keep the running sum66
-5keep the running sum16
4keep the running sum56

Result: 6

Notice: The answer [4, −1, 2, 1] = 6 starts right after a reset — the moment the running sum went negative.

python
def max_sub_array(nums):
    best = nums[0]
    running = 0
    for x in nums:
        if running < 0:
            running = 0
        running += x
        best = max(best, running)
    return best

Medium example: Jump Game

Input: nums = [3, 2, 1, 0, 4]

inums[i]farthest reachfarthest
03max(0, 0 + 3) = 33
12max(3, 1 + 2) = 33
21max(3, 2 + 1) = 33
30max(3, 3 + 0) = 33
44index 4 is past the farthest reach (3) → stuck3

Result: False

Notice: Only one number matters: how far you could possibly get. If you ever stand beyond it, you're stuck.

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

Step 5 Practise

Read each question and say the pattern and the trick out loud before you open the answer. Then solve it on LeetCode. Tick a problem once you've solved it on your own: it comes back for review tomorrow, then after 3, 7, 14 and 30 days, then every month, on the DSA page.

Medium

  1. Maximum Subarray Medium

    Find the contiguous subarray with the largest sum.

    Show answer

    Technique: Kadane's algorithm

    The clue: Largest sum of a contiguous subarray.

    The trick: Drop the running sum when it goes negative; it can only hurt what follows.

  2. Jump Game Medium

    Each number is the maximum jump from that spot; can you reach the last index?

    Show answer

    Technique: Greedy farthest reach

    The clue: 'Can you reach the end?'.

    The trick: Track the farthest reachable index; if you ever stand beyond it, you can't.

  3. Jump Game II Medium

    Find the fewest jumps to reach the last index.

    Show answer

    Technique: Greedy BFS by ranges

    The clue: 'Fewest jumps' (always reachable).

    The trick: Treat each jump as a level: scan the current range, track the farthest next reach, and count a jump when the range ends.

  4. Gas Station Medium

    Find the station where you can start and drive a full circle without running out of gas.

    Show answer

    Technique: Greedy running total

    The clue: A circle, and a running total that must stay positive.

    The trick: If total gas < total cost, impossible; otherwise restart just after any point where the tank goes negative.

  5. Hand of Straights Medium

    Decide whether cards can be split into groups of consecutive numbers of a given size.

    Show answer

    Technique: Greedy from the smallest card + counts

    The clue: Groups of consecutive values.

    The trick: The smallest card must start a group; take the next group-size values from the counts.

  6. Merge Triplets to Form Target Triplet Medium

    Decide whether taking element-wise maxima of some triplets can produce the target.

    Show answer

    Technique: Greedy filtering

    The clue: Max operations only ever increase values.

    The trick: Ignore any triplet with a value above the target; check whether the good ones together match each target position.

  7. Partition Labels Medium

    Split a string into as many parts as possible so that each letter appears in only one part.

    Show answer

    Technique: Greedy with last occurrences

    The clue: Every letter must stay inside one part.

    The trick: Record each letter's last index; extend the current part's end to the last index of every letter seen; cut when you reach it.

  8. Valid Parenthesis String Medium

    Decide whether a string of '(', ')' and '*' (either bracket or empty) can be valid.

    Show answer

    Technique: Greedy range of open counts

    The clue: '*' could be three things — track a range instead of trying all.

    The trick: Keep the minimum and maximum possible open brackets; fail if the max goes negative; succeed if the min can be 0 at the end.

What to say in the interview

'I noticed that making the locally optimal choice doesn't penalize future decisions. Therefore, I can bypass DP and use a strictly O(N) Greedy algorithm.'

Follow-up prep

Can you prove why your Greedy choice doesn't fail? (Interviewer might ask you to justify why DP isn't needed).