Topic 14: Greedy Algorithms

Key-Intuition: Greedy algorithms rely on the optimal choice property and local decisions leading to global optima.

Canonical Questions #

Reachability and Jumping Games #

Jump from indices or points under certain conditions

Problems #

This is somewhat easy to reason with, we have a goal and we work backwards from the goal as much as possible and finally check if we have reached the start. The greedy choice property is that if I take a step as soon as I find it, that step will be at least one option / subset from the set of options I can, I can eventually build towards the goal. Best optimal local action is just to take a viable candidate as soon as we see it.

this avoids the exploration of ALL possibilities and gives us AN optimal solution to our problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
   class Solution:
     def canJump(self, nums: List[int]) -> bool:
       goal = len(nums) - 1

         # start from left of the goal
         for i in range(len(nums) - 2, -1, -1):
           # if I can find a jmp source, I take it:
         if i + nums[i] >= goal:
           goal = i

         return goal == 0

Code Snippet 1: Jump Game (55)

Pattern Extraction

Core Insight: Track the farthest reachable index as you scan left to right. If you ever land on an index beyond the current farthest reach, the answer is False. If farthest reach \(\geq\) last index, True. Pattern Name: Greedy Reachability Sweep Canonical Section: Greedy > Reachability / Jump Games Recognition Signals:

“Can you reach the end” from position 0
At each position, you can jump up to nums[i] steps forward
Boolean output (reachability)

Anti-Signals:

Need the minimum number of jumps – greedy but with jump counting. Connects to LC 45 Jump Game II
Can jump backward – BFS/BFS, not greedy
Jump distances are fixed (not “up to”) – different problem structure

Decision Point: Reachability = single greedy sweep with max-reach tracking. Minimum jumps = greedy with level-based BFS or interval tracking.

Pitfalls and Misconceptions

Trap: Using BFS or DP when greedy suffices. Why: BFS is \(O(n^2)\) worst case. DP is \(O(n^2)\). The greedy sweep is \(O(n)\). Correction: Just track max_reach = max(max_reach, i + nums[i]) and check i < max_reach=.
Trap: Not short-circuiting when max_reach > n - 1=. Why: Once you’ve confirmed reachability, continuing the loop is wasted work. Correction: Return True as soon as max_reach > n - 1=.

Problem Mutations

What if you needed the minimum number of jumps? (stress-tests: boolean vs count) Track the current level’s farthest reach and the next level’s farthest reach. Increment jumps when you step beyond the current level. Connects to LC 45 Jump Game II.
What if you could jump backward? (stress-tests: forward-only) BFS with visited set. Greedy max-reach doesn’t work because backward jumps can unlock forward progress.
What if jump costs varied by position? (stress-tests: uniform cost) Dijkstra’s on the implicit graph. Greedy reachability doesn’t account for costs. Connects to weighted shortest path.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Jump Game generated via batch canonical enrichment pass. Review against personal solving experience and adjust.

Jump Game II (45)

This differs a little, the greedy choice property is to take the best jump based on the frontier that we can currently reach (which is what current_end represents in the code below)

the clever part about this is that we need to think about the main goal and think about proxy ways that the goal can be rephrased. In this case, the main goal is to be able to make the least jumps and reach the end. A rephrasing means that we need each jump to make the furthest future progress as possible.

Applying the greedy framework

Problem Restatement:
Find minimum number of jumps to reach the last index.
Greedy Choice Property:
At every jump, pick next index from reachable positions that allows furthest future progress.
Optimal Substructure:
If minimum jumps to index i is known, then the jumps to reachable next indices from i can be minimized greedily.
Decision Making:
Instead of exploring all paths, keep track of max reachable index within current jump; when you reach current jump boundary, increment jump count, update boundary to furthest reachable.
Global Optimal:
Greedy steps collectively ensure minimal jumps since you never miss an opportunity to jump to a position enabling maximal progress.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
   class Solution:
      def jump(self, nums: List[int]) -> int:
         """
          Each local choice i need to choose something that gives me the rightmost advancement. I can sweep onto the current "frontier"/"current_end" and pick that best choice after exploring all choices.


          So this is like a sweeping search pointer then decision-maker pointer.
          """
          if len(nums) == 1:
              return 0

          jumps = 0
          current_end = 0     # End of current jump coverage
          furthest = 0        # Furthest reachable index so far

          for i in range(len(nums) - 1):  # no need to jump from last element
             furthest = max(furthest, i + nums[i])

              # When reach the boundary of current jump range
              if i == current_end:
                 jumps += 1
                 current_end = furthest

                  if current_end >= len(nums) - 1:
                      break

          return jumps

Code Snippet 2: Jump Game II (45)

Pattern Extraction

Core Insight: BFS-like level processing: track the farthest reachable index in the current “level” (jump). When you step beyond the current level’s boundary, increment jumps and extend the boundary. Pattern Name: Greedy BFS-Level Jump Counting Canonical Section: Greedy > Reachability / Jump Games Recognition Signals:

“Minimum number of jumps to reach the end”
Always reachable (guaranteed by problem)
Greedy: always extend as far as possible per jump

Anti-Signals:

Can jump backward – BFS with visited set, not greedy
Need to check IF reachable first – that’s LC 55

