Greedy algorithms:

The class of algorithms that make locally optimal choices at each step with the hope that these choices will lead to a globally optimal solution. They are particularly useful for optimization problems where you want to find the best solution among many possible ones.

Key Characteristics of Greedy Problems:

1. Optimal Substructure: The problem can be broken down into smaller subproblems, and the optimal solution to the problem can be constructed from optimal solutions to its subproblems.
2. Greedy Choice Property: A globally optimal solution can be arrived at by making a locally optimal (greedy) choice at each step. This means that the choice made at each step is the best possible at that moment without reconsidering previous choices.

Categorizing Problems Under the Greedy Bucket:

To determine if a problem can be solved using a greedy approach, ask yourself:

• Does the problem involve making a sequence of choices where each choice is the best possible at that moment?
• Can the problem be broken down into steps where the optimal solution to the entire problem depends on the optimal solution to its subproblems?
• Is it possible to make a choice at each step that looks best at the moment and still reach a global optimum?

Now, let's categorize each of the given problems under the greedy bucket based on these criteria.

When to Use Greedy?

1. Maximum Subarray → Drop negative sums, keep extending if positive (Kadane’s greedy choice).
2. Jump Game → Always jump to the farthest reachable index (local optimal = global optimal).
3. Jump Game II → Jump only when you must (minimize jumps by delaying decisions).
4. Gas Station → Restart from next station if gas runs out (no backtracking).
5. Hand of Straights → Always use the smallest card first (sorted greedy grouping).
6. Merge Triplets → Ignore triplets that exceed target (locally filter bad choices).
7. Partition Labels → Expand partition until last occurrence (greedy boundary tracking).
8. Valid Parenthesis → Track possible open counts (flexible wildcard handling).

Greedy in 1 Line

"If you can solve it by making the best local choice without backtracking, it’s greedy."

✅ Optimal Substructure: The best solution at step i depends only on step i-1.

✅ Greedy Choice Property: A locally optimal choice leads to a global optimum.

❌ No Backtracking Needed: If future choices don’t invalidate past decisions.

Step-by-Step Framework to Identify Greedy Problems

🔹 Step 1: Is It an Optimization Problem?

Look for keywords:

1. "Minimum/Maximum number of..."
2. "Smallest/Largest possible..."
3. "Can you reach/partition/select optimally?"

Example:

1. ✅ "Find the minimum jumps to reach the end." → Greedy (Jump Game II)
2. ❌ "Count all possible paths." → DP (not greedy)

🔹 Step 2: Can You Make Locally Optimal Choices?

Ask:

• Does the problem allow making a choice now without reconsidering past decisions?
• Is the solution built incrementally with no backtracking?

Test Case:

• ✅ Gas Station: Choose to start at station i if current_tank >= 0 → Greedy (no need to revisit past stations).
• ❌ House Robber: Can’t rob adjacent houses → DP (depends on previous choices).

🔹 Step 3: Is There a Clear Heuristic?

Common Greedy Rules:

1. "Take the smallest/largest first" → Sort + process (e.g., Hand of Straights).
2. "Drop negative contributions" → Reset when harmful (e.g., Kadane’s Algorithm).
3. "Expand until invalid" → Grow window while possible (e.g., Partition Labels).

Example:

• ✅ Maximum Subarray: Drop subarrays with negative sums → Greedy heuristic.

🔹 Step 4: Can You Solve It in a Single Pass?

Greedy Hallmark:

• O(n) time complexity (no nested loops).
• Track 1–2 variables (e.g., max_reach, current_sum).

Example:

• ✅ Valid Parenthesis String: Track min_open and max_open in one pass → Greedy.
• ❌ Longest Increasing Subsequence: Requires DP (O(n²)).

🔹 Step 5: Match Known Greedy Patterns

🔹 Step 6: Rule Out DP/Backtracking

Ask:

• Does the problem require evaluating all combinations? → DP.
• Can you solve it with incremental choices? → Greedy.

Example:

• ❌ Coin Change: Greedy fails for [1,3,4] and amount=6 → Requires DP.
• ✅ Jump Game: Track max_reach → Greedy.

📌 Final Checklist (Is It Greedy?)

1. Optimization goal? (min/max) → ✅
2. Local choices don’t affect future? → ✅
3. Single-pass solution? → ✅
4. Fits a greedy pattern? → ✅

If all 4 are true → Greedy!

Example Walkthrough: "Partition Labels"

1. Keyword: "Minimum partitions" → Optimization (✅).
2. Choice: Extend partition to last occurrence → No backtracking (✅).
3. Heuristic: "Expand as far as possible" (✅).
4. Single Pass: Track last_occurrence → O(n) (✅).
5. Pattern: Matches "expand until invalid" (✅).
6. Not DP: No need to evaluate all splits (✅).

Conclusion: Greedy!

🚀 When Greedy Fails (Red Flags)

