What is Greedy, anyway?

One of the goals I had coming to RC was to gain deeper understanding of fundamental concepts in Computer Science and Software Engineering. One of the things I was confused about was greedy algorithms.

According to wikipedia,

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum. In many problems, a greedy strategy does not in general produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a global optimal solution in a reasonable time.

As such, I assumed a greedy approach to be a way of finding a sub-optimal solution for some optimization problem. However, I kept running into greedy algorithm problems on interview prep websites, e.g. LeetCode, InterviewBit and others. How could an online judge evaluate a suboptimal solution?

Then I had a chat with amazing Marielle Foster (Summer 2016 batch), and she pointed out that there’s a class of problems that generally belong to dynamic programming but can be solved with greedy approach. So I re-read the wikipedia article, and found the last missing piece of the puzzle.

Note that in general the change-making problem requires dynamic programming or integer programming to find an optimal solution; however, most currency systems, including the Euro and US Dollar, are special cases where the greedy strategy does find an optimal solution.

It is clear now that in Tech Interview language, the greedy algorithm problem is a problem that can be solved using dynamic programming but also allows for a more efficient and elegant greedy solution. A couple of examples, to illustrate the point.

1. Increasing Subsequences Count

You are given an array of n positive integers, A1, A2 ,…, An. Let’s denote by A[i, j] the subarray Ai, Ai+1 ,…, Aj. Count pairs (i, j) such that 1 ≤ i ≤ j ≤ n and subarray A[i, j] is increasing. A subarray A1, A2 ,…, An is increasing if Ai < Ai+1, for all 1 ≤ i < N.

Seemingly a typical DP problem, it has a better solution that doesn’t involve keeping a DP table and looking up results of smaller sub-problems to find the solution for the whole input. But let’s take a look at DP solution first.

def subseq_count(A):
    dptable = {}
    for i in range(len(A)):
        dptable[(i,i)] = 1
    for i in range(1, len(A)):
        for j in range(len(A)-i):
            if (j, j+i-1) in dptable and A[j+i] > A[j+i-1]:
                dptable[(j, j+i)] = 1
    return len(dptable)

O(n^2) time and O(n^2) space complexity. Slow and clunky. Let’s look at greedy solution. We can take advantage of the fact that the number of unique subsequences of a given sequence with order preserved is n*(n+1)/2.

def subseq_count(A):
    res = len(A)
    i, j = 0, 0
    while j < len(A):
        while j < len(A) and A[j] > A[j-1]:
            j += 1
        if j-1 > i:
            n = j-1-i
            res += n*(n+1)//2
        i = j
        j += 1
    return res

There it is. Linear time and constant space complexity.

2. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than floor(n/2) times. You may assume that the array is non-empty and the majority element always exist in the array.
For input of [2, 1, 2] return 2.

Here’s dynamic-programming-style (not DP per se, but a good example nevertheless) solution in which you keep count of every element and end up using O(n) extra space.

def majority_element(A):
    hashmap = {}
    for element in A:
        if element in hashmap:
            hashmap[element] += 1
        else:
            hashmap[element] = 1
        if hashmap[element] > len(A)//2:
            return element

And here’s a constant extra space solution using greedy-style approach.

def majority_element(A):
    count = 1
    maj_idx = 0
    for i in range(1, len(A)):
        if A[i] == A[maj_idx]:
            count += 1
        else:
            count -= 1
        if not count:
            maj_idx = i
            count = 1
    return A[maj_idx]

Conclusion

Some DP problems will have a greedy solution. Some problems that are somewhat similar to DP in nature will have a greedy solution. I still don’t know if there’s a rule of thumb that will tell you when a problem has one. Perhaps, with practice you can spot them right away.

Share →