Sorting is the secret weapon that unlocks greedy solutions. It transforms chaotic data into monotonic sequences where greedy decisions become obvious.
But here's the challenge: what do you sort by? Start time or end time? Ascending or descending? Single array or both? The wrong sorting criterion leads to wrong answers, and this is one of the most common greedy mistakes.
In this guide, you'll learn when sorting enables greedy, systematic frameworks for choosing sorting criteria, complete templates, and how to avoid the #1 sorting mistake.
Use greedy with sorting when:
Template:
arr1.sort() # Sort by appropriate criterion
arr2.sort()
i = j = 0
while i < len(arr1) and j < len(arr2):
if can_match(arr1[i], arr2[j]):
i += 1
j += 1
else:
j += 1 # Or i += 1, depends on problemKey insight: Sorting creates monotonicity → enables greedy decisions.
Without sorting: No clear greedy choice
Children greed: [3, 1, 2]
Cookies: [1, 2, 1]
Which child gets which cookie? No obvious greedy strategy ✗With sorting: Greedy choice becomes obvious
Children greed: [1, 2, 3] (sorted)
Cookies: [1, 1, 2] (sorted)
Greedy: Match smallest greed with smallest satisfying cookie
Child 1 (greed=1) ← Cookie 1 (size=1) ✓
Child 2 (greed=2) ← Cookie 3 (size=2) ✓
Child 3 (greed=3) ← No cookies left
Result: 2 children satisfied (optimal) ✓Why it works: Sorting creates monotonicity. If cookie j can't satisfy child i, it can't satisfy any child i+1, i+2, ... (who have higher greed). This enables greedy skipping.
Sorting helps when:
Sorting hurts when:
Single array problems:
| Problem Type | Sort By | Example |
|---|---|---|
| Interval scheduling | End time | Meeting Rooms |
| Greedy selection | Value, size, or ratio | Fractional Knapsack |
| Pairing with self | Natural order | Two City Scheduling (by difference) |
Two array problems:
| Problem Type | Sort Both By | Example |
|---|---|---|
| Matching | Natural order | Assign Cookies |
| Pairing | Natural order | Boats to Save People |
| Bipartite matching | Natural order | Advantage Shuffle |
Special cases:
| Problem Type | Sort By | Example |
|---|---|---|
| Sort by ratio | value/weight | Fractional Knapsack |
| Sort by difference | cost[A] - cost[B] | Two City Scheduling |
| Sort by custom key | Problem-specific | Various |
Sort ascending when:
Sort descending when:
Example:
# Assign Cookies: Sort both ascending
children.sort() # Smallest greed first
cookies.sort() # Smallest cookie first
# Match smallest greed with smallest satisfying cookie
# Fractional Knapsack: Sort descending by ratio
items.sort(key=lambda x: x.value/x.weight, reverse=True)
# Take highest value/weight ratio firstSort both when:
Sort one when:
Example:
# Assign Cookies: Sort BOTH
children.sort()
cookies.sort()
# Two Sum II: Array already sorted, don't sort again
# (given sorted array)def greedy_two_pointer(arr1, arr2):
"""
Template for greedy matching/pairing with two pointers.
Args:
arr1: First array (e.g., requirements)
arr2: Second array (e.g., resources)
Returns:
Count of successful matches
Time: O(n log n + m log m)
Space: O(1)
"""
# Sort both arrays (criterion depends on problem)
arr1.sort()
arr2.sort()
# Two pointers
i = j = 0
count = 0
while i < len(arr1) and j < len(arr2):
# Check if current elements can be matched
if can_match(arr1[i], arr2[j]):
# Match successful
count += 1
i += 1
j += 1
else:
# Can't match, move appropriate pointer
# If arr2[j] too small, try next arr2
# If arr2[j] too large, try next arr1
j += 1 # Or i += 1, depends on problem
return count
# Helper function (problem-specific)
def can_match(requirement, resource):
return resource >= requirementfunction greedyTwoPointer(arr1, arr2) {
arr1.sort((a, b) => a - b);
arr2.sort((a, b) => a - b);
let i = 0, j = 0, count = 0;
while (i < arr1.length && j < arr2.length) {
if (canMatch(arr1[i], arr2[j])) {
count++;
i++;
j++;
} else {
j++;
}
}
return count;
}
function canMatch(requirement, resource) {
return resource >= requirement;
}public int greedyTwoPointer(int[] arr1, int[] arr2) {
Arrays.sort(arr1);
Arrays.sort(arr2);
int i = 0, j = 0, count = 0;
while (i < arr1.length && j < arr2.length) {
if (canMatch(arr1[i], arr2[j])) {
count++;
i++;
j++;
} else {
j++;
}
}
return count;
}
private boolean canMatch(int requirement, int resource) {
return resource >= requirement;
}Problem: Maximize number of content children by assigning cookies.
Greedy insight: Match smallest greed with smallest satisfying cookie.
Solution:
def findContentChildren(g: List[int], s: List[int]) -> int:
"""
Assign cookies to children to maximize satisfied children.
Args:
g: Children's greed factors
s: Cookie sizes
Returns:
Maximum number of content children
Time: O(n log n + m log m)
Space: O(1)
"""
# Sort both arrays ascending
g.sort()
s.sort()
child = cookie = 0
while child < len(g) and cookie < len(s):
# If cookie satisfies child, move to next child
if s[cookie] >= g[child]:
child += 1
# Always move to next cookie
cookie += 1
return child
# Example
print(findContentChildren([1,2,3], [1,1])) # 1
# Child with greed 1 gets cookie size 1
# Children with greed 2,3 can't be satisfied
print(findContentChildren([1,2], [1,2,3])) # 2
# Child 1 gets cookie 1, child 2 gets cookie 2Why it works:
Proof: If we give a larger cookie to a child with smaller greed, we waste resources. Matching smallest-to-smallest is optimal.
See detailed guide: Assign Cookies Greedy Explained
Problem: Minimum boats needed (each boat holds max 2 people, weight limit).
Greedy insight: Pair heaviest with lightest to minimize boats.
Solution:
def numRescueBoats(people: List[int], limit: int) -> int:
"""
Find minimum boats needed.
Args:
people: Array of people's weights
limit: Maximum weight per boat
Returns:
Minimum number of boats
Time: O(n log n)
Space: O(1)
"""
people.sort()
left, right = 0, len(people) - 1
boats = 0
while left <= right:
# Try to pair heaviest with lightest
if people[left] + people[right] <= limit:
left += 1 # Both can go in same boat
# Heaviest always goes (alone or with lightest)
right -= 1
boats += 1
return boats
# Example
print(numRescueBoats([1,2], 3)) # 1
# Both fit in one boat: 1+2=3 ≤ 3
print(numRescueBoats([3,2,2,1], 3)) # 3
# Boat 1: [1,2], Boat 2: [2], Boat 3: [3]
print(numRescueBoats([3,5,3,4], 5)) # 4
# Each person needs their own boatWhy it works:
Proof: If heaviest can't pair with lightest, they can't pair with anyone (everyone else is heavier than lightest). Greedy pairing is optimal.
See detailed guide: Greedy Two-Pointer Pattern
Problem: Send n people to city A and n people to city B, minimize total cost.
Greedy insight: Sort by difference (costA - costB), send first half to A, second half to B.
Solution:
def twoCitySchedCost(costs: List[List[int]]) -> int:
"""
Minimize cost of sending n people to each city.
Args:
costs: costs[i] = [costA, costB] for person i
Returns:
Minimum total cost
Time: O(n log n)
Space: O(1)
"""
# Sort by difference: costA - costB
# Negative difference = prefer city A
# Positive difference = prefer city B
costs.sort(key=lambda x: x[0] - x[1])
n = len(costs) // 2
total = 0
# Send first n to city A (most prefer A)
for i in range(n):
total += costs[i][0]
# Send last n to city B (most prefer B)
for i in range(n, 2 * n):
total += costs[i][1]
return total
# Example
costs = [[10,20], [30,200], [400,50], [30,20]]
print(twoCitySchedCost(costs)) # 110
# Sorted by difference:
# [10,20] diff=-10 → send to A (cost 10)
# [30,20] diff=10 → send to B (cost 20)
# [30,200] diff=-170 → send to A (cost 30)
# [400,50] diff=350 → send to B (cost 50)
# Total: 10+30+20+50 = 110Why it works:
Proof: Sending someone to their less-preferred city increases cost by |difference|. Minimizing total difference minimizes total cost.
Use ascending when:
Examples:
Assign Cookies:
g.sort() # Ascending: smallest greed first
s.sort() # Ascending: smallest cookie first
# Match smallest greed with smallest satisfying cookieBoats to Save People:
people.sort() # Ascending
# Pair smallest with largestUse descending when:
Examples:
Fractional Knapsack:
items.sort(key=lambda x: x[1]/x[0], reverse=True)
# Descending by value/weight ratio
# Take highest ratio firstMaximum Units on Truck:
boxTypes.sort(key=lambda x: x[1], reverse=True)
# Descending by units per box
# Take boxes with most units firstAssign Cookies:
g.sort() # Children's greed
s.sort() # Cookie sizes
# Both ascending, match smallest-to-smallestAdvantage Shuffle:
A.sort()
B.sort()
# Both ascending, strategic matching❌ Wrong:
# Two City Scheduling
costs.sort(key=lambda x: x[0]) # WRONG: sort by costA only✅ Correct:
costs.sort(key=lambda x: x[0] - x[1]) # Sort by differenceWhy it matters: Sorting by wrong key gives suboptimal solution.
See guide: Wrong Sorting Criterion
❌ Wrong:
# Problem asks for original indices
nums.sort() # Loses original indices!✅ Correct:
# Track indices while sorting
indexed = [(val, i) for i, val in enumerate(nums)]
indexed.sort()❌ Wrong:
# Assign Cookies
g.sort()
# Forgot to sort s!✅ Correct:
g.sort()
s.sort() # Sort both arrays❌ Wrong:
# Fractional Knapsack
items.sort(key=lambda x: x.value/x.weight) # Ascending (wrong)✅ Correct:
items.sort(key=lambda x: x.value/x.weight, reverse=True) # DescendingProblem: Fractional Knapsack
def fractionalKnapsack(values, weights, capacity):
# Sort by value/weight ratio (descending)
items = [(v/w, w, v) for v, w in zip(values, weights)]
items.sort(reverse=True)
total_value = 0
for ratio, weight, value in items:
if capacity >= weight:
total_value += value
capacity -= weight
else:
total_value += ratio * capacity
break
return total_valueProblem: Two City Scheduling
def twoCitySchedCost(costs):
# Sort by difference (costA - costB)
costs.sort(key=lambda x: x[0] - x[1])
n = len(costs) // 2
return sum(c[0] for c in costs[:n]) + sum(c[1] for c in costs[n:])Problem: Reorder Data in Log Files
def reorderLogFiles(logs):
def get_key(log):
identifier, rest = log.split(' ', 1)
if rest[0].isalpha():
# Letter log: sort by content, then identifier
return (0, rest, identifier)
else:
# Digit log: keep original order
return (1,)
return sorted(logs, key=get_key)Time Complexity:
Space Complexity:
Comparison:
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy + Sort | O(n log n) | O(1) | Matching, pairing |
| Hash Map | O(n) | O(n) | Need O(n) time |
| Brute Force | O(n²) | O(1) | Small inputs |
Master greedy with sorting:
Beginner:
Intermediate:
4. Two City Scheduling (#1029) - sort by difference
5. Advantage Shuffle (#870) - strategic matching
6. Minimum Deletions to Make Array Beautiful (#2216)
Advanced:
7. Minimum Cost to Hire K Workers (#857) - sort + heap
8. Maximize Sum of Array After K Negations (#1005)
9. Reduce Array Size to Half (#1338)
Q: When should I sort ascending vs descending?
A: Sort ascending if you want smallest first (matching, building up). Sort descending if you want largest first (greedy selection of maximum).
Q: What if I need original indices?
A: Create pairs of (value, index) before sorting, or use a different approach (hash map).
Q: Should I always sort both arrays?
A: Only if both need monotonicity for greedy decisions. If one is already sorted or doesn't need sorting, don't sort it.
Q: How do I choose the sorting key?
A: Think about what makes an element "better" for greedy selection. Sort by that criterion.
Sorting is the key that unlocks greedy solutions for matching and pairing problems.
Key principles:
The template:
arr1.sort()
arr2.sort()
i = j = 0
while i < len(arr1) and j < len(arr2):
if can_match(arr1[i], arr2[j]):
i += 1
j += 1
else:
j += 1When to use:
Master this pattern, and you'll solve greedy sorting problems with confidence. For more patterns, see the complete greedy guide, Greedy vs DP, and Wrong Sorting Criterion.
Next time you see "assign" or "match optimally," reach for greedy with sorting.
LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free