Decision Point: Minimum jumps = greedy level-based BFS (\(O(n)\)). Reachability = greedy max-reach sweep (LC 55).

Pitfalls and Misconceptions

Trap: Using explicit BFS with a queue (\(O(n^2)\) worst case). Why: Each node adds up to nums[i] neighbours to the queue. Correction: Track current_end and farthest. When i = current_end=: current_end = farthest; jumps + 1=.
Trap: Incrementing jumps when reaching the last index (off-by-one). Why: You want to reach n - 1, not go past it. Don’t increment when the current boundary already covers the end. Correction: Loop until i < n - 1 (not i < n). Check if current_end > n - 1= to break early.

Problem Mutations

What if jumps had variable costs? (stress-tests: uniform cost) DP or Dijkstra on the implicit graph. Greedy doesn’t account for costs.
What if you could also jump backward? (stress-tests: forward-only) BFS with visited set. Greedy forward-only doesn’t work.
What if you needed the actual jump sequence? (stress-tests: count vs path) Track which position triggered each level boundary. Reconstruct from the end.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Jump Game II generated via batch canonical enrichment pass.

Resource Allocation & Circular Trips #

Distribute resources or find valid circular trips

Problems #

Gas Station (134)

The question actually helps to make the solutioning simpler for us (e.g. by saying that there’s a single unique solution). We have to do two things: (i) check global feasibility and (ii) check what should be the starting idx

for (i) we just keep accumulating and the final sum has to be positive

for (ii) we know that if at any point in time, the running sum is negative, then the previous starting index won’t work (between i (the exploration pointer) and 0), so just keep starting fresh (i + 1) if the tank goes negative.

This approach is similar to the kadane algorithm in its essence.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
   class Solution:
      def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
         # total_balance: we're just accumulating for all the gas stations, if the total_balance at the end of the accumulation is negative then the journey is impossible.
         # curr_balance is just a curr accumulator
          total_balance, curr_balance = 0, 0
          # best candidate yet (may not be useful if the journey is impossible)
          best_start = 0

          for i in range(len(gas)):
             diff = gas[i] - cost[i]
             total_balance += diff
             curr_balance += diff

              # if impossible then all from best_start to i are impossible, so we restart the joruney from the next one (though we don't actually make the journey)
              if curr_balance < 0:
                 best_start = i + 1
                 curr_balance = 0

          return best_start if total_balance >= 0 else -1

   # alternative language:
   class Solution:
      def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
         total_tank = 0         # net gas over the whole journey
         current_tank = 0       # net gas from the current starting candidate
         start_index = 0        # candidate starting point

          for i in range(len(gas)):
             gain = gas[i] - cost[i]
             total_tank += gain
             current_tank += gain

              # If we can't reach the next station, start from i + 1
              if current_tank < 0:
                 start_index = i + 1
                 current_tank = 0

          return start_index if total_tank >= 0 else -1

Code Snippet 3: Gas Station (134)

General Greedy Problem-solving Steps:
Formulate the subproblem:
Can I make a locally optimal decision (e.g., when to reset my starting point) that leads to the global optimum (successful circuit)?
Greedy choice property:
If I fail at curr_balance < 0, any previous candidate in this segment can’t be the start—reset is safe.
Optimal substructure:
Once you fail, the next possible successful start is strictly after your failure point.
Iterate with this rule:
Reset candidate each time running tank falls negative, while maintaining total balance.
Check feasibility:
Only possible if total gas ≥ total cost.

Pattern Extraction

Core Insight: If total gas \(\geq\) total cost, a solution exists. The starting point is right after the position where cumulative surplus hits its minimum. Pattern Name: Circular Sweep with Reset Canonical Section: Greedy > Circular Problems Recognition Signals:

Circular route with resource collection and consumption
“Find starting point for a complete circuit”
At most one valid starting point (unique solution guaranteed)

Anti-Signals:

Multiple valid starting points – need to enumerate all
Resource can be stored beyond capacity – different constraint

Decision Point: Total feasibility check + greedy reset. If cumulative < 0 at position \(i\), everything in \([start, i]\) fails as a starting point. Reset start = i + 1.

Pitfalls and Misconceptions

Trap: Trying all \(n\) starting points (\(O(n^2)\)). Why: The greedy observation (reset after deficit) gives \(O(n)\). Correction: Single pass: if tank < 0, reset start = i + 1 and tank = 0.
Trap: Not checking total feasibility (sum(gas) > sum(cost)=). Why: Without the total check, you might report a start position for an infeasible circuit. Correction: Check total first. If infeasible, return -1.

Problem Mutations

What if there were multiple valid starting points? (stress-tests: unique solution) Each minimum in the cumulative surplus curve is a valid start. Return all.
What if the route were not circular? (stress-tests: circular) Linear route: just check if cumulative surplus stays non-negative from the start. Simpler.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Gas Station generated via batch canonical enrichment pass.

Sorting and Matching #

Greedy sorting based on problem-specific criteria and matching elements

Problems #

Partition Labels (763) This problem fundamentally relies on greedy expansion and two-pointer/caterpillar technique. It can also be viewed as interval partitioning, where intervals are letter occurrences. The solution merges overlapping intervals greedily.