• Counterexample Needed: Greedy fails if local choices lead to suboptimal results.
• Example: Coin change [1,3,4] for 6. Greedy gives 4+1+1 (3 coins), but optimal is 3+3 (2 coins).
• Requires Revisiting Choices: If past decisions affect future → DP.

Summary Flowchart

Practice Problem

Problem: "Given intervals, find the minimum number of intervals to remove to make the rest non-overlapping."

Apply the framework:

1. Optimization? ✅ (min removals).
2. Local choice? ✅ (pick earliest-ending interval).
3. Heuristic? ✅ "Sort by end time, take non-overlapping".
4. Single pass? ✅ O(n log n) sort + O(n) pass.
5. Pattern? ✅ "Interval scheduling".

Verdict: Greedy!

A boilerplate for greedy algorithm is:

function greedySolution(input) {

Step 1: Sort if needed (many greedy problems require sorting)
 // input.sort((a, b) => a - b); // Example for numbers
 // input.sort((a, b) => a[1] - b[1]); // Example for intervals

Step 2: Initialize tracking variables
 let result = 0; // or [], or true/false
 let currentState = 0;  //currentEnd, farthestReach, currentSum

Step 3: Iterate and make greedy choices
 for (let i = 0; i < input.length; i++) {
  // Update state based on greedy choice
  // Example: Take the best local option
  if (/* condition for taking this element */) {
   result++; // or update result
   currentState = /* update based on choice */;
  }
 }

Step 4: Handle edge cases (if any)
 if (result === 0 && input.length > 0) return // fallback value

Step 5: Return the result
 
return result;

}

Maximum Subarray

Given an array of integers nums, find the subarray with the largest sum and return the sum.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

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

Explanation: The subarray [4,-2,2,1,-1,4] has the largest sum 8.

Example 2:

function maxSubArray(nums) {
  let maxSum = nums[0];
  let currentSum = nums[0];

  for (let i = 1; i < nums.length; i++) {
    // Greedy choice: extend current subarray or start new?
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
  return maxSum;
}

Jump Game

You are given an integer array nums where each element nums[i] indicates your maximum jump length at that position.

Return true if you can reach the last index starting from index 0, or false otherwise.

Example 1:

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

Output: true

Explanation: First jump from index 0 to 1, then from index 1 to 3, and lastly from index 3 to 4.

Example 2:

function canJump(nums) {
  let farthest = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > farthest) return false; // Can't proceed further
    farthest = Math.max(farthest, i + nums[i]); 
    // Greedy: take max reach
  }
  return farthest >= nums.length - 1;
}

Jump Game II

 You are given an array of integers nums, where nums[i] represents the maximum length of a jump towards the right from index i. For example, if you are at nums[i], you can jump to any index i + j where:

• j <= nums[i]
• i + j < nums.length

You are initially positioned at nums[0].

Return the minimum number of jumps to reach the last position in the array (index nums.length - 1). You may assume there is always a valid answer.

Example 1:

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

Output: 2

Explanation: Jump from index 0 to index 1, then jump from index 1 to the last index.

Example 2:

function jump(nums) {
  let jumps = 0, currentEnd = 0, farthest = 0;
  for (let i = 0; i < nums.length - 1; i++) {
   // Greedy: track farthest
    farthest = Math.max(farthest, i + nums[i]); 
    if (i === currentEnd) { // Time to jump
      jumps++;
      currentEnd = farthest;
    }
  }
  return jumps;
}

Gas Station

There are n gas stations along a circular route. You are given two integer arrays gas and cost where:

• gas[i] is the amount of gas at the ith station.
• cost[i] is the amount of gas needed to travel from the ith station to the (i + 1)th station. (The last station is connected to the first station)

You have a car that can store an unlimited amount of gas, but you begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index such that you can travel around the circuit once in the clockwise direction. If it's impossible, then return -1.

It's guaranteed that at most one solution exists.

Example 1:

Input: gas = [1,2,3,4], cost = [2,2,4,1]

Output: 3

Explanation: Start at station 3 (index 3) and fill up with 4 unit of gas.

Your tank = 0 + 4 = 4

Travel to station 0. Your tank = 4 - 1 + 1 = 3

Travel to station 1. Your tank = 3 - 2 + 2 = 3

Travel to station 2. Your tank = 3 - 2 + 3 = 4

Travel to station 3. Your tank = 2 - 4 + 4 = 2

Example 2:

function canCompleteCircuit(gas, cost) {
  let totalGas = 0, currentGas = 0, start = 0;
  for (let i = 0; i < gas.length; i++) {
    totalGas += gas[i] - cost[i];
    currentGas += gas[i] - cost[i];
  
// Greedy: reset start if gas runs out
    if (currentGas < 0) { 
      start = i + 1;
      currentGas = 0;
    }
  }
  return totalGas >= 0 ? start : -1;
}

Explanation:

