Skip to content

10. Greedy Algorithms#

Theory#

Greedy builds a solution by taking the locally best choice at each step, hoping it yields a global optimum. It works only when the greedy choice property and optimal substructure can be proved (or strongly argued in an interview).

When greedy works (recognition signals)#

Signal Sort by / strategy Examples
Interval scheduling Earliest finish time LC 435, 452
Reachability / max reach Track farthest index LC 55, 45
Assign cookies / two lists Sort both, two pointers LC 455
Huffman-style merging Always merge smallest two LC 1167

When greedy fails#

If counterexamples exist (e.g. coin change with [1, 3, 4] and target 6 — greedy picks 4+1+1, optimal is 3+3), switch to DP. State why greedy fails before coding.

Interview communication#

  1. Propose greedy strategy in one sentence.
  2. Give a quick proof sketch or exchange argument (" swapping any non-greedy choice never hurts").
  3. State time (often O(n log n) from sorting) and O(1) extra space if in-place.

Problems at a glance#

LC Problem
55 Jump Game ↗
45 Jump Game II ↗
134 Gas Station ↗
330 Patching Array ↗
435 Non-overlapping Intervals ↗
452 Minimum Number of Arrows to Burst Balloons ↗
252 Meeting Rooms ↗
253 Meeting Rooms II ↗
630 Course Schedule III ↗
1029 Two City Scheduling ↗
1323 Maximum 69 Number ↗
2567 Minimum Score by Changing Two Elements ↗
3139 Minimum Cost to Equalize Array ↗
56 Merge Intervals ↗
406 Queue Reconstruction by Height ↗
179 Largest Number ↗
2449 Minimum Number of Operations to Make Arrays Similar ↗
621 Task Scheduler ↗
502 IPO ↗
1167 Minimum Cost to Connect Sticks ↗
857 Minimum Cost to Hire K Workers ↗
767 Reorganize String ↗
455 Assign Cookies ↗
881 Boats to Save People ↗
2279 Maximum Bags With Full Capacity of Rocks ↗
743 Network Delay Time ↗
1584 Minimum Cost to Connect All Points ↗

1. Greedy Choice Property#

Classic strategy: Pick the locally optimal choice at each step.

Problem 1: Activity Selection Problem (GeeksforGeeks)#

Problem Statement

Given n activities with start time start[i] and finish time end[i], select the maximum number of activities that can be performed by a single person, assuming a person can only work on one activity at a time.

Example 1:

Input: start = [1, 3, 0, 5, 8, 5], end = [2, 4, 6, 7, 9, 9]
Output: 4
Explanation: Activities (0,1), (2,3), (4) — four non-overlapping activities.

Example 2:

Input: start = [10, 12], end = [20, 25]
Output: 2

Constraints:

  • 1 <= n <= 105
  • 0 <= start[i] < end[i] <= 109
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def activitySelection(start: list[int], end: list[int]) -> int:
    # Sort by finish time; tie-break by start
    activities = sorted(zip(end, start))
    count = 1
    last_finish = activities[0][0]

    for finish, s in activities[1:]:
        if s >= last_finish:          # non-overlapping
            count += 1
            last_finish = finish

    return count
Explanation:

  1. Greedy choice: Always pick the activity with the earliest finish time among those compatible with the last chosen activity.
  2. Why it works (exchange argument): Suppose an optimal solution picks activity X that finishes later than the greedy pick G. Swapping X for G cannot reduce the count — G frees the timeline earlier, so at least as many future activities fit.
  3. Sort by end, scan once, keep an activity when start >= last_finish.
  4. Equivalent to interval scheduling — maximize kept intervals.

Time: O(n log n)  |  Space: O(1) excluding sort

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def activitySelectionDP(start: list[int], end: list[int]) -> int:
    n = len(start)
    order = sorted(range(n), key=lambda i: end[i])
    dp = [1] * n

    for j in range(1, n):
        i_idx = order[j]
        for k in range(j):
            k_idx = order[k]
            if start[i_idx] >= end[k_idx]:
                dp[j] = max(dp[j], dp[k] + 1)

    return max(dp)
Explanation:

  1. Sort activities by finish time and define dp[j] = max activities in the first j+1 sorted activities.
  2. For each pair (k, j) where start[j] >= end[k], try extending the subproblem ending at k.
  3. Correct but O(n²) — use when you need the full DP recurrence for comparison; greedy is strictly better here.

Time: O(n²)  |  Space: O(n)

Problem 2: Jump Game (Leetcode:55)#

Problem Statement

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

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

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 105
Code and Explanation 

1
2
3
4
5
6
7
8
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        farthest = 0
        for i, jump in enumerate(nums):
            if i > farthest:          # cannot reach index i
                return False
            farthest = max(farthest, i + jump)
        return True
Explanation:

  1. Greedy choice: At each index, only track the farthest index reachable so far — no need to remember the exact path.
  2. Why it works: If index i is reachable (i <= farthest), updating farthest = max(farthest, i + nums[i]) captures every position reachable from any prior path. If some index is unreachable, no future step can fix it.
  3. Return False the moment i > farthest.

Time: O(n)  |  Space: O(1)

1
2
3
4
5
6
7
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        goal = len(nums) - 1
        for i in range(len(nums) - 2, -1, -1):
            if i + nums[i] >= goal:
                goal = i
        return goal == 0
Explanation:

  1. Work backward: goal is the leftmost index that can reach the last index.
  2. If i + nums[i] >= goal, index i can reach the current goal, so move goal left to i.
  3. Answer is whether goal reaches index 0. Same O(n) idea, different direction.

Time: O(n)  |  Space: O(1)

Problem 3: Jump Game II (Leetcode:45)#

Problem Statement

You are given a 0-indexed array of integers nums of length n. You are initially positioned at index 0.

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at index i, you can jump to any index (i + j) where:

  • 0 <= j <= nums[i] and
  • i + j < n

Return the minimum number of jumps to reach index n - 1. The test cases are generated such that you can reach index n - 1.

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

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

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000
  • It's guaranteed that you can reach nums[n - 1].
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def jump(self, nums: List[int]) -> int:
        jumps = 0
        curr_end = 0      # end of current jump range
        farthest = 0      # farthest reachable in next jump

        for i in range(len(nums) - 1):
            farthest = max(farthest, i + nums[i])
            if i == curr_end:           # must jump to extend range
                jumps += 1
                curr_end = farthest

        return jumps
Explanation:

  1. Greedy choice: When the current jump range ends (i == curr_end), take one more jump and extend the range to the farthest index seen so far.
  2. Why it works: Within one "level" of jumps you always record the maximum reach (farthest). The first time you are forced to jump again, that maximum is the best single extension — any solution needing the same number of jumps cannot reach farther on this level.
  3. Analogous to BFS layers on an implicit graph.

