Greedy

Greedy means: at every step take the choice that looks best right now and never look back. It is only correct when you can argue the local best never hurts the future, so always ask "why can't this choice be a mistake?".

After this topic: You can propose a greedy rule, test it against a counter-example, and explain why it is safe.

Do these first: Heap / Priority Queue

0 of 8 solved0%

Step 1 · Read the lesson

Greedy

Take the best local choice and never undo it, when you can argue it is safe.

Step 2 · Solve the problems in order

Try each one for about 20 minutes first. Problems with a Run code tab are checked right here. If you are stuck, open Nudge, think again, then Idea. Go skeleton only gives the function shape, and Reference solution is for comparing after you have tried. Tick the box when you could solve it again without help.

1.Maximum SubarrayMedium
If the running sum before the current number is negative, is it helping or hurting?
Kadane: curr = max(num, curr + num); best = max(best, curr).
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func maxSubArray(nums []int) int
Tested with go test. Try it yourself first, then compare.
// MaxSubArray (Kadane): if the running sum before this number is negative it only hurts, so drop it and // start fresh here. cur = the best sum of a subarray that ENDS at this number. func MaxSubArray(nums []int) int { best, cur := nums[0], 0 for _, n := range nums { cur = max(n, cur+n) best = max(best, cur) } return best }
2.Jump GameMedium
Do not simulate every jump — track only how far you can possibly reach.
Keep the farthest reachable index; if the current index is beyond it you are stuck; return true when farthest ≥ last.
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func canJump(nums []int) bool
Tested with go test. Try it yourself first, then compare. It is explained step by step on the Greedy lesson page.
// CanJump: can you reach the last index if nums[i] is the max jump length from i? // Greedy: track the farthest index reachable so far. If we ever stand beyond it, we are stuck. func CanJump(nums []int) bool { farthest := 0 for i, jump := range nums { if i > farthest { // an unreachable gap return false } farthest = max(farthest, i+jump) } return true }
3.Jump Game IIMedium
Think in "waves": all positions reachable with one jump, then two jumps, and so on.
Track the end of the current wave and the farthest reach inside it; when you pass the wave end, take another jump and extend the wave.
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func jump(nums []int) int
Tested with go test. Try it yourself first, then compare. It is explained step by step on the Greedy lesson page.
// MinJumps: fewest jumps to reach the last index (it is always reachable). // Greedy BFS-by-ranges: end is the edge of the current jump; farthest is the best edge of the next one. func MinJumps(nums []int) int { jumps, end, farthest := 0, 0, 0 for i := 0; i < len(nums)-1; i++ { farthest = max(farthest, i+nums[i]) if i == end { // we must jump now: take the best landing we saw jumps++ end = farthest } } return jumps }
4.Gas StationMedium
If you cannot get from station A to B, can any station between A and B be a valid start?
If total gas < total cost return −1. Otherwise scan with a running tank; when it drops below 0 reset it and make the next station the new start.
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func canCompleteCircuit(gas []int, cost []int) int
Tested with go test. Try it yourself first, then compare. It is explained step by step on the Greedy lesson page.
// CanCompleteCircuit: the start index that completes the circular route, or -1. // Greedy: if the tank goes negative at i, no start in [start, i] can work, so restart at i+1. func CanCompleteCircuit(gas, cost []int) int { total, tank, start := 0, 0, 0 for i := range gas { diff := gas[i] - cost[i] total += diff tank += diff if tank < 0 { start = i + 1 tank = 0 } } if total < 0 { return -1 } return start }

5.Hand of StraightsMedium

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

func isNStraightHand(hand []int, groupSize int) bool

Tested with go test. Try it yourself first, then compare.

// IsNStraightHand: the smallest remaining card can only start a group (nothing smaller is left to precede it),
// so repeatedly start a run at the smallest card and take groupSize consecutive values.
func IsNStraightHand(hand []int, groupSize int) bool {
	if len(hand)%groupSize != 0 {
		return false
	}
	count := map[int]int{}
	for _, c := range hand {
		count[c]++
	}
	keys := make([]int, 0, len(count))
	for c := range count {
		keys = append(keys, c)
	}
	sort.Ints(keys)
	for _, start := range keys {
		n := count[start]
		if n == 0 {
			continue
		}
		for v := start; v < start+groupSize; v++ {
			if count[v] < n {
				return false // the run cannot be completed
			}
			count[v] -= n // start n groups at once
		}
	}
	return true
}

6.Merge Triplets to Form Target TripletMedium

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

func mergeTriplets(triplets [][]int, target []int) bool

Tested with go test. Try it yourself first, then compare.

// MergeTriplets: merging takes the max in each position, so a triplet with ANY value above the target can never
// be used. Among the usable ones, check that every target value is hit exactly by some triplet.
func MergeTriplets(triplets [][]int, target []int) bool {
	var hit [3]bool
	for _, t := range triplets {
		if t[0] > target[0] || t[1] > target[1] || t[2] > target[2] {
			continue
		}
		for i := 0; i < 3; i++ {
			if t[i] == target[i] {
				hit[i] = true
			}
		}
	}
	return hit[0] && hit[1] && hit[2]
}

7.Partition LabelsMedium

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

func partitionLabels(s string) []int

Tested with go test. Try it yourself first, then compare. It is explained step by step on the Greedy lesson page.

// PartitionLabels: split s so each letter appears in at most one part; return the part sizes.
// Greedy: a part must reach at least the last occurrence of every letter inside it.
func PartitionLabels(s string) []int {
	last := map[rune]int{}
	for i, r := range s {
		last[r] = i
	}
	var sizes []int
	start, end := 0, 0
	for i, r := range s {
		end = max(end, last[r]) // extend the part to cover this letter's last occurrence
		if i == end {           // nothing inside the part appears later: close it
			sizes = append(sizes, end-start+1)
			start = i + 1
		}
	}
	return sizes
}

8.Valid Parenthesis StringMedium

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

func checkValidString(s string) bool

Tested with go test. Try it yourself first, then compare.

// CheckValidString: '*' can be '(', ')' or empty. Instead of choosing, track the RANGE of possible counts of
// unmatched '(' : lo (stars all used as ')') up to hi (stars all used as '(').
func CheckValidString(s string) bool {
	lo, hi := 0, 0
	for _, c := range s {
		switch c {
		case '(':
			lo++
			hi++
		case ')':
			lo--
			hi--
		default:
			lo--
			hi++
		}
		if hi < 0 {
			return false // even with every star as '(' there are too many ')'
		}
		lo = max(lo, 0) // a negative count just means some stars were treated as empty
	}
	return lo == 0
}