You can't start at station 0 or 1, since there isn't enough gas to travel to the next station.

If you start at station 2, you can move to station 0, and then station 1.

At station 1 your tank = 0 + 3 - 2 + 1 - 2 = 0.

You're stuck at station 1, so you can't travel around the circuit.

Hand of Straights

You are given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize.

You want to rearrange the cards into groups so that each group is of size groupSize, and card values are consecutively increasing by 1.

Return true if it's possible to rearrange the cards in this way, otherwise, return false.

Example 1:

Input: hand = [1,2,4,2,3,5,3,4], groupSize = 4

Output: true

Explanation: The cards can be rearranged as [1,2,3,4] and [2,3,4,5].

Example 2:

function isNStraightHand(hand, groupSize) {
  if (hand.length % groupSize !== 0) return false;
  hand.sort((a, b) => a - b); // Sort first
  const freq = new Map();
  for (const num of hand) freq.set(num, (freq.get(num) || 0) + 1);

  for (const num of hand) {
    if (freq.get(num) === 0) continue;
    for (let i = 0; i < groupSize; i++) {
  
     // Greedy: check consecutive
      if (!freq.get(num + i)) return false; 
      freq.set(num + i, freq.get(num + i) - 1);
    }
  }
  return true;
}

Explanation: The closest we can get is [1,2,3,4] and [3,5,6,7], but the cards in the second group are not consecutive.

Merge Triplets to Form Target

You are given a 2D array of integers triplets, where triplets[i] = [ai, bi, ci] represents the ith triplet. You are also given an array of integers target = [x, y, z] which is the triplet we want to obtain.

To obtain target, you may apply the following operation on triplets zero or more times:

Choose two different triplets triplets[i] and triplets[j] and update triplets[j] to become [max(ai, aj), max(bi, bj), max(ci, cj)].

* E.g. if triplets[i] = [1, 3, 1] and triplets[j] = [2, 1, 2], triplets[j] will be updated to [max(1, 2), max(3, 1), max(1, 2)] = [2, 3, 2].

Return true if it is possible to obtain target as an element of triplets, or false otherwise.

Example 1:

Input: triplets = [[1,2,3],[7,1,1]], target = [7,2,3]

Output: true

Explanation:

Choose the first and second triplets, update the second triplet to be [max(1, 7), max(2, 1), max(3, 1)] = [7, 2, 3].

Example 2:

function mergeTriplets(triplets, target) {
  let [x, y, z] = target;
  let foundX = false, foundY = false, foundZ = false;
  for (const [a, b, c] of triplets) {
    // Greedy: ignore triplets that exceed target
    if (a > x || b > y || c > z) continue;
    if (a === x) foundX = true;
    if (b === y) foundY = true;
    if (c === z) foundZ = true;
  }
  return foundX && foundY && foundZ;
}

Partition Labels

You are given a string s consisting of lowercase english letters.

We want to split the string into as many substrings as possible, while ensuring that each letter appears in at most one substring.

Return a list of integers representing the size of these substrings in the order they appear in the string.

Example 1:

Input: s = "xyxxyzbzbbisl"

Output: [5, 5, 1, 1, 1]

Explanation: The string can be split into ["xyxxy", "zbzbb", "i", "s", "l"].

Example 2:

function partitionLabels(s) {
  const lastOccurrence = {};
  for (let i = 0; i < s.length; i++) lastOccurrence[s[i]] = i;
  
  let start = 0, end = 0;
  const result = [];
  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, lastOccurrence[s[i]]); // Greedy: expand partition
    if (i === end) { // Partition found
      result.push(end - start + 1);
      start = end + 1;
    }
  }
  return result;
}

Valid Parenthesis String

You are given a string s which contains only three types of characters: '(', ')' and '*'.

Return true if s is valid, otherwise return false.

A string is valid if it follows all of the following rules:

• Every left parenthesis '(' must have a corresponding right parenthesis ')'.
• Every right parenthesis ')' must have a corresponding left parenthesis '('.
• Left parenthesis '(' must go before the corresponding right parenthesis ')'.
• A '*' could be treated as a right parenthesis ')' character or a left parenthesis '(' character, or as an empty string "".

Example 1:

Input: s = "((**)"

Output: true

Explanation: One of the '*' could be a ')' and the other could be an empty string.

Example 2:

function checkValidString(s) {
  let minOpen = 0, maxOpen = 0;
  for (const char of s) {
    if (char === '(') {
      minOpen++;
      maxOpen++;
    } else if (char === ')') {
      minOpen = Math.max(minOpen - 1, 0);
      maxOpen--;
    } else { // '*'
      minOpen = Math.max(minOpen - 1, 0);
      maxOpen++;
    }
    if (maxOpen < 0) return false; // More ')' than '('
  }
  return minOpen === 0;
}

Explanation: The string is not valid because there is an extra '(' at the beginning, regardless of the extra '*'.