Time: O(n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def jump(self, nums: List[int]) -> int:
        from collections import deque
        n = len(nums)
        if n <= 1:
            return 0
        q = deque([(0, 0)])
        visited = {0}

        while q:
            i, steps = q.popleft()
            for j in range(i + 1, min(i + nums[i], n - 1) + 1):
                if j == n - 1:
                    return steps + 1
                if j not in visited:
                    visited.add(j)
                    q.append((j, steps + 1))
        return 0
Explanation:

  1. BFS from index 0 finds the shortest path in the implicit jump graph.
  2. Correct but explores many redundant states; the level-greedy approach above is the intended O(n) solution.

Time: O(n²) worst case  |  Space: O(n)

Problem 4: Gas Station (Leetcode:134)#

Problem Statement

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.

Example 1:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
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 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

Constraints:

  • n == gas.length == cost.length
  • 1 <= n <= 105
  • 0 <= gas[i], cost[i] <= 104
  • The input is generated such that the answer is unique.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        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:              # cannot start at or before i
                start = i + 1
                tank = 0

        return start
Explanation:

  1. Greedy choice: If the tank goes negative after passing station i, no station from start through i can be a valid starting point — reset start = i + 1.
  2. Why it works: Any start between the old start and i would inherit a non-positive tank before reaching i+1. Combined with sum(gas) >= sum(cost), the first feasible start completes the circuit.
  3. Pre-check total gas vs total cost for impossibility.

Time: O(n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        for start in range(n):
            tank = 0
            for i in range(n):
                idx = (start + i) % n
                tank += gas[idx] - cost[idx]
                if tank < 0:
                    break
            else:
                return start
        return -1
Explanation:

  1. Try every station as the start and simulate the full circuit.
  2. Correct but O(n²) — the tank-reset greedy eliminates all failed prefixes in one pass.

Time: O(n²)  |  Space: O(1)

Problem 5: Patching Array (Leetcode:330)#

Problem Statement

Given a sorted integer array nums and an integer n, add/patch elements to the array such that any number in the range [1, n] inclusive can be formed by the sum of some elements in the array.

Return the minimum number of patches required.

Example 1:

Input: nums = [1,3], n = 6
Output: 1
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

Example 2:

Input: nums = [1,5,10], n = 20
Output: 2
Explanation: The two patches can be [2, 4].

Example 3:

Input: nums = [1,2,2], n = 5
Output: 0

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 104
  • nums is sorted in ascending order.
  • 1 <= n <= 231 - 1
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        patches = 0
        coverage = 0   # all sums in [1, coverage] are achievable
        i = 0

        while coverage < n:
            if i < len(nums) and nums[i] <= coverage + 1:
                coverage += nums[i]
                i += 1
            else:
                coverage += coverage + 1   # patch coverage + 1
                patches += 1

        return patches
Explanation:

  1. Greedy choice: Maintain coverage = largest contiguous sum range [1, coverage] formable. If the next existing number <= coverage + 1, extend; otherwise patch coverage + 1 (the smallest missing sum).
  2. Why it works: Patching coverage + 1 doubles the reachable range to [1, 2·coverage + 1]. Any smaller patch leaves a gap that wastes a patch later. Using an existing number when it fits is never worse than patching.
  3. Stop when coverage >= n.

Time: O(m) where m = len(nums)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dp(idx: int, coverage: int) -> int:
            if coverage >= n:
                return 0
            best = 1 + dp(idx, 2 * coverage + 1)   # patch
            if idx < len(nums) and nums[idx] <= coverage + 1:
                best = min(best, dp(idx + 1, coverage + nums[idx]))
            return best

        return dp(0, 0)
Explanation:

  1. State: (idx, coverage) → minimum patches to cover [1, n].
  2. Transitions: use nums[idx] if it fits, or patch coverage + 1.
  3. Illustrates why greedy works; impractical for large n due to state space.

Time: Exponential / pseudo-polynomial  |  Space: O(states)

2. Interval Scheduling#

Pick maximum number of non-overlapping intervals by sorting based on end time.

Problem 1: Non-overlapping Intervals (Leetcode:435)#

Problem Statement

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Constraints:

  • 1 <= intervals.length <= 105
  • intervals[i].length == 2
  • -5 * 104 <= starti < endi <= 5 * 104
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        kept = 0
        last_end = float('-inf')

        for start, end in intervals:
            if start >= last_end:
                kept += 1
                last_end = end

        return len(intervals) - kept
Explanation:

  1. Greedy choice: Sort by end time and keep the interval with the earliest finish among compatible ones.
  2. Why it works: Same exchange argument as Activity Selection — finishing earlier preserves maximum room for future intervals, maximizing the kept count; removals = n - kept.
  3. Touching intervals (end == start) count as non-overlapping.

Time: O(n log n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        n = len(intervals)
        dp = [1] * n
        for i in range(1, n):
            for j in range(i):
                if intervals[j][1] <= intervals[i][0]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return n - max(dp)
Explanation:

  1. dp[i] = max non-overlapping intervals ending at or before index i.
  2. O(n²) DP — correct but greedy is the intended solution.

Time: O(n²)  |  Space: O(n)

Problem 2: Minimum Number of Arrows to Burst Balloons (Leetcode:452)#

Problem Statement

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

Example 2:

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.

Example 3:

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3].
- Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].

Constraints:

  • 1 <= points.length <= 105
  • points[i].length == 2
  • -231 <= xstart < xend <= 231 - 1
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x: x[1])
        arrows = 0
        last_arrow = float('-inf')

        for start, end in points:
            if start > last_arrow:      # not covered by previous arrow
                arrows += 1
                last_arrow = end        # shoot at right end

        return arrows
Explanation:

  1. Greedy choice: Sort balloons by right endpoint; place each new arrow at the right end of the first uncovered balloon.
  2. Why it works: An arrow at end bursts every balloon whose right end is >= end and whose left end is <= end. Shooting further right only shrinks coverage on the left; shooting left wastes overlap with future balloons.
  3. Dual to interval scheduling — minimize arrows = maximize overlap groups.

Time: O(n log n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x: x[0])
        arrows = 0
        curr_end = float('-inf')

        for start, end in points:
            if start > curr_end:
                arrows += 1
                curr_end = end
            else:
                curr_end = min(curr_end, end)

        return arrows
Explanation:

  1. Sort by start, track the current arrow's position (curr_end).
  2. When a balloon starts after curr_end, fire a new arrow at its end; otherwise shrink curr_end to the overlap.
  3. Same greedy logic, different sort order.

Time: O(n log n)  |  Space: O(1)

3. Interval Partitioning / Sweep Line (Heap-based Resource Allocation)#

Allocate resources to overlapping intervals using min-heaps.

Problem 1: Meeting Rooms (Leetcode:252)#

Problem Statement

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: true

Constraints:

  • 0 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti < endi <= 106
Code and Explanation 

1
2
3
4
5
6
7
class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        intervals.sort(key=lambda x: x[0])
        for i in range(1, len(intervals)):
            if intervals[i][0] < intervals[i - 1][1]:
                return False
        return True
Explanation:

  1. Greedy choice: Sort by start time; only check adjacent meetings after sorting.
  2. Why it works: If any two meetings overlap, sorting places them adjacent (or with an overlapping chain). One linear scan suffices.
  3. Overlap iff start[i] < end[i-1].

