Data Structures and Algorithms. Greedy approach

6 min readMar 11, 2024

Hi! It’s nice to see you here.

For today we’ll explore a new concept to work with DSA, such as Greedy approach.

Have you ever tried to solve the problems, when it was required to find something the biggest or the lowest? This way you were looking for the optimal solution.

To understand what it means, let’s consider a very simple example.

You have a list of nums. You should find an integer, that has the greatest frequency. If there’s a tie, you asked to return the lowest one.

This can be solved in TC O(N) in an easy way: create a frequency HashMap cache, ans and maxFreq to store answer and maximum frequency, respectively. Iterate over nums and update a particular maxFreq with ans.

def find(nums):
    ans, maxFreq = 0, 0
    cache = defaultdict(int)

    for num in nums:
        cache[num] += 1

        if maxFreq <= cache[num]:
            if maxFreq < cache[num]:
                maxFreq = cache[num]
                ans = num
            else:
                ans = min(num, ans)

    return ans

While you iterating over nums, you update the maximum frequency with the lowest ans.

Greedy is the strategy to find something optimal as an extremum (min/max). There’re some common techiques: Sorting and Heap/Priority Queue. But be careful:

Greedy isn’t a data structure and it doesn’t have a SPECIFIC boilerplate to apply for.

2656. Maximum Sum With Exactly K Elements

You are given a 0-indexed integer array nums and an integer k. Your task is to perform the following operation exactly k times in order to maximize your score:
1. Select an element m from nums.
2. Remove the selected element m from the array.
3. Add a new element with a value of m + 1 to the array.
4. Increase your score by m.
Return the maximum score you can achieve after performing the operation exactly k times.

Okay, if you follow these steps, you’ll get an optimal solution, that’s the maximum sum.

class Solution:
    def maximizeSum(self, nums: List[int], k: int) -> int:
        maximum = max(nums)
        ans = 0

        while k:
            ans += maximum
            maximum += 1
            k -= 1

        return ans

Time Complexity: O(N).

Space Complexity: O(1).

Okay, this was a warm-up. How about this one?

1561. Maximum Number of Coins You Can Get

There are 3n piles of coins of varying size, you and your friends will take piles of coins as follows:
- In each step, you will choose any 3 piles of coins (not necessarily consecutive).
- Of your choice, Alice will pick the pile with the maximum number of coins.
- You will pick the next pile with the maximum number of coins.
- Your friend Bob will pick the last pile.
- Repeat until there are no more piles of coins.
Given an array of integers piles where piles[i] is the number of coins in the ith pile.
Return the maximum number of coins that you can have.

The description is quite understandable. We have two friends with you as a second friend. In this company we have 3n piles and we should split them optimally in a such way, that you extract the maximum possible amount of coins.

The first player get the extremum, then you and then the last friend.

It’s obvious, that to distribute these coins, we should use sorting.

class Solution:
    def maxCoins(self, piles: List[int]) -> int:
        piles.sort(reverse=True)
        count = len(piles) / 3
        ans = 0
        # use this pointer to simply sum up our coins
        pointer = 1

        while count:
            count -= 1
            ans += piles[pointer]
            pointer += 2
        
        return ans

Time Complexity: O(N log N).

Space Complexity: O(1).

Let’s consider the next example.

2966. Divide Array Into Arrays With Max Difference

You are given an integer array nums of size n and a positive integer k.
Divide the array into one or more arrays of size 3 satisfying the following conditions:
Each element of nums should be in exactly one array.
The difference between any two elements in one array is less than or equal to k.
Return a 2D array containing all the arrays. If it is impossible to satisfy the conditions, return an empty array. And if there are multiple answers, return any of them.

Again, it’s obvious to follow the problem’s description for implementation. One thing to mention here is that we should sort an input again to be sure that difference between adjacent elements isn’t large than k.

class Solution:
    def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
        nums.sort()
        ans = []

        for i in range(1, len(nums) - 1, 3):
            prev, cur, nxt = nums[i - 1], nums[i], nums[i + 1]

            if nxt - cur > k or nxt - prev > k or cur - prev > k:
                return []

            ans.append([prev, cur, nxt])

        return ans

Time Complexity: O(N log N).

Space Complexity: O(N).

The next example will be the last one.

646. Maximum Length of Pair Chain

You are given an array of n pairs pairs where pairs[i] = [left, right] and left < right.
A pair p2 = [c, d] follows a pair p1 = [a, b] if b < c. A chain of pairs can be formed in this fashion.
Return the length longest chain which can be formed.
You do not need to use up all the given intervals. You can select pairs in any order.

The first thought: can we find a starting interval in advance to be sure THIS can be the first in the chain?
The second thought is: we’ve found a start interval, assume that we can choose any interval NEXT to the starting if it MEET the conditions:

# for [A,B] and [C, D] 
# B must be less then C. 
# Let's consider an example

a = [1, 2]
b = [2, 3]
c = [3, 4]

# The resulting chain will be [a, c], because
# a and c interval NON-OVERLAP each other, and the next interval
# can be any of them, if it will meet the conditions, respectively.
# This's the championship interval, whose ending point 
# will be THE FIRST ENDING point inside chain

And here is the solution:

class Solution:
    def findLongestChain(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        last = 0
        excluded = 0

        for i in range(1, len(intervals)):
            if intervals[last][1] >= intervals[i][0]:
                excluded += 1
            else:
                last = i

        return len(intervals) - excluded

Time Complexity: O(N log N).

Space Complexity: O(1).