This is really a 2 pointer caterpillar type but we can make life easy by knowing when is the last idx when a particular character appears. This can help us determine when to segment (and how many within the segment).

simpler than it looks actually, the main thing is the “greedy” part which is we need to expand then consume like a caterpiller, how far to expand? until all within this window don’t have their last occurrence somewhere outside of the window. It’s like some sort of linear dependency culling thing going on.

Greedy framework:

Greedy Choice: At any point, expand the partition to include the last occurrence of the current character.
Feasibility Check: You can end a partition only when all letters inside it don’t appear beyond the partition end.
Optimal Substructure: The global optimum (max partitions) arises from correctly identifying all partition boundaries greedily without backtracking.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
    from typing import List

    class Solution:
        def partitionLabels(self, s: str) -> List[int]:
            # we can save time by doing the pre-calculations, this dictcomp will just keep getting updated and give us the last idx
            last_occurrence = {c: i for i, c in enumerate(s)}
            partitions = []

            # use two pointes, move like a caterpillar
            start = 0
            end = 0

            for i, c in enumerate(s):
                end = max(end, last_occurrence[c])
                if i == end: # no more to consider, we can segment this off
                    size = i - start + 1
                    partitions.append(size)
                    start = i + 1

            return partitions

Code Snippet 4: Partition Labels (763)

Pattern Extraction

Core Insight: Find the last occurrence of each character. Greedily extend the current partition to include the last occurrence of every character in it. When the current index reaches the partition boundary, close the partition. Pattern Name: Greedy Interval Merging with Last-Occurrence Tracking Canonical Section: Sliding Window > Interval-Based Partitioning (also Greedy) Recognition Signals:

“Partition string into maximum parts such that each character appears in at most one part”
Greedy partitioning with reach/boundary extension
Precompute last occurrences

Anti-Signals:

Minimum partitions (not maximum) – different problem, likely DP
Characters can overlap between partitions – not a valid partition constraint

Decision Point: “Each character in at most one part” means each character’s range [first, last] defines a constraint. Merge overlapping ranges greedily. This is interval merging applied to character ranges.

Pitfalls and Misconceptions

Trap: Not precomputing last occurrences, instead scanning ahead each time. Why: Scanning ahead for each character’s last occurrence is \(O(n^2)\). Precomputing is \(O(n)\). Correction: One pass to build last = {c: i for i, c in enumerate(s)}, then one pass to partition.
Trap: Closing the partition too early – when the current character’s last occurrence is reached but other characters in the partition still have later occurrences. Why: The partition boundary must accommodate ALL characters in the partition, not just the current one. Correction: boundary = max(boundary, last[c]) for each character. Close partition only when i = boundary=.

Problem Mutations

What if you needed the minimum number of partitions with the same constraint? (stress-tests: max vs min) Minimum partitions = 1 (the whole string). The problem is interesting only as maximum partitions.
What if the constraint were that each character appears in at most \(k\) parts? (stress-tests: at most 1) More complex. Need to track how many parts each character spans and allow up to \(k\) splits. Likely DP.
What if the input were an array of integers instead of characters? (stress-tests: alphabet size) Same algorithm, but last is a hash map instead of a size-26 array. No structural change.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Partition Labels generated via batch canonical enrichment pass. Review against personal solving experience.

TODO Candy (135)
TODO Assign Cookies (455)

Maximum/Minimum Subarray and Kadane’s Framework #

Problems involving maximum or minimum contiguous sums using local greedy decisions

Problems #

Maximum Subarray (53) :completed:

This is literally max subarray sum (kadane’s algo)

Since we are looking for subarrays ( contiguous, non-empty ), we immediately try to see if we can make some local decisions that lead up to global optima. Greedy choice property here is that we accumulate ONLY if the diff is not 0, so if the total sum becomes negative, then we can start fresh. This is Kadane’s Algo, classic stuff.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    class Solution:
        def maxSubArray(self, nums: List[int]) -> int:
            best = -float('inf')
            curr_accum = 0
            for num in nums:
                # greedy choice: I make the best choice possible
                new_accum = curr_accum + num
                best = max(best, new_accum)
                # choose A: start from scratch or B: carry on
                curr_accum = 0 if new_accum < 0 else new_accum

            return  best

Code Snippet 5: Maximum Subarray (53)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        """
        This is straight up just Kadane Algo:
        1. we care about inclusion or exclusion.
        2. elements can be negative

        Thinking of it as a state-tracing 1D DP isn't that far off though. We can realise that it's Kadane-by focusing on the substructures and then emphasising the contiguious nature of the problem.

        Fastest recognition heuristic: "contiguous subarray" + "maximise sum" + values can be negative → Kadane, immediate.
        """
        best_ending_here = nums[0]
        global_best = nums[0]
        for num in nums[1:]:
            best_ending_here = max(best_ending_here + num, num) # build onto, include num OR start fresh
            global_best = max(global_best, best_ending_here)

        return global_best

Code Snippet 6: Maximum Subarray (53)

For discussion sake, the question extension asks us to consider a divide-and-conquer approach. We have to realise that we can do left, right or max subarray cases: A: max subarray is entirely in the left half B: max subarray is entirely in the right half C: max subarray spans the left and right half, across the middle point.

