NeetCode 150 · Greedy

Greedy Problems

Greedy algorithms make locally optimal choices at each step. The key is proving that a greedy choice leads to a global optimum — often by showing a better solution can be converted to the greedy one.

Problems: 8
Easy: 0
Medium: 8
Hard: 0
Learning approach: Read the problem. Try the test cases yourself first. Click Hint if stuck — it guides without spoiling. Use Show Solution only after a genuine attempt. Then hit Let's Code to run your solution live.
01 Medium ArrayDP
Find the subarray with the largest sum. Return the sum.
Test Cases
maxSubArray([-2,1,-3,4,-1,2,1,-5,4]) → 6 # [4,-1,2,1] maxSubArray([1]) → 1 maxSubArray([5,4,-1,7,8]) → 23
Kadane's algorithmreset on negativeO(n)
Kadane's: keep a running sum. If it becomes negative, reset to 0 (starting fresh is better). Track the best sum seen.
Python Solution
def maxSubArray(nums): max_sum = nums[0] cur = 0 for n in nums: if cur < 0: cur = 0 # reset — extending a negative sum is counterproductive cur += n max_sum = max(max_sum, cur) return max_sum
Key idea: Kadane's algorithm. If the current running sum is negative, starting fresh from the current element is always better. Track the best sum seen during the scan.
Time: O(n).
Space: O(1).
02 Medium ArrayGreedyDP
Each element represents max jump length. Starting from index 0, can you reach the last index?
Test Cases
canJump([2,3,1,1,4]) → True canJump([3,2,1,0,4]) → False
track max_reachO(n)greedy one-pass
Track the furthest index reachable. If you ever need to move past the max reach, return False.
Python Solution
def canJump(nums): max_reach = 0 for i, jump in enumerate(nums): if i > max_reach: return False # can't reach this index max_reach = max(max_reach, i + jump) return True
Key idea: Greedily track the maximum reachable index. If the current index exceeds max_reach, we're stuck. Otherwise, update max_reach and continue.
Time: O(n).
Space: O(1).
03 Medium ArrayGreedyDP
Given array where each element is max jump length, find the minimum number of jumps to reach the last index.
Test Cases
jump([2,3,1,1,4]) → 2 jump([2,3,0,1,4]) → 2
greedy BFS layerscurr_end/farthestO(n)
Think of it as BFS levels. Within the current jump range, find the farthest reach. When you exhaust the current range, increment jump count.
Python Solution
def jump(nums): jumps = farthest = curr_end = 0 for i in range(len(nums) - 1): farthest = max(farthest, i + nums[i]) if i == curr_end: # reached end of current jump range jumps += 1 curr_end = farthest return jumps
Key idea: BFS level by level. curr_end marks the end of the current jump level. When we reach it, we must take another jump — update curr_end to farthest. Count jumps.
Time: O(n).
Space: O(1).
04 Medium ArrayGreedy
n gas stations in a circle. gas[i] available, cost[i] to travel to next. Find starting station index to complete the circuit, or -1.
Test Cases
canCompleteCircuit([1,2,3,4,5],[3,4,5,1,2]) → 3 canCompleteCircuit([2,3,4],[3,4,3]) → -1
total gas checkcumulative tank resetO(n)
If total gas < total cost, it's impossible. Otherwise, a solution always exists. Find the starting point by resetting when tank goes negative.
Python Solution
def canCompleteCircuit(gas, cost): if sum(gas) < sum(cost): return -1 tank = 0 start = 0 for i in range(len(gas)): tank += gas[i] - cost[i] if tank < 0: start = i + 1 # can't start at or before i tank = 0 return start
Key idea: If total gas ≥ total cost, a solution exists. Find it by scanning: whenever tank goes negative, reset start to the next station (we know everything before can't be a valid start).
Time: O(n).
Space: O(1).
05 Medium ArrayGreedyHash Map
Alice has cards. Can she rearrange all cards into groups of groupSize consecutive cards?
Test Cases
isNStraightHand([1,2,3,6,2,3,4,7,8], 3) → True isNStraightHand([1,2,3,4,5], 4) → False
Countersort+consumeO(n log n)
Sort the distinct card values. For the smallest card, form a group of size groupSize starting from it. Decrement counts.
Python Solution
from collections import Counter def isNStraightHand(hand, groupSize): if len(hand) % groupSize != 0: return False count = Counter(hand) for card in sorted(count): if count[card] > 0: n = count[card] # need n groups starting at 'card' for i in range(groupSize): if count[card + i] < n: return False count[card + i] -= n return True
Key idea: Process cards from smallest to largest. For each card, form as many groups as needed (count[card] groups). If there aren't enough consecutive cards to complete the groups, return False.
Time: O(n log n).
Space: O(n).
06 Medium ArrayGreedy
Given triplets and a target, merge triplets by taking element-wise max. Return True if we can achieve target.
Test Cases
mergeTriplets([[2,5,3],[1,8,4],[1,7,5]],[2,7,5]) → True mergeTriplets([[3,4,5],[4,5,6]],[3,2,5]) → False
filter invalid tripletselement-wise maxO(n)
Only consider triplets where no element exceeds the corresponding target element (others can never help). Check if the max of valid triplets equals the target.
Python Solution
def mergeTriplets(triplets, target): result = [0, 0, 0] for t in triplets: # Skip triplets that exceed any target element if all(t[i] <= target[i] for i in range(3)): result = [max(result[i], t[i]) for i in range(3)] return result == target
Key idea: A triplet is only useful if none of its values exceed the corresponding target. Filter useful triplets, then check if their element-wise max equals the target.
Time: O(n).
Space: O(1).
07 Medium StringGreedy
Partition string so each letter appears in at most one part. Return list of part sizes.
Test Cases
partitionLabels('ababcbacadefegdehijhklij') → [9, 7, 8] partitionLabels('eccbbbbdec') → [10]
last occurrence mapextend end greedilyO(n)
For each character, find its last occurrence. As you scan, extend the current partition's end to the last occurrence of each character seen.
Python Solution
def partitionLabels(s): last = {ch: i for i, ch in enumerate(s)} result = [] start = end = 0 for i, ch in enumerate(s): end = max(end, last[ch]) # extend end to include this char's last occurrence if i == end: # we've covered all occurrences of chars in this partition result.append(end - start + 1) start = end + 1 return result
Key idea: Record the last occurrence of each character. Scan left to right, extending the current partition's end. When we reach the end, we've found a valid partition boundary.
Time: O(n).
Space: O(1).
08 Medium StringGreedyStackDP
String with '(', ')', and '*'. '*' can be '(', ')' or empty. Return True if valid.
Test Cases
checkValidString('(*)') → True checkValidString('(**))') → True checkValidString('(*()') → True
min/max open counttrack rangeO(n) O(1)
Track a range [min_open, max_open] of possible open bracket counts. '(' increases both; ')' decreases both; '*' expands the range. If max_open < 0, invalid.
Python Solution
def checkValidString(s): min_open = max_open = 0 for ch in s: if ch == '(': min_open += 1 max_open += 1 elif ch == ')': min_open -= 1 max_open -= 1 else: # '*' can be '(', ')' or '' min_open -= 1 max_open += 1 if max_open < 0: return False # too many ')' min_open = max(min_open, 0) # min can't go below 0 return min_open == 0
Key idea: Track the minimum and maximum possible open bracket count. '*' expands the range. If max_open < 0, there are too many ')'. At the end, min_open == 0 means we can always close all opens.
Time: O(n).
Space: O(1).
← Prev Category Next Category →