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.
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.
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.
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.
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).
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.
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.
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.
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.