We just do partial sums for them and find our solution:

Interval Coverage and Partitioning #

Partitioning sequences or intervals using greedy local expansions

Problems #

⭐️Partition Labels (763) This problem fundamentally relies on greedy expansion and two-pointer/caterpillar technique. It can also be viewed as interval partitioning, where intervals are letter occurrences. The solution merges overlapping intervals greedily.

Greedy framework:

Greedy Choice: At any point, expand the partition to include the last occurrence of the current character.
Feasibility Check: You can end a partition only when all letters inside it don’t appear beyond the partition end.
Optimal Substructure: The global optimum (max partitions) arises from correctly identifying all partition boundaries greedily without backtracking.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
   from typing import List

         class Solution:
             def partitionLabels(self, s: str) -> List[int]:
                 # we can save time by doing the pre-calculations, this dictcomp will just keep getting updated and give us the last idx
                 last_occurrence = {c: i for i, c in enumerate(s)}
                 partitions = []

                 # use two pointes, move like a caterpillar
                 start = 0
                 end = 0

                 for i, c in enumerate(s):
                     end = max(end, last_occurrence[c])
                     if i == end: # no more to consider, we can segment this off
                         size = i - start + 1
                         partitions.append(size)
                         start = i + 1

                 return partitions

Code Snippet 7: Partition Labels (763)

Pattern Extraction

“Partition string into maximum parts such that each character appears in at most one part”
Greedy partitioning with reach/boundary extension
Precompute last occurrences

Anti-Signals:

Minimum partitions (not maximum) – different problem, likely DP
Characters can overlap between partitions – not a valid partition constraint

Pitfalls and Misconceptions

Trap: Not precomputing last occurrences, instead scanning ahead each time. Why: Scanning ahead for each character’s last occurrence is \(O(n^2)\). Precomputing is \(O(n)\). Correction: One pass to build last = {c: i for i, c in enumerate(s)}, then one pass to partition.
Trap: Closing the partition too early – when the current character’s last occurrence is reached but other characters in the partition still have later occurrences. Why: The partition boundary must accommodate ALL characters in the partition, not just the current one. Correction: boundary = max(boundary, last[c]) for each character. Close partition only when i = boundary=.

Problem Mutations

What if you needed the minimum number of partitions with the same constraint? (stress-tests: max vs min) Minimum partitions = 1 (the whole string). The problem is interesting only as maximum partitions.
What if the constraint were that each character appears in at most \(k\) parts? (stress-tests: at most 1) More complex. Need to track how many parts each character spans and allow up to \(k\) splits. Likely DP.
What if the input were an array of integers instead of characters? (stress-tests: alphabet size) Same algorithm, but last is a hash map instead of a size-26 array. No structural change.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Partition Labels generated via batch canonical enrichment pass. Review against personal solving experience.

Frequency Counting and Constructive Greedy (Group Formation, Coverage) #

Use frequency counts to form groups or satisfy constraints greedily

Problems #

Hand of Straights (846)

this is really just a grouping exercise and we use frequency counter to assist us. Frequency counting is sound because we have the “consecutive card” constraint, so we don’t need to do PQ-approaches, we just need to make sure that if card value of j has m freq, then card value of j + 1, (j + 2), (j + 3) + … must have at least m each, else we know that it won’t work.

remember that the sorting helps us out for the consecutive argument.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

   from collections import Counter

   class Solution:
      def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:

          # early returns if nondivisible
          if len(hand) % groupSize != 0:
              return False

          count = Counter(hand)

          for card in sorted(count):
             # can start from this:
              if count[card] > 0:
                 # if consecutive, then we at least need this many next cards:
                  required = count[card]
                  # since it's consecutive, we can do (card + groupSize) as the end range
                  for next_card in range(card, card + groupSize):
                      if count[next_card] < required:
                          return False

                      count[next_card] -= required
                      # this allows the next_card to be possibly reused as as starting card

          return True

Code Snippet 8: Hand of Straights (846)

Framing into greedy context:

Greedy decision: Always use the smallest available card to start a group of consecutive cards.
Why smallest?
Because completing groups starting from smaller cards prevents “blocking” larger cards later that must be consecutive.
Local optimal choice:
At any point, if you have leftover cards of the smallest value, you must include them in a sequence starting now to avoid leftover partial groups.
Global optimality:
This local choice guarantees no leftover cards prevent creating proper groups down the line.
This fits the greedy choice property and optimal substructure:
Greedily constructing consecutive sequences starting from the smallest card makes the remainder problem similar but smaller.
The solution to the smaller problem leads to the global solution.

Pattern Extraction

Core Insight: Sort the cards. Greedily form groups starting from the smallest available card. Use a Counter to track remaining cards. For each group, consume consecutive values starting from the current smallest. Pattern Name: Greedy Consecutive Group Formation Canonical Section: Greedy > Grouping / Partitioning Recognition Signals:

“Group elements into sets of \(k\) consecutive values”
Greedy: always start from the smallest unused value
Counter-based tracking of remaining elements

Anti-Signals:

Groups don’t need to be consecutive – just partition into equal groups
Need to maximise the number of groups (not fixed size) – different optimisation

Decision Point: Consecutive grouping = sort + greedy from smallest.

Pitfalls and Misconceptions

Trap: Not checking if len(hand) % groupSize = 0= first. Why: If the total count isn’t divisible by group size, no valid grouping exists. Correction: Early return False if len(hand) % groupSize ! 0=.
Trap: Not handling the case where a needed consecutive value has count 0. Why: If we need value v+1 but its count is 0, the current group can’t be formed. Correction: When decrementing, if the needed value isn’t in the counter or has count 0, return False.

Problem Mutations

What if the values didn’t need to be consecutive? (stress-tests: consecutive constraint) Much simpler: just check if len(hand) % k = 0=. Any partition works.
What if the group size could vary? (stress-tests: fixed group size) Need DP or more complex greedy. The fixed group size is what makes this problem tractable with a simple greedy.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Hand of Straights generated via batch canonical enrichment pass.

Merge and Element-wise Coverage #

Coverage checking and pruning in multidimensional greedy problems

Problems #

Merge Triplets to Form Target Triplet (1899)

Idea here is that we don’t need to simulate the merging, we just need to know if it’s feasible or not to reach the target (coverage). So we just need to comb through and consider merge candidates (which are just:

ignore the entire triple if any of the individual values exceed the corresponding target value) \(\implies\) a strategy to prune choices

mark 3 flags to check if we have reached out targets, and if so, to return early:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
         class Solution:
             def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
                 tx, ty, tz = target
                 found_x, found_y, found_z = False, False, False

                 for x, y, z in triplets:
                     # If all coordinates are already covered, we can return early
                     if found_x and found_y and found_z:
                         return True

                     # Skip triplets that exceed target in any coordinate
                     if x > tx or y > ty or z > tz:
                         continue

                     # Mark coverage for coordinates matching target
                     if x == tx:
                         found_x = True
                     if y == ty:
                         found_y = True
                     if z == tz:
                         found_z = True

                 # Return True only if all three target coordinates are covered
                 return found_x and found_y and found_z

Code Snippet 9: Merge Triplets to Form Target Triplet (1899)

here’s an clean but slow version, but it’s slower becuase no early returns and has intermediate lists

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
         class Solution:
             def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
                 filtered = [t for t in triplets if all(t[i] <= target[i] for i in range(3))]
                 covered = [False] * 3

                 for t in filtered:
                     if all(covered): return True

                     for i in range(3):
                         if t[i] == target[i]:
                             covered[i] = True

                 return all(covered)

Framework Step	Explanation
Problem restatement:	Can we get exactly the `target` triplet via coordinate-wise max merges of any triplets?
Greedy choice property:	We select triplets that do not exceed the target in any coordinate and cover each target coordinate exactly once.
Optimal substructure:	After choosing triplets covering each coordinate, the merged result is exactly the target.
Algorithm:	Filter triplets not exceeding target; check coverage for each coordinate by exact matches.
Result:	If all coordinates covered, answer true; else false.

Pattern Extraction

Core Insight: A triplet is usable if none of its values exceed the corresponding target value. Among usable triplets, check if we can cover each target position (at least one usable triplet has the target value at each position). Pattern Name: Greedy Filtering + Coverage Check Canonical Section: Greedy > Filtering/Selection Recognition Signals:

“Can you form a target from max-operations on triplets?”
Filter out bad candidates, check coverage of remaining

Anti-Signals:

Need to minimise the number of operations – counting, not just feasibility

Decision Point: Filter triplets that would exceed any target coordinate. Among survivors, check that each target coordinate is achievable.

Pitfalls and Misconceptions

Trap: Including triplets that have ANY value exceeding the target. Why: Max-merging with such a triplet would push that coordinate above the target permanently. Correction: Only consider triplets where a[i] < target[i]= for ALL three positions.

Problem Mutations

What if the operation were min instead of max? (stress-tests: max-merge) Filter out triplets with any value BELOW target. Check coverage similarly.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Merge Triplets to Form Target Triplet.

Parentheses and String Validation via Range Counting or Stack-Based Greedy #

Validate balanced strings with wildcards using greedy interval counting or stack methods

Problems #

Valid Parenthesis String (678)

This is just 2 stacks: one for actual working for open parentheses, and the other is for wildcards (for making rectifications). we just need to know that the rectifications require us to keep track of when the wildcard was seen. We can only rectify if the wildcard came after the problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
   class Solution:
      def checkValidString(self, s: str) -> bool:
         # wildcards allow us to make "mistakes"
          stack, wildcard = [], []

          for idx, char in enumerate(s):
              if char == "(":
                 stack.append(idx)

              if char == ")" and not stack and not wildcard:
                  return False

              # rectifiable mistake
              if char == ")" and not stack and wildcard:
                 wildcard.pop()

              if char == ")" and stack:
                 stack.pop()

              if char == "*":
                 wildcard.append(idx)

          if stack:
              while is_correct_order:= stack and wildcard and stack[-1] < wildcard[-1]:
                 stack.pop()
                 wildcard.pop()

          return not stack

Code Snippet 10: Valid Parenthesis String (678)