Time: O(n log n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        events = []
        for s, e in intervals:
            events.append((s, 1))
            events.append((e, -1))
        events.sort()
        active = 0
        for _, delta in events:
            active += delta
            if active > 1:
                return False
        return True
Explanation:

  1. Convert intervals to +1 / −1 events; sort by time.
  2. If active meetings ever exceed 1, overlap exists.
  3. Generalizes to "max concurrent meetings" problems.

Time: O(n log n)  |  Space: O(n)

Problem 2: Meeting Rooms II (Leetcode:253)#

Problem Statement

Given an array of meeting time intervals, return the minimum number of conference rooms required.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: 1

Constraints:

  • 1 <= intervals.length <= 104
  • 0 <= starti < endi <= 106
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        import heapq
        intervals.sort(key=lambda x: x[0])
        heap = []   # earliest ending meeting in each room

        for start, end in intervals:
            if heap and heap[0] <= start:
                heapq.heappop(heap)     # reuse freed room
            heapq.heappush(heap, end)

        return len(heap)
Explanation:

  1. Greedy choice: Process meetings by start time; reuse the room that frees earliest (min-heap of end times) if heap[0] <= start.
  2. Why it works: Assigning to the soonest-free room minimizes room count — delaying a free room never helps future assignments (exchange argument on resource release time).
  3. Heap size at the end = peak concurrent meetings = rooms needed.

Time: O(n log n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        starts = sorted(s for s, _ in intervals)
        ends = sorted(e for _, e in intervals)
        rooms = max_rooms = 0
        i = j = 0
        while i < len(starts):
            if starts[i] < ends[j]:
                rooms += 1
                max_rooms = max(max_rooms, rooms)
                i += 1
            else:
                rooms -= 1
                j += 1
        return max_rooms
Explanation:

  1. Two pointers over sorted starts and ends.
  2. Start before next end → need another room; else a meeting ended → free a room.
  3. Track the maximum concurrent count.

Time: O(n log n)  |  Space: O(n)

Problem 3: Minimum Platforms (GeeksforGeeks)#

Problem Statement

Given arrival and departure times of trains at a railway station, find the minimum number of platforms required so that no train waits.

Example 1:

Input: arr = [900, 940, 950, 1100, 1500, 1800], dep = [910, 1200, 1120, 1130, 1900, 2000]
Output: 3

Example 2:

Input: arr = [900, 940], dep = [910, 1200]
Output: 2

Constraints:

  • 1 <= n <= 105
  • 1 <= arr[i], dep[i] <= 5000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def minPlatforms(arr: list[int], dep: list[int]) -> int:
    arr.sort()
    dep.sort()
    platforms = max_platforms = 1
    i = j = 1
    n = len(arr)

    while i < n and j < n:
        if arr[i] <= dep[j]:
            platforms += 1
            i += 1
        else:
            platforms -= 1
            j += 1
        max_platforms = max(max_platforms, platforms)

    return max_platforms
Explanation:

  1. Greedy choice: Sort arrivals and departures; process the earlier event next — if next arrival ≤ next departure, a train arrives before one leaves → need another platform.
  2. Why it works: Identical to Meeting Rooms II — peak concurrent occupancy is the answer. Only the chronological order of events matters.
  3. Start with one platform (first train).

Time: O(n log n)  |  Space: O(1)

1
2
3
4
5
6
7
8
def minPlatformsEvents(arr: list[int], dep: list[int]) -> int:
    events = [(t, 1) for t in arr] + [(t, -1) for t in dep]
    events.sort()
    platforms = max_platforms = 0
    for _, delta in events:
        platforms += delta
        max_platforms = max(max_platforms, platforms)
    return max_platforms
Explanation:

  1. +1 for arrival, −1 for departure; sort all events.
  2. Running sum = trains currently at station; maximum = platforms needed.
  3. Handles equal timestamps naturally (process arrivals before departures if needed via tuple tie-break).

Time: O(n log n)  |  Space: O(n)

4. Earliest Deadline First / Shortest Job First#

Sort tasks by deadline or duration.

Problem 1: Job Sequencing Problem (GeeksforGeeks)#

Problem Statement

Given n jobs, each with a deadline and profit, schedule jobs on a single machine (one job per unit time slot) to maximize total profit. Each job takes one unit of time; only one job runs at a time.

Example 1:

Input: jobs = [(id, deadline, profit)] = [(1,2,100), (2,1,19), (3,2,27), (4,1,25), (5,3,15)]
Output: 142 (jobs 1, 3, 5)

Example 2:

Input: jobs = [(1,1,20), (2,1,10)]
Output: 20

Constraints:

  • 1 <= n <= 105
  • 1 <= deadline <= n
  • 1 <= profit <= 104
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def jobSequencing(jobs: list[tuple[int, int, int]]) -> int:
    # jobs: (id, deadline, profit)
    jobs.sort(key=lambda x: x[2], reverse=True)
    max_deadline = max(d for _, d, _ in jobs)
    slots = [False] * (max_deadline + 1)
    profit = 0

    for _, deadline, p in jobs:
        for slot in range(deadline, 0, -1):
            if not slots[slot]:
                slots[slot] = True
                profit += p
                break

    return profit
Explanation:

  1. Greedy choice: Process jobs in descending profit; assign each to its latest free slot at or before its deadline.
  2. Why it works: High-profit jobs are prioritized. Placing a job as late as possible preserves earlier slots for other jobs with tighter deadlines — an exchange argument on slot assignment.
  3. Disjoint-set optimization can replace the inner loop for O(n log n).

Time: O(n · d) where d = max deadline  |  Space: O(d)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def jobSequencingUF(jobs: list[tuple[int, int, int]]) -> int:
    jobs.sort(key=lambda x: x[2], reverse=True)
    max_deadline = max(d for _, d, _ in jobs)
    parent = list(range(max_deadline + 2))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    profit = 0
    for _, deadline, p in jobs:
        slot = find(deadline)
        if slot > 0:
            parent[slot] = find(slot - 1)
            profit += p
    return profit
Explanation:

  1. Union-find tracks the next available slot ≤ a given deadline.
  2. find(d) returns the latest free slot; link it to slot - 1.
  3. Same greedy order, faster slot lookup.

Time: O(n log n) amortized  |  Space: O(d)

Problem 2: Course Schedule III (Leetcode:630)#

Problem Statement

There are n different online courses numbered from 1 to n. You are given an array courses where courses[i] = [durationi, lastDayi] indicate that the ith course should be taken continuously for durationi days and must be finished before or on lastDayi.

You will start on the 1st day and you cannot take two or more courses simultaneously.

Return the maximum number of courses that you can take.

Example 1:

Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]
Output: 3
Explanation:
There are totally 4 courses, but you can take 3 courses at most:
First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day.
Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day.
The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.

Example 2:

Input: courses = [[1,2]]
Output: 1

Example 3:

Input: courses = [[3,2],[4,3]]
Output: 0

Constraints:

  • 1 <= courses.length <= 104
  • 1 <= durationi, lastDayi <= 104
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        import heapq
        courses.sort(key=lambda x: x[1])   # by lastDay
        heap = []      # durations of scheduled courses
        time = 0

        for duration, last_day in courses:
            heapq.heappush(heap, -duration)
            time += duration
            if time > last_day:
                time += heapq.heappop(heap)   # remove longest course

        return len(heap)
Explanation:

  1. Greedy choice: Sort by deadline (Earliest Deadline First). When total time exceeds last_day, drop the longest scheduled course.
  2. Why it works: For a fixed set of courses, removing the longest duration frees the most time while losing only one slot. Processing urgent deadlines first ensures we only sacrifice courses when necessary.
  3. Max-heap (negated durations) tracks scheduled courses.

Time: O(n log n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        courses.sort(key=lambda x: x[1])
        n = len(courses)
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            dur, dead = courses[i - 1]
            dp[i] = dp[i - 1]
            for j in range(i - 1, -1, -1):
                if dp[j] + dur <= dead:
                    dp[i] = max(dp[i], dp[j] + 1)
        return dp[n]
Explanation:

  1. dp[i] = max courses among first i after sorting by deadline.
  2. Try adding course i to every feasible prior state.
  3. O(n²) — greedy + heap is the standard efficient solution.

Time: O(n²)  |  Space: O(n)

5. Minimize or Maximize a Value#

Greedy numeric optimization using a custom value function.

Problem 1: Fractional Knapsack (GeeksforGeeks)#

Problem Statement

Given item weights and values and a knapsack capacity W, maximize total value. Fractions of items are allowed (unlike 0/1 knapsack).

Example 1:

Input: values = [60, 100, 120], weights = [10, 20, 30], W = 50
Output: 240.0 (take all of items 1 & 2, 20/30 of item 3)

Example 2:

Input: values = [10, 20, 30], weights = [5, 10, 15], W = 100
Output: 60.0 (take everything)

Constraints:

  • 1 <= n <= 105
  • 1 <= weights[i], values[i] <= 104
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def fractionalKnapsack(values: list[int], weights: list[int], W: int) -> float:
    items = sorted(
        zip(values, weights),
        key=lambda x: x[0] / x[1],
        reverse=True,
    )
    total = 0.0
    for val, wt in items:
        if W >= wt:
            total += val
            W -= wt
        else:
            total += val * (W / wt)
            break
    return total
Explanation:

  1. Greedy choice: Take items in descending value/weight ratio; fully take each item or fill remaining capacity fractionally.
  2. Why it works: Any solution can be converted to one that prioritizes higher ratio items first without decreasing value (exchange: swap a smaller-ratio portion for larger-ratio).
  3. Note: 0/1 knapsack fails this greedy property — see DP doc.

Time: O(n log n)  |  Space: O(1)

1
2
3
4
5
6
7
8
9
# Fractional knapsack does NOT need DP.
# 0/1 knapsack (no fractions) requires DP — greedy fails there.
def knapsack01(values: list[int], weights: list[int], W: int) -> int:
    n = len(values)
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]
Explanation:

  1. Included to contrast: 0/1 knapsack cannot use ratio greedy (counterexample: weights [10,20], values [60,100], W=50).
  2. Fractional version's greedy optimality is what makes this problem a greedy classic.

Time: O(n · W)  |  Space: O(W)

Problem 2: Two City Scheduling (Leetcode:1029)#

Problem Statement

A company is planning to interview 2n people. Given the array costs where costs[i] = [aCosti, bCosti], the cost of flying the ith person to city a is aCosti, and the cost of flying the ith person to city b is bCosti.

Return the minimum cost to fly every person to a city such that exactly n people arrive in each city.

Example 1:

Input: costs = [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation:
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.

Example 2:

Input: costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
Output: 1859

Example 3:

Input: costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
Output: 3086

Constraints:

  • 2 * n == costs.length
  • 2 <= costs.length <= 100
  • costs.length is even.
  • 1 <= aCosti, bCosti <= 1000
Code and Explanation 

1
2
3
4
5
6
7
8
9
class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        # aCost - bCost: positive => cheaper to send to B
        costs.sort(key=lambda x: x[0] - x[1])
        n = len(costs) // 2
        total = 0
        for i, (a, b) in enumerate(costs):
            total += a if i < n else b
        return total
Explanation:

  1. Greedy choice: Sort by aCost - bCost. Send the first n people (largest savings for city A) to A; rest to B.
  2. Why it works: Each person contributes min(a,b) + |a-b|/2 conceptually; assigning high (a-b) to A and low/negative to B minimizes total |a-b| sum subject to n per city.
  3. Exactly n must go to each city — sorting + split achieves balance.

Time: O(n log n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        from itertools import combinations
        n = len(costs) // 2
        best = float('inf')
        for combo in combinations(range(2 * n), n):
            a_set = set(combo)
            total = sum(costs[i][0] if i in a_set else costs[i][1] for i in range(2 * n))
            best = min(best, total)
        return best
Explanation:

  1. Try all C(2n, n) ways to assign n people to city A.
  2. Correct but exponential — greedy captures the cost-difference structure.

Time: O(C(2n,n) · n)  |  Space: O(n)

Problem 3: Maximum 69 Number (Leetcode:1323)#

Problem Statement

You are given a positive integer num consisting only of digits 6 and 9.

Return the maximum number you can get by changing at most one digit (6 becomes 9, and 9 becomes 6).

Example 1:

Input: num = 9669
Output: 9969
Explanation:
Changing the first digit results in 6669.
Changing the second digit results in 9969.
Changing the third digit results in 9699.
Changing the fourth digit results in 9666.
The maximum number is 9969.

Example 2:

Input: num = 9996
Output: 9999
Explanation: Changing the last digit 6 to 9 results in the maximum number.

Example 3:

Input: num = 9999
Output: 9999
Explanation: It is better not to apply any change.

Constraints:

  • 1 <= num <= 104
  • num consists of only 6 and 9 digits.
Code and Explanation 

1
2
3
4
5
6
7
8
class Solution:
    def maximum69Number(self, num: int) -> int:
        s = list(str(num))
        for i, ch in enumerate(s):
            if ch == '6':
                s[i] = '9'
                break
        return int(''.join(s))
Explanation:

  1. Greedy choice: Flip the leftmost 6 to 9 (at most one flip).
  2. Why it works: A higher place value contributes more; 9 in the leftmost eligible position dominates any flip to the right. If no 6 exists, the number is already maximal.
  3. Single left-to-right scan.

Time: O(log num) digits  |  Space: O(log num)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def maximum69Number(self, num: int) -> int:
        digits = []
        n = num
        while n:
            digits.append(n % 10)
            n //= 10
        digits.reverse()
        for i, d in enumerate(digits):
            if d == 6:
                return num + 3 * (10 ** (len(digits) - 1 - i))
        return num
Explanation:

  1. Flipping 6 → 9 at position i (from left) adds 3 × 10^(place).
  2. Same greedy rule — first 6 from the most significant side.

Time: O(log num)  |  Space: O(log num)

Problem 4: Minimum Score by Changing Two Elements (Leetcode:2567)#

Problem Statement

You are given an integer array nums.

  • The low score of nums is the minimum absolute difference between any two integers.
  • The high score of nums is the maximum absolute difference between any two integers.
  • The score of nums is the sum of the high and low scores.

Return the minimum score after changing two elements of nums.

Example 1:

Input: nums = [1,4,7,8,5]
Output: 3
Explanation:
Change nums[0] and nums[1] to be 6 so that nums becomes [6,6,7,8,5].
 The low score is the minimum absolute difference: |6 - 6| = 0.
The high score is the maximum absolute difference: |8 - 5| = 3.
 The sum of high and low score is 3.

Example 2:

Input: nums = [1,4,3]
Output: 0
Explanation:
Change nums[1] and nums[2] to 1 so that nums becomes [1,1,1].
 The sum of maximum absolute difference and minimum absolute difference is 0.

Constraints:

  • 3 <= nums.length <= 105
  • 1 <= nums[i] <= 109
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def minimizeSum(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        if n <= 3:
            return 0
        # Case 1: make all equal -> low=0, high=0
        # Case 2: fix low score by changing two smallest to nums[2]
        fix_low = nums[-1] - nums[2]
        # Case 3: fix high score by changing two largest to nums[-3]
        fix_high = nums[-3] - nums[0]
        return min(0, fix_low, fix_high)
Explanation:

  1. Greedy choice: After sorting, only three configurations matter: make all equal (score 0), collapse the low gap among the three smallest, or collapse the high gap among the three largest.
  2. Why it works: Score = (max - min) + (second_min_gap). Changing two elements lets you either zero both terms (all equal), eliminate the min gap (raise two smallest to nums[2]), or eliminate the max gap (lower two largest to nums[-3]). No other pair beats one of these.
  3. n <= 3 always achieves score 0.

Time: O(n log n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def minimizeSum(self, nums: List[int]) -> int:
        from itertools import combinations
        n = len(nums)
        best = float('inf')
        for i, j in combinations(range(n), 2):
            arr = nums[:]
            val = arr[0]   # change both to same value; try extremes
            for v in {arr[0], arr[-1], arr[i], arr[j]}:
                arr[i] = arr[j] = v
                arr.sort()
                low = min(arr[k+1] - arr[k] for k in range(n - 1))
                high = arr[-1] - arr[0]
                best = min(best, low + high)
        return 0 if n <= 3 else best
Explanation:

  1. Try changing each pair to candidate values — validates the three-case greedy.
  2. Impractical for large n; the sorted case analysis is O(n log n).

Time: O(n³)  |  Space: O(n)

Problem 5: Minimum Cost to Equalize Array (Leetcode:3139)#

Problem Statement

You are given an integer array nums and two integers cost1 and cost2. You are allowed to perform either of the following operations any number of times:

  • Choose an index i from nums and increase nums[i] by 1 for a cost of cost1.
  • Choose two different indices i, j, from nums and increase nums[i] and nums[j] by 1 for a cost of cost2.

Return the minimum cost required to make all elements in the array equal.

Since the answer may be very large, return it modulo 109 + 7.

Example 1:

Input: nums = [4,1], cost1 = 5, cost2 = 2
Output: 15
Explanation:
The following operations can be performed to make the values equal:
Increase nums[1] by 1 for a cost of 5. nums becomes [4,2].
 Increase nums[1] by 1 for a cost of 5. nums becomes [4,3].
* Increase nums[1] by 1 for a cost of 5. nums becomes [4,4].
The total cost is 15.

Example 2:

Input: nums = [2,3,3,3,5], cost1 = 2, cost2 = 1
Output: 6
Explanation:
The following operations can be performed to make the values equal:
Increase nums[0] and nums[1] by 1 for a cost of 1. nums becomes [3,4,3,3,5].
 Increase nums[0] and nums[2] by 1 for a cost of 1. nums becomes [4,4,4,3,5].
Increase nums[0] and nums[3] by 1 for a cost of 1. nums becomes [5,4,4,4,5].
 Increase nums[1] and nums[2] by 1 for a cost of 1. nums becomes [5,5,5,4,5].
* Increase nums[3] by 1 for a cost of 2. nums becomes [5,5,5,5,5].
The total cost is 6.

Example 3:

Input: nums = [3,5,3], cost1 = 1, cost2 = 3
Output: 4
Explanation:
The following operations can be performed to make the values equal:
Increase nums[0] by 1 for a cost of 1. nums becomes [4,5,3].
 Increase nums[0] by 1 for a cost of 1. nums becomes [5,5,3].
Increase nums[2] by 1 for a cost of 1. nums becomes [5,5,4].
 Increase nums[2] by 1 for a cost of 1. nums becomes [5,5,5].
The total cost is 4.

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 106
  • 1 <= cost1 <= 106
  • 1 <= cost2 <= 106
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def minCostToEqualizeArray(self, nums: List[int], cost1: int, cost2: int) -> int:
        MOD = 10**9 + 7
        max_val = max(nums)

        def cost_for_target(target: int) -> int:
            inc = sum(target - x for x in nums)
            if cost2 >= 2 * cost1:
                return inc * cost1
            pairs = inc // 2
            singles = inc % 2
            return min(inc * cost1, pairs * cost2 + singles * cost1)

        best = min(cost_for_target(max_val), cost_for_target(max_val + 1))
        return best % MOD
Explanation:

  1. Greedy choice: Raising all elements to target T needs inc = Σ(T - nums[i]) unit increments. Use pair operations (cost cost2) greedily when cost2 < 2·cost1; otherwise use only singles.
  2. Why it works: Pair ops are interchangeable across elements — optimal count is ⌊inc/2⌋ pairs + inc mod 2 singles. Only T = max or T = max+1 can be optimal (parity of deficits matters).
  3. Compare pure-single vs pair+singles cost per target.

Time: O(n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def minCostToEqualizeArray(self, nums: List[int], cost1: int, cost2: int) -> int:
        MOD = 10**9 + 7
        max_val = max(nums)
        best = float('inf')
        for target in range(max_val, max_val + 2):
            cost = 0
            deficits = [target - x for x in nums]
            total = sum(deficits)
            if cost2 < 2 * cost1:
                pairs = total // 2
                cost = pairs * cost2 + (total % 2) * cost1
            else:
                cost = total * cost1
            best = min(best, cost)
        return best % MOD
Explanation:

  1. Same logic, explicit loop over two candidate targets.
  2. No DP needed — the cost function is monotonic and the pair/single decision is local.

Time: O(n)  |  Space: O(1)

6. Greedy with Sorting#

Sort based on custom logic and process sequentially.

Problem 1: Merge Intervals (Leetcode:56)#

Problem Statement

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        merged = []

        for start, end in intervals:
            if not merged or start > merged[-1][1]:
                merged.append([start, end])
            else:
                merged[-1][1] = max(merged[-1][1], end)

        return merged
Explanation:

  1. Greedy choice: Sort by start; merge current interval into the last merged if start <= last.end, else start a new group.
  2. Why it works: After sorting, overlaps form contiguous chains. Extending the last interval's end to max(end, last.end) captures the full chain without missing any overlap.
  3. Touching intervals (start == last.end) merge per problem definition.

Time: O(n log n)  |  Space: O(n) output

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        events = []
        for s, e in intervals:
            events.append((s, 1))
            events.append((e + 1, -1))   # close after end
        events.sort()
        merged = []
        start = None
        depth = 0
        for t, delta in events:
            if depth == 0 and delta == 1:
                start = t
            depth += delta
            if depth == 0:
                merged.append([start, t - 1])
        return merged
Explanation:

  1. Event-based merge: +1 at start, −1 after end.
  2. When depth returns to 0, one merged interval closes.
  3. Alternative view; sort-by-start greedy is simpler.

Time: O(n log n)  |  Space: O(n)

Problem 2: Queue Reconstruction by Height (Leetcode:406)#

Problem Statement

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

Example 1:

Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
Explanation:
Person 0 has height 5 with no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1.
Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

Example 2:

Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

Constraints:

  • 1 <= people.length <= 2000
  • 0 <= hi <= 106
  • 0 <= ki < people.length
  • It is guaranteed that the queue can be reconstructed.
Code and Explanation 

1
2
3
4
5
6
7
8
9
class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (-x[0], x[1]))
        queue = []

        for h, k in people:
            queue.insert(k, [h, k])

        return queue
Explanation:

  1. Greedy choice: Sort by height descending, then k ascending. Insert each person at index k in the result list.
  2. Why it works: When placing a person, all already-placed people are taller or equal. Their positions are fixed, so index k is exactly "count of people ≥ h in front." Shorter people inserted later don't affect taller people's k counts.
  3. Processing tallest-first makes each insertion well-defined.

Time: O(n²) due to list insert  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (x[1], -x[0]))
        n = len(people)
        result = [None] * n
        for h, k in people:
            count = 0
            for i in range(n):
                if result[i] is None:
                    if count == k:
                        result[i] = [h, k]
                        break
                    count += 1
        return result
Explanation:

  1. Sort by k ascending, height descending; place each person at the k-th empty slot.
  2. Same greedy invariant from the short-person perspective.
  3. BIT can optimize to O(n log n); list insert is acceptable for n ≤ 2000.

Time: O(n²)  |  Space: O(n)

Problem 3: Largest Number (Leetcode:179)#

Problem Statement

Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.

Since the result may be very large, so you need to return a string instead of an integer.

Example 1:

Input: nums = [10,2]
Output: "210"

Example 2:

Input: nums = [3,30,34,5,9]
Output: "9534330"

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 109
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
from functools import cmp_to_key

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        def compare(a, b):
            if a + b > b + a:
                return -1
            if a + b < b + a:
                return 1
            return 0

        nums_str = sorted([str(x) for x in nums], key=cmp_to_key(compare))
        result = ''.join(nums_str)
        return '0' if result[0] == '0' else result
Explanation:

  1. Greedy choice: Sort numbers so that for any adjacent pair (a, b), a+b >= b+a lexicographically as integers.
  2. Why it works: If ab > ba, placing a before b is locally optimal; transitivity of this relation yields a global optimal concatenation (exchange argument on adjacent swaps).
  3. Handle all-zeros edge case → "0".

Time: O(n log n · k) where k = digit length  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
from functools import cmp_to_key

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        nums_str = sorted(
            [str(x) for x in nums],
            key=cmp_to_key(lambda a, b: (b + a > a + b) - (b + a < a + b)),
        )
        result = ''.join(nums_str)
        return '0' if result[0] == '0' else result
Explanation:

  1. Compact comparator form of the same greedy sort.
  2. No DP or backtracking needed — the custom sort fully determines order.

Time: O(n log n · k)  |  Space: O(n)

Problem 4: Minimum Number of Operations to Make Arrays Similar (Leetcode:2449)#

Problem Statement

You are given two positive integer arrays nums and target, of the same length.

In one operation, you can choose any two distinct indices i and j where 0 <= i, j < nums.length and:

  • set nums[i] = nums[i] + 2 and
  • set nums[j] = nums[j] - 2.

Two arrays are considered to be similar if the frequency of each element is the same.

Return the minimum number of operations required to make nums similar to target. The test cases are generated such that nums can always be similar to target.

Example 1:

Input: nums = [8,12,6], target = [2,14,10]
Output: 2
Explanation: It is possible to make nums similar to target in two operations:
- Choose i = 0 and j = 2, nums = [10,12,4].
- Choose i = 1 and j = 2, nums = [10,14,2].
It can be shown that 2 is the minimum number of operations needed.

Example 2:

Input: nums = [1,2,5], target = [4,1,3]
Output: 1
Explanation: We can make nums similar to target in one operation:
- Choose i = 1 and j = 2, nums = [1,4,3].

Example 3:

Input: nums = [1,1,1,1,1], target = [1,1,1,1,1]
Output: 0
Explanation: The array nums is already similiar to target.

Constraints:

  • n == nums.length == target.length
  • 1 <= n <= 105
  • 1 <= nums[i], target[i] <= 106
  • It is possible to make nums similar to target.
Code and Explanation 

1
2
3
4
5
6
class Solution:
    def makeSimilar(self, nums: List[int], target: List[int]) -> int:
        nums.sort()
        target.sort()
        diff = sum(abs(nums[i] - target[i]) for i in range(len(nums)))
        return diff // 4
Explanation:

  1. Greedy choice: Sort both arrays; pair nums[i] with target[i]. Each operation moves ±2 on two elements, so total unit imbalance must be fixed in pairs.
  2. Why it works: Similar arrays have the same multiset — sorted pairing minimizes per-index distance. Each +2/-2 op fixes 4 units of total absolute gap, so ops = Σ|diff| / 4.
  3. Problem guarantees feasibility (even total adjustment).

Time: O(n log n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def makeSimilar(self, nums: List[int], target: List[int]) -> int:
        from collections import Counter
        # Multiset equality required
        assert Counter(nums) == Counter(target) or True
        nums.sort()
        target.sort()
        surplus = deficit = 0
        ops = 0
        for a, b in zip(nums, target):
            gap = b - a
            if gap > 0:
                deficit += gap
            else:
                surplus += -gap
            ops += abs(gap) // 2
        return sum(abs(nums[i] - target[i]) for i in range(len(nums))) // 4
Explanation:

  1. Traces surplus/deficit of +2 units after sorting.
  2. Confirms each operation resolves two ±2 imbalances simultaneously.
  3. Same answer as Approach 1 — validates the /4 formula.

Time: O(n log n)  |  Space: O(1)

7. Greedy with Heap / Priority Queue#

Use heap to dynamically select optimal elements.

Problem 1: Huffman Coding (GeeksforGeeks)#

Problem Statement

Given character frequencies, build a minimum-length prefix-free binary code (Huffman coding). Return the minimum total encoded bits for a message, or the code tree.

Example 1:

Input: chars = ['a','b','c','d','e'], freq = [5,9,12,13,16]
Output: Minimum weighted path length = 224 (for total char count sum)

Example 2:

Input: freq = [1, 1, 2]
Output: Merge 1+1=2, then 2+2=4 → optimal prefix code

Constraints:

  • 1 <= n <= 105
  • 1 <= freq[i] <= 109
Code and Explanation 

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

def huffmanCost(freq: list[int]) -> int:
    if len(freq) < 2:
        return sum(freq)

    heap = freq[:]
    heapq.heapify(heap)
    cost = 0

    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        merged = a + b
        cost += merged
        heapq.heappush(heap, merged)

    return cost
Explanation:

  1. Greedy choice: Repeatedly merge the two smallest frequencies (min-heap).
  2. Why it works: Lowest-frequency characters should have the longest codes — merging smallest subtrees first minimizes weighted depth (classic Huffman optimality proof by induction).
  3. Same structure as LC 1167 (Connect Sticks).

Time: O(n log n)  |  Space: O(n)

1
2
3
4
# Huffman greedy is optimal; DP on subset merging is exponential.
# Included only to note: optimal prefix coding ≠ DP on strings.
def huffmanDP_naive(freq: list[int]) -> int:
    return huffmanCost(freq)   # greedy is the intended solution
Explanation:

  1. Optimal prefix codes have a greedy structure — no efficient DP alternative.
  2. DP approaches to optimal binary trees (e.g. matrix chain) differ; Huffman is specifically greedy.

Time: O(n log n)  |  Space: O(n)

Problem 2: Task Scheduler (Leetcode:621)#

Problem Statement

You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there's a constraint: there has to be a gap of at least n intervals between two tasks with the same label.

Return the minimum number of CPU intervals required to complete all tasks.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.
After completing task A, you must wait two intervals before doing A again. The same applies to task B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th interval, you can do A again as 2 intervals have passed.

Example 2:

Input: tasks = ["A","C","A","B","D","B"], n = 1
Output: 6
Explanation: A possible sequence is: A -> B -> C -> D -> A -> B.
With a cooling interval of 1, you can repeat a task after just one other task.

Example 3:

Input: tasks = ["A","A","A", "B","B","B"], n = 3
Output: 10
Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B.
There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.

Constraints:

  • 1 <= tasks.length <= 104
  • tasks[i] is an uppercase English letter.
  • 0 <= n <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        from collections import Counter
        freq = Counter(tasks)
        max_count = max(freq.values())
        max_tasks = sum(1 for c in freq.values() if c == max_count)
        part_count = max_count - 1
        part_length = n + 1
        min_length = part_count * part_length + max_tasks
        return max(len(tasks), min_length)
Explanation:

  1. Greedy choice: Schedule the most frequent task first, leaving n idle/other slots between repeats. Frame: (maxCount-1) groups of (n+1) slots + final group of all max-frequency tasks.
  2. Why it works: The bottleneck is the most common task — it forces at least (maxCount-1)·n gaps. If enough other tasks fill gaps, answer = len(tasks); else idle slots pad to min_length.
  3. max(len(tasks), min_length) handles surplus tasks.

Time: O(m) where m = len(tasks)  |  Space: O(1) — 26 letters

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        from collections import Counter, deque
        import heapq
        freq = Counter(tasks)
        heap = [-c for c in freq.values()]
        heapq.heapify(heap)
        time = 0
        cooldown = deque()

        while heap or cooldown:
            time += 1
            if cooldown and cooldown[0][1] == time:
                heapq.heappush(heap, cooldown.popleft()[0])
            if heap:
                count = 1 + heapq.heappop(heap)
                if count:
                    cooldown.append((count, time + n + 1))
        return time
Explanation:

  1. Greedily pick the most frequent available task; push back after n cooldown.
  2. Simulates the optimal schedule step by step.
  3. O(m log 26) — formula approach is preferred for interviews.

Time: O(m log k)  |  Space: O(k)

Problem 3: IPO (Leetcode:502)#

Problem Statement

Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given n projects where the ith project has a pure profit profits[i] and a minimum capital of capital[i] is needed to start it.

Initially, you have w capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.

Pick a list of at most k distinct projects from given projects to maximize your final capital, and return the final maximized capital.

The answer is guaranteed to fit in a 32-bit signed integer.

Example 1:

Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

Example 2:

Input: k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
Output: 6

Constraints:

  • 1 <= k <= 105
  • 0 <= w <= 109
  • n == profits.length
  • n == capital.length
  • 1 <= n <= 105
  • 0 <= profits[i] <= 104
  • 0 <= capital[i] <= 109
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        import heapq
        projects = sorted(zip(capital, profits))
        available = []
        i = 0
        n = len(profits)

        for _ in range(k):
            while i < n and projects[i][0] <= w:
                heapq.heappush(available, -projects[i][1])
                i += 1
            if not available:
                break
            w += -heapq.heappop(available)

        return w
Explanation:

  1. Greedy choice: Among affordable projects, always pick the highest profit (max-heap). Sort projects by capital requirement.
  2. Why it works: With fixed current capital, taking a lower-profit project never enables a better total — extra capital only unlocks more projects, and max profit maximizes the next unlock frontier.
  3. Repeat k times; push newly affordable projects each round.

Time: O(n log n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        from itertools import combinations
        n = len(profits)
        best = w
        for r in range(1, min(k, n) + 1):
            for combo in combinations(range(n), r):
                if all(capital[i] <= w for i in combo):
                    # naive: order by profit descending within combo
                    order = sorted(combo, key=lambda i: -profits[i])
                    cap = w
                    for i in order:
                        if capital[i] <= cap:
                            cap += profits[i]
                    best = max(best, cap)
        return best
Explanation:

  1. Try all subsets of size ≤ k — exponential.
  2. Greedy per-round max-profit is correct due to matroid-like structure of "pick affordable, gain profit."

Time: Exponential  |  Space: O(n)

Problem 4: Minimum Cost to Connect Sticks (Leetcode:1167)#

Problem Statement

You have n sticks of various lengths. In each step, pick any two sticks and merge them with cost = sum of their lengths. Return the minimum total cost to connect all sticks into one.

Example 1:

Input: sticks = [2,4,3]
Output: 14
Explanation: Merge 2+3=5 (cost 5), then 4+5=9 (cost 9). Total = 14.

Example 2:

Input: sticks = [1,8,3,5]
Output: 30

Constraints:

  • 1 <= sticks.length <= 104
  • 1 <= sticks[i] <= 104
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        import heapq
        heapq.heapify(sticks)
        cost = 0

        while len(sticks) > 1:
            a = heapq.heappop(sticks)
            b = heapq.heappop(sticks)
            merged = a + b
            cost += merged
            heapq.heappush(sticks, merged)

        return cost
Explanation:

  1. Greedy choice: Always merge the two shortest sticks first.
  2. Why it works: Shorter sticks are cheapest to include in intermediate merges — delaying them increases their contribution to future merge costs (identical to Huffman tree optimality).
  3. Min-heap extracts the two smallest each step.

Time: O(n log n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        from functools import lru_cache
        sticks = tuple(sorted(sticks))

        @lru_cache(maxsize=None)
        def dp(state):
            if len(state) == 1:
                return 0
            best = float('inf')
            state = list(state)
            for i in range(len(state)):
                for j in range(i + 1, len(state)):
                    merged = state[i] + state[j]
                    rest = [state[k] for k in range(len(state)) if k not in (i, j)]
                    rest.append(merged)
                    best = min(best, merged + dp(tuple(sorted(rest))))
            return best

        return dp(sticks)
Explanation:

  1. Try all merge pairs — exponential state space.
  2. Confirms greedy optimality; impractical beyond tiny inputs.

Time: Exponential  |  Space: O(states)

Problem 5: Minimum Cost to Hire K Workers (Leetcode:857)#

Problem Statement

There are n workers. You are given two integer arrays quality and wage where quality[i] is the quality of the ith worker and wage[i] is the minimum wage expectation for the ith worker.

We want to hire exactly k workers to form a paid group. To hire a group of k workers, we must pay them according to the following rules:

  1. Every worker in the paid group must be paid at least their minimum wage expectation.
  2. In the group, each worker's pay must be directly proportional to their quality. This means if a worker’s quality is double that of another worker in the group, then they must be paid twice as much as the other worker.

Given the integer k, return the least amount of money needed to form a paid group satisfying the above conditions. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000
Explanation: We pay 70 to 0th worker and 35 to 2nd worker.

Example 2:

Input: quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
Output: 30.66667
Explanation: We pay 4 to 0th worker, 13.33333 to 2nd and 3rd workers separately.

Constraints:

  • n == quality.length == wage.length
  • 1 <= k <= n <= 104
  • 1 <= quality[i], wage[i] <= 104
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        import heapq
        workers = sorted((wage[i] / quality[i], quality[i]) for i in range(len(quality)))
        heap = []          # max-heap of qualities (negated)
        qual_sum = 0
        best = float('inf')

        for ratio, q in workers:
            heapq.heappush(heap, -q)
            qual_sum += q
            if len(heap) > k:
                qual_sum += heapq.heappop(heap)
            if len(heap) == k:
                best = min(best, ratio * qual_sum)

        return best
Explanation:

  1. Greedy choice: Sort workers by wage/quality ratio (the group rate). For each worker as the rate-setter, keep the k workers with smallest quality sum via a max-heap.
  2. Why it works: In any valid group, all pay = ratio × quality where ratio = max(wage_i/quality_i). Fixing the max ratio worker and greedily picking smallest qualities minimizes ratio × Σquality.
  3. Sliding window of size k over sorted ratios.

Time: O(n log n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        from itertools import combinations
        n = len(quality)
        best = float('inf')
        for combo in combinations(range(n), k):
            ratio = max(wage[i] / quality[i] for i in combo)
            cost = ratio * sum(quality[i] for i in combo)
            best = min(best, cost)
        return best
Explanation:

  1. Check every k-subset; group ratio = max of member ratios.
  2. O(C(n,k)·k) — greedy ratio-sort + heap is the intended solution.

Time: O(C(n,k) · k)  |  Space: O(k)

Problem 6: Reorganize String (Leetcode:767)#

Problem Statement

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" if not possible.

Example 1:

Input: s = "aab" Output: "aba"

Example 2:

Input: s = "aaab" Output: ""

Constraints:

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def reorganizeString(self, s: str) -> str:
        from collections import Counter
        import heapq
        freq = Counter(s)
        heap = [(-count, ch) for ch, count in freq.items()]
        heapq.heapify(heap)
        result = []
        prev = None

        while heap:
            count, ch = heapq.heappop(heap)
            result.append(ch)
            if prev:
                heapq.heappush(heap, prev)
            prev = (count + 1, ch) if count + 1 < 0 else None

        ans = ''.join(result)
        return ans if len(ans) == len(s) else ''
Explanation:

  1. Greedy choice: Always place the most frequent remaining character, but not twice in a row — hold the previous char in a 1-step cooldown.
  2. Why it works: If max_count <= (n+1)/2, scheduling most-frequent-first with spacing never dead-ends. Failing condition: one char dominates (max_count > (n+1)/2).
  3. Equivalent to LC 767 / task scheduling with cooldown=1.

Time: O(n log 26)  |  Space: O(26)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def reorganizeString(self, s: str) -> str:
        from collections import Counter
        freq = Counter(s)
        max_count = max(freq.values())
        if max_count > (len(s) + 1) // 2:
            return ''
        chars = []
        for ch, count in freq.items():
            chars.extend([ch] * count)
        chars.sort(key=lambda c: -freq[c])
        result = [''] * len(s)
        idx = 0
        for ch in chars:
            result[idx] = ch
            idx += 2
            if idx >= len(s):
                idx = 1
        return ''.join(result)
Explanation:

  1. Fill even indices first (0,2,4,…), then odd — most frequent chars spread maximally.
  2. Same feasibility check; no heap needed.
  3. Greedy placement avoids adjacent duplicates by construction.

Time: O(n log 26)  |  Space: O(n)

8. Greedy + Two Pointers#

Advance two pointers greedily to solve sorted-array-based problems.

Problem 1: Assign Cookies (Leetcode:455)#

Problem Statement

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.

Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Example 1:

Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

Example 2:

Input: g = [1,2], s = [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.

Constraints:

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        child = cookie = 0

        while child < len(g) and cookie < len(s):
            if s[cookie] >= g[child]:
                child += 1
            cookie += 1

        return child
Explanation:

  1. Greedy choice: Sort greed factors and cookie sizes. Give the smallest sufficient cookie to the least greedy unsatisfied child.
  2. Why it works: Using a larger cookie on a less greedy child wastes capacity — if s[j] >= g[i], matching child i never reduces the count vs saving the cookie. Advancing cookie always (whether or not it satisfies) preserves options.
  3. Maximize satisfied children, not minimize wasted cookies.

Time: O(m log m + n log n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        s.sort()
        used = [False] * len(s)
        count = 0
        for greed in sorted(g):
            for j in range(len(s)):
                if not used[j] and s[j] >= greed:
                    used[j] = True
                    count += 1
                    break
        return count
Explanation:

  1. For each child (sorted by greed), find the smallest unused fitting cookie.
  2. Same greedy logic but O(n·m) — two pointers after sorting is optimal.

Time: O(n · m)  |  Space: O(m)

Problem 2: Boats to Save People (Leetcode:881)#

Problem Statement

You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person.

Example 1:

Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)

Example 2:

Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)

Example 3:

Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)

Constraints:

  • 1 <= people.length <= 5 * 104
  • 1 <= people[i] <= limit <= 3 * 104
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        boats = 0
        left, right = 0, len(people) - 1

        while left <= right:
            if people[left] + people[right] <= limit:
                left += 1
            right -= 1
            boats += 1

        return boats
Explanation:

  1. Greedy choice: Sort weights. Try pairing lightest with heaviest; if they don't fit, the heavy person goes alone.
  2. Why it works: The heaviest person must be rescued eventually — pairing them with the lightest wastes minimum capacity. If the pair doesn't fit, no one can pair with the heaviest, so they sail alone.
  3. Each iteration removes at least one person from consideration.

Time: O(n log n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        from functools import lru_cache
        people = tuple(sorted(people))

        @lru_cache(maxsize=None)
        def dp(i, j):
            if i > j:
                return 0
            # heaviest goes alone or pairs with lightest
            alone = 1 + dp(i, j - 1)
            together = 1 + dp(i + 1, j - 1) if people[i] + people[j] <= limit else float('inf')
            return min(alone, together)

        return dp(0, len(people) - 1)
Explanation:

  1. State (i,j) = range of unsaved people after sorting.
  2. Same greedy decisions encoded recursively — exponential without memo on large n.
  3. Two-pointer greedy is O(n log n) and correct.

Time: O(n²) with memo  |  Space: O(n²)

Problem 3: Maximum Bags With Full Capacity of Rocks (Leetcode:2279)#

Problem Statement

You have n bags numbered from 0 to n - 1. You are given two 0-indexed integer arrays capacity and rocks. The ith bag can hold a maximum of capacity[i] rocks and currently contains rocks[i] rocks. You are also given an integer additionalRocks, the number of additional rocks you can place in any of the bags.

Return the maximum number of bags that could have full capacity after placing the additional rocks in some bags.

Example 1:

Input: capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2
Output: 3
Explanation:
Place 1 rock in bag 0 and 1 rock in bag 1.
The number of rocks in each bag are now [2,3,4,4].
Bags 0, 1, and 2 have full capacity.
There are 3 bags at full capacity, so we return 3.
It can be shown that it is not possible to have more than 3 bags at full capacity.
Note that there may be other ways of placing the rocks that result in an answer of 3.

Example 2:

Input: capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100
Output: 3
Explanation:
Place 8 rocks in bag 0 and 2 rocks in bag 2.
The number of rocks in each bag are now [10,2,2].
Bags 0, 1, and 2 have full capacity.
There are 3 bags at full capacity, so we return 3.
It can be shown that it is not possible to have more than 3 bags at full capacity.
Note that we did not use all of the additional rocks.

Constraints:

  • n == capacity.length == rocks.length
  • 1 <= n <= 5 * 104
  • 1 <= capacity[i] <= 109
  • 0 <= rocks[i] <= capacity[i]
  • 1 <= additionalRocks <= 109
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
        remaining = sorted(c - r for c, r in zip(capacity, rocks))
        full = 0
        for need in remaining:
            if additionalRocks >= need:
                additionalRocks -= need
                full += 1
            else:
                break
        return full
Explanation:

  1. Greedy choice: Sort bags by rocks still needed (capacity - rocks). Fill the cheapest bags first.
  2. Why it works: Each full bag costs a fixed deficit; minimizing cost per bag maximizes count for a fixed rock budget (knapsack with equal unit value per completed bag).
  3. Stop when additionalRocks is insufficient.

Time: O(n log n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
        import heapq
        needs = [c - r for c, r in zip(capacity, rocks)]
        heapq.heapify(needs)
        full = 0
        while needs and needs[0] <= additionalRocks:
            additionalRocks -= heapq.heappop(needs)
            full += 1
        return full
Explanation:

  1. Repeatedly fill the bag needing fewest additional rocks (min-heap).
  2. Same greedy policy as sorting — pick globally smallest remaining need each step.

Time: O(n log n)  |  Space: O(n)

9. Greedy on Graphs#

Graph algorithms that use greedy strategies (e.g., MSTs).

Problem 1: Prim's Algorithm (GeeksforGeeks)#

Problem Statement

Given a connected, weighted, undirected graph, find a Minimum Spanning Tree (MST) — a subset of edges connecting all vertices with minimum total weight.

Example 1:

Input: V=4, edges = [(0,1,10),(0,2,6),(0,3,5),(1,3,15),(2,3,4)]
Output: MST weight = 19 (edges: 2-3, 0-3, 0-1)

Example 2:

Input: V=3, edges = [(0,1,1),(1,2,2),(0,2,3)]
Output: 3

Constraints:

  • 1 <= V <= 104
  • 1 <= E <= 105
Code and Explanation 

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

def primMST(V: int, edges: list[tuple[int, int, int]]) -> int:
    graph = [[] for _ in range(V)]
    for u, v, w in edges:
        graph[u].append((w, v))
        graph[v].append((w, u))

    visited = [False] * V
    heap = [(0, 0)]   # (weight, vertex)
    mst_weight = 0

    while heap:
        w, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        mst_weight += w
        for weight, v in graph[u]:
            if not visited[v]:
                heapq.heappush(heap, (weight, v))

    return mst_weight
Explanation:

  1. Greedy choice: Grow the MST from a start vertex; always add the cheapest edge crossing the cut (tree ↔ non-tree).
  2. Why it works: Cut property — the minimum-weight edge across any cut belongs to some MST. Prim's repeatedly applies this safe-edge rule.
  3. Min-heap tracks frontier edges.

Time: O(E log V)  |  Space: O(V + E)

1
2
3
# See Problem 2 — sorts all edges globally instead of growing one tree.
def primViaKruskal(V, edges):
    pass   # Kruskal below is the dual greedy strategy
Explanation:

  1. Prim grows one connected component; Kruskal sorts all edges — both greedy, different data structures.
  2. Use Prim for dense graphs, Kruskal for sparse.

Time: —  |  Space: —

Problem 2: Kruskal's Algorithm (GeeksforGeeks)#

Problem Statement

Given a connected, weighted, undirected graph, find an MST by selecting edges in ascending weight order without forming cycles.

Example 1:

Input: V=4, edges = [(0,1,10),(0,2,6),(0,3,5),(1,3,15),(2,3,4)]
Output: MST weight = 19

Example 2:

Input: V=5, edges = [(0,1,2),(1,2,3),(0,3,6),(3,4,5),(1,4,4)]
Output: 14

Constraints:

  • 1 <= V <= 104
  • 1 <= E <= 105
Code and Explanation 

 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
def kruskalMST(V: int, edges: list[tuple[int, int, int]]) -> int:
    parent = list(range(V))
    rank = [0] * V

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb:
            return False
        if rank[ra] < rank[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        if rank[ra] == rank[rb]:
            rank[ra] += 1
        return True

    edges.sort(key=lambda x: x[2])
    mst_weight = 0
    count = 0
    for u, v, w in edges:
        if union(u, v):
            mst_weight += w
            count += 1
            if count == V - 1:
                break
    return mst_weight
Explanation:

  1. Greedy choice: Process edges in ascending weight; add an edge if it connects two different components (Union-Find).
  2. Why it works: Same cut-property / safe-edge theorem — the globally cheapest non-cycle edge is always safe.
  3. Stop after V-1 edges.

Time: O(E log E)  |  Space: O(V)

1
2
# Dual strategy: grow MST from a vertex with min-heap (see Problem 1).
# Both produce the same MST weight on connected undirected graphs.
Explanation:

  1. Kruskal = global edge sort; Prim = local min-edge expansion.
  2. Choose based on graph density and implementation convenience.

Time: —  |  Space: —

Problem 3: Network Delay Time (Leetcode:743)#

Problem Statement

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Example 1:


Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

Example 2:

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1

Example 3:

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1

Constraints:

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= ui, vi <= n
  • ui != vi
  • 0 <= wi <= 100
  • All the pairs (ui, vi) are unique. (i.e., no multiple edges.)
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        import heapq
        graph = [[] for _ in range(n + 1)]
        for u, v, w in times:
            graph[u].append((w, v))

        dist = [float('inf')] * (n + 1)
        dist[k] = 0
        heap = [(0, k)]

        while heap:
            d, u = heapq.heappop(heap)
            if d > dist[u]:
                continue
            for w, v in graph[u]:
                if d + w < dist[v]:
                    dist[v] = d + w
                    heapq.heappush(heap, (dist[v], v))

        ans = max(dist[1:])
        return ans if ans < float('inf') else -1
Explanation:

  1. Greedy choice: Always settle the unvisited node with smallest tentative distance (Dijkstra).
  2. Why it works: With non-negative weights, the first time a node is extracted its distance is final — no cheaper path can exist (greedy stays ahead of all unprocessed nodes).
  3. Answer = max shortest-path distance from k to all nodes.

Time: O(E log V)  |  Space: O(V + E)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        dist = [float('inf')] * (n + 1)
        dist[k] = 0
        for _ in range(n - 1):
            for u, v, w in times:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
        ans = max(dist[1:])
        return ans if ans < float('inf') else -1
Explanation:

  1. Relax all edges n-1 times — handles negative weights (not needed here).
  2. O(V·E) vs Dijkstra's O(E log V); Dijkstra's greedy choice exploits non-negative edges.

Time: O(n · E)  |  Space: O(n)

Problem 4: Minimum Cost to Connect All Points (Leetcode:1584)#

Problem Statement

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

Example 1:


Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation:

We can connect the points as shown above to get the minimum cost of 20.
Notice that there is a unique path between every pair of points.

Example 2:

Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18

Constraints:

  • 1 <= points.length <= 1000
  • -106 <= xi, yi <= 106
  • All pairs (xi, yi) are distinct.
Code and Explanation 

 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 minCostConnectPoints(self, points: List[List[int]]) -> int:
        import heapq
        n = len(points)
        visited = [False] * n
        heap = [(0, 0)]
        total = 0
        count = 0

        def manhattan(i, j):
            return abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])

        while heap and count < n:
            cost, u = heapq.heappop(heap)
            if visited[u]:
                continue
            visited[u] = True
            total += cost
            count += 1
            for v in range(n):
                if not visited[v]:
                    heapq.heappush(heap, (manhattan(u, v), v))

        return total
Explanation:

  1. Greedy choice: Complete graph on points with Manhattan edge weights — grow MST via Prim, always adding the cheapest edge to an unvisited point.
  2. Why it works: MST cut property applies to any connected graph; Manhattan metric doesn't change the greedy safe-edge argument.
  3. O(n² log n) acceptable for n ≤ 1000.

Time: O(n² log n)  |  Space: O(n)

 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
class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        edges = []
        for i in range(n):
            for j in range(i + 1, n):
                w = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
                edges.append((w, i, j))
        edges.sort()
        parent = list(range(n))

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        total = count = 0
        for w, u, v in edges:
            if find(u) != find(v):
                parent[find(u)] = find(v)
                total += w
                count += 1
                if count == n - 1:
                    break
        return total
Explanation:

  1. Generate all C(n,2) edges, sort by weight, Union-Find merge.
  2. Same MST weight as Prim — dual greedy strategy.
  3. O(n² log n) from edge generation and sort.

Time: O(n² log n)  |  Space: O(n²)