An alternative way is to see it as greedy interval counting:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
   class Solution:
      def checkValidString(self, s: str) -> bool:
         low = 0   # minimum unmatched '('
         high = 0  # maximum unmatched '('

          for ch in s:
          if ch == '(':
             low += 1
             high += 1
          elif ch == ')':
             low = max(low - 1, 0)
             high -= 1
          else:  # ch == '*'
             low = max(low - 1, 0)  # if '*' acts as ')'
             high += 1              # if '*' acts as '('

          if high < 0:
                  return False  # can't balance because too many ')'

          return low == 0  # balanced if minimal unmatched '(' is zero

Code Snippet 11: Valid Parenthesis String (678) – Alternative: greedy-interval counting

explanation:

Intuition:
The low and high represent a range of possible “open parenthesis counts” given the ambiguous ‘*’.
While scanning, a ‘*’ increases uncertainty: it could be ‘(’, ‘)’, or `` (empty), so the actual open count can vary within this range.
By maintaining these bounds, you efficiently track whether the string can possibly be balanced.
Here’s what they mean precisely:
low: The minimum number of unmatched open parentheses that you must have considering all interpretations of ‘’ so far (where ‘’ can act as ‘(’, ‘)’, or empty).
It helps track the least possible open count because some ‘*’ may act as closing parentheses or empty strings.
high: The maximum number of unmatched open parentheses that you could possibly have, again considering all ways to interpret ‘*’.
It tracks the most open parentheses possible, if all ‘*’ are counted as ‘(’.
How low and high get updated per character:
When you see ‘(’:
Both low and high increase by 1 (you definitely have one more unmatched open parenthesis).
When you see ‘)’:
Both low and high decrease by 1 (you close at least one open parenthesis, possibly more).
When you see ‘*’:
low decreases by 1 (if ‘*’ acts as ‘)’)
high increases by 1 (if ‘*’ acts as ‘(’)
After each step:
If high becomes negative → too many closing parentheses → invalid → return False early.
Make sure low never goes below zero (can’t have negative minimum unmatched opens).
At the end, if low == 0, it means there is at least one interpretation of ‘*’ that makes the string balanced (all open parentheses matched).
An alternative is the greedy interval counting approach:
Track a range [low, high] of the number of open parentheses possible at current character.
Update this range as you scan the string:
( increases both low and high
) decreases both low and high
* can either act as ‘(’, ‘)’, or empty, so adjust accordingly
If high < 0 at any point → invalid
At the end, if low = 0= → valid
This greedy counting approach is harder to see at first but very elegant.

Contextualising to the greedy framework:

Greedy Algorithm Context & Framework
Problem Restatement:
Check if a string with (, ), and * can be interpreted as a valid parentheses string considering * as either (, ), or empty.
Key insight:
The * can flexibly act to correct mismatches locally.
Greedy property:
Keep track of possible open parenthesis counts (range [low, high]).
Local decision:
Adjust low and high based on current character assuming minimal and maximal open parentheses.
Global optimality:
If at any point, it’s impossible to balance parentheses (e.g., too many )), fail early.
Final check: If after processing all characters, the minimal count of open parentheses can reach zero (balanced), string is valid.

Pattern Extraction

Core Insight: Track a range [lo, hi] of possible open-bracket counts. '(' increases both, ')' decreases both, '*' spreads the range. The string is valid iff 0 is in the range at the end. Pattern Name: Greedy Range Tracking Canonical Section: Greedy > Range / Interval Counting Recognition Signals:

Parenthesis validation with wildcards ('*' can be '(', ')', or empty)
Need to check if ANY assignment of wildcards makes the string valid
\(O(n)\) time, \(O(1)\) space

Anti-Signals:

No wildcards – simple counter or stack
Need to count the NUMBER of valid assignments – DP

Decision Point: Wildcards create uncertainty in the open-bracket count. Tracking the range of possible counts is the key insight.

Pitfalls and Misconceptions

Trap: Trying to use a stack to handle wildcards. Why: A stack commits to a specific interpretation of each wildcard. The range approach tracks all possibilities simultaneously. Correction: Track lo (minimum possible open count) and hi (maximum possible open count).
Trap: Allowing lo to go negative. Why: You can’t have fewer than zero unmatched open brackets. Clamping lo to 0 is essential. Correction: lo = max(lo, 0) after each step.
Trap: Only checking hi > 0= without checking lo < 0= at the end. Why: hi < 0 means no assignment works (too many close brackets). lo > 0 at the end means some open brackets are always unmatched. Correction: During: if hi < 0: return False. After: return lo = 0=.

Problem Mutations

What if you needed to count valid assignments? (stress-tests: existence vs counting) DP with state = current open count. Each wildcard triples the state space. \(O(n^2)\).
What if wildcards could only be '(' or empty? (stress-tests: wildcard flexibility) hi increases but lo stays the same on wildcard. The range shrinks less.
What if there were multiple bracket types with wildcards? (stress-tests: single bracket type) Need a stack-based approach or multi-dimensional range tracking. Much more complex.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Valid Parenthesis String generated via batch canonical enrichment pass.

Activity Selection and Interval Scheduling #

Select maximum number of non-overlapping intervals/events

Problems #

Course Schedule III (630) — Advanced scheduling with optimization, extending topological and greedy concepts

This was easier than it seems.

misconception log

   problem: LC 630 (Course Schedule III)
   canonical: Greedy Deadline-Driven Scheduling
   mistake_type: pattern_misclass
   specifically: Approached as backtracking (explore take/skip branches), trying to optimize the search with heuristics. Missed that the problem admits a clean greedy solution: sort by deadline, drop longest on conflict.
   fix_pattern: When a problem asks "maximize count subject to hard constraints," and items can be reordered, suspect greedy + deadline sorting. If conflicts arise, dropping the highest-cost item (by the metric you care about) is often optimal.
   recognition_signal_missed: The freedom to reorder courses (they don't have prerequisites) is the signal for greedy. Backtracking is necessary only if there are dependencies.

The pedestrian approach is to consider a backtracking one, it won’t be good enough because that will end up having exponential time complexity

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

   class Solution:
     def scheduleCourse(self, courses: List[List[int]]) -> int:
       """
         [initial thoughts]
          * Feels like greedy because there's some local decisions to be made possibly and to move along. -- correction: no, the local decision will affect decisions later
           - now it feels like a backtracking thing, if there's a clash, I either take the previous one or skip it
          * Asked for max number of courses -- so we need to at least know the ordering of which they expire and we need to try and get the minimum durations for them -- so some kind of min-heap approach to choosing which to take
          * is it just a sorting or something?  -- first order by lastDay then by the duration, take the least first
          * on the sorted, it doesn't feel right for it to be a linear scan because it matters
         """
       n = len(courses)
       courses.sort(key=lambda x: (x[1], x[0]))

         def consider(idx, curr_time):
             if idx == n:
                 return 0

             skip = consider(idx + 1, curr_time)
             duration, deadline = courses[idx]
             if curr_time + duration <= deadline: # no clash
               take = 1 + consider(idx + 1, curr_time + duration)
             else:
               take = 0 # can't take it, so this branch contributes 0

             return max(skip, take)

         return consider(0, 0)

Code Snippet 12: backtracking solution in \(O(2^n)\) time

Instead, we realise that we need to look for a greedy approach – one that will allow us to exploit a greedy choice property to get an optimal solution. Greedy Insight: we shall sort by deadline and then greedily add each course in order. If a course would violate a deadline, then we shall remove the longest course taken so far (outside of the current one) so that we would have a minimized impact on the schedule.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
   import heapq

   class Solution:
     def scheduleCourse(self, courses: List[List[int]]) -> int:
       courses.sort(key=lambda x:x[1])

         max_heap = [] # maxheap of durations
         curr_day = 0

         for duration, deadline in courses :
           # try taking this course:
             curr_day += duration
             heapq.heappush(max_heap, -duration) # allows max-heap semantics

             # if violated:
             if curr_day > deadline:
               longest = -(heapq.heappop(max_heap))
               curr_day -= longest

         return len(max_heap)

Code Snippet 13: (630) Course-schedule III optimal solution – greedy approach, choose using max-heap

Pattern Extraction

Core Insight: Sort tasks by deadline. Greedily add each task. When a deadline would be violated, remove the longest task taken so far, not the current one. This minimizes wasted time and keeps room for future tasks.

Pattern Name: Deadline-Driven Greedy Substitution with Max-Heap

Canonical Section: Greedy Algorithms > Deadline-Constrained Scheduling

Recognition Signals:

“Maximize count of tasks/courses” subject to hard deadlines
Tasks can be reordered (no dependencies)
Taking a task consumes time; dropping it frees time
Conflict resolution: “which task should I drop to fit a new one?”

Anti-Signals:

Tasks have dependencies (DAG) – topological sort, not greedy
Weighted tasks (profit/cost) – DP or weighted scheduling
Soft deadlines with penalties – different objective, not feasibility-driven

Decision Point: Greedy fails if task order is fixed or dependencies matter. This pattern applies when you have scheduling freedom and can reorder/drop tasks at will.

Interviewer Comms: “Sort by deadline. Add courses greedily in order. When you overshoot a deadline, drop the longest course taken so far — this frees the most time for future courses. Use a max-heap to find the longest in O(log n) time.”

Pitfalls and Misconceptions

Trap: Approaching this as a full backtracking exploration (explore all 2^n take/skip branches). Why: Correct but exponential (\(O(2^n)\)). Your code attempted this with heuristic pruning but pruned incorrectly. Correction: Recognize the greedy property: sorting by deadline + greedy substitution gives \(O(n \log n)\). No backtracking needed.
Trap: Dropping the current course instead of the longest course when a conflict arises. Why: Dropping the current course might waste opportunities. The longest course is “dead weight” — it consumed the most time for one unit of count. Dropping it minimizes regret. Correction: Always drop the longest course in the heap, not the current one attempting to enter.
Trap: Not sorting by deadline first. Why: Without deadline order, you lose the greedy property. Early deadlines take priority; later courses are adjustments. Without sorting, you can’t guarantee feasibility. Correction: courses.sort(key=lambda x: x[1]) ensures deadline order is processed first.
Trap: Using a min-heap instead of a max-heap for durations. Why: You’d drop the shortest course on conflict, keeping the longest. This wastes time and violates the greedy property. Correction: Use a max-heap: heapq.heappush(max_heap, -duration) to find the longest in O(log n).
Trap: Attempting to “fix” a backtracking solution by skipping non-viable courses, instead of exploring full take/skip branches. Why: Your original code checked if the next course clashed, and if so, skipped it entirely. This breaks the search tree — you never explore “take course B, skip course C, take course D”. You need either full backtracking or greedy, not a hybrid. Correction: Either commit to backtracking (2^n, correct but slow) or switch to greedy (O(n log n), correct and fast). Don’t mix.

Problem Mutations

What if you needed to minimize schedule duration instead of maximize course count? (stress-tests: optimization objective) Greedy still works, but the heap logic changes. Drop the longest to minimize total time. Same algorithm, different interpretation.
What if courses had weights (profits) instead of uniform count? (stress-tests: uniform -> weighted) Greedy fails. You’d need DP: dp[i][time] = max profit using courses 0..i within time limit. Dropping the longest by duration doesn’t maximize profit.
What if courses had prerequisites (dependencies)? (stress-tests: freedom -> constraints) Greedy fails. Topological sort required. Course B can’t be taken until A is done. Now dropping A affects B’s feasibility.
What if deadlines were soft (penalties for lateness instead of rejection)? (stress-tests: hard -> soft) Different objective. Greedy doesn’t apply; need weighted scheduling or DP to balance count vs. lateness cost.
What if you could take multiple courses in parallel (e.g., 2 per time unit)? (stress-tests: sequential -> parallel) Becomes a bin-packing or interval scheduling problem. Max-heap no longer sufficient.

AI usage disclosure Claude Sonnet 4.6 · coaching session

Standardised annotation dropdowns for Course Schedule III (LC 630) generated via coaching session. Core misconception: attempting backtracking with incorrect pruning instead of recognising the greedy property. The greedy insight is that deadline-ordered processing + dropping the longest course on conflict is optimal. Backtracking is correct but exponential; greedy is the correct pattern here.

Coin Change (Greedy Cases) #

Use greedy when canonical coin denominations permit optimal greedy solutions

TODO Problems #

(to be added)

Huffman Coding and Greedy Tree Construction #

Build optimal prefix codes or trees using greedy merges

TODO Problems #

(to be added)

SOE #

Incorrect greedy choice proof or counterexamples
Wrong tie-breaker decisions leading to suboptimal solutions
In cases where we are greedily rectifying problems, e.g. the “Valid Parenthesis String (678)” we know that wildcards are to be used to rectify problems, but we need to ensure that the relative ordering is kept so that the attempt at rectifying is legitimate. (we can’t use a wildcard to rectify if it came earlier).

Decision Flow #

Multiple feasible solutions? → Attempt greedy with sorting
Resource or capacity constraints? → Greedy exchange principle

Styles, Tricks and Boilerplate #

Boilerplate #

Kadane’s Algorithm for subarray sums/etc (\(O(n)\) single sweep, greedy approach) #

Kadane’s Algorithm is a dynamic programming technique and is the gold standard for maximum subarray sum problems.

A subarray is continguous region of an array. We wish to find out the max subarray based on some scoring system.

We keep a global max_so_far and a local one, max_ending_here. This is because for each element we encounter, we have 2 choices:

A: continue extending the current subarray
B: start a new subarray

how to make the choice? suppose the scoring was a positive score.

If choice A makes the running sum negative then its effect is worse than if it was a 0. So we should pick choice B at that point.

This gives us the following style, Kadane’s Algorithm:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def max_subarray_sum(nums):
    max_so_far = float('-inf')
    max_ending_here = 0

    for num in nums:
        max_ending_here += num
        max_so_far = max(max_so_far, max_ending_here)
        if max_ending_here < 0:
            max_ending_here = 0

    return max_so_far

Code Snippet 14: Kadane's Algorithm for subarray sums/etc (\(O(n)\) single sweep, greedy approach)

Activity Selection / Interval Scheduling Maximisation #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def max_non_overlapping(intervals):
    """Greedy: sort by end time, always pick earliest-finishing compatible interval."""
    intervals.sort(key=lambda x: x[1])
    count = 0
    last_end = float('-inf')
    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end
    return count

Code Snippet 15: Activity selection: maximise non-overlapping intervals by sorting on end time

AI usage disclosure Claude Opus 4.6 · boilerplate generation

Activity selection boilerplate, the canonical greedy interval scheduling algorithm. Review for style.

Canonical Questions #

Reachability and Jumping Games #

Problems #

Resource Allocation & Circular Trips #

Problems #

Sorting and Matching #

Problems #

Maximum/Minimum Subarray and Kadane’s Framework #

Problems #

Interval Coverage and Partitioning #

Problems #

Frequency Counting and Constructive Greedy (Group Formation, Coverage) #

Problems #

Merge and Element-wise Coverage #

Problems #

Parentheses and String Validation via Range Counting or Stack-Based Greedy #

Problems #

Activity Selection and Interval Scheduling #

Problems #

Coin Change (Greedy Cases) #

TODO Problems #

Huffman Coding and Greedy Tree Construction #

TODO Problems #

SOE #

Decision Flow #

Styles, Tricks and Boilerplate #

Boilerplate #

Kadane’s Algorithm for subarray sums/etc (\(O(n)\) single sweep, greedy approach) #

Activity Selection / Interval Scheduling Maximisation #

TODO KIV #