[Leetcode] Greedy

Posted on | In , |

Intro

An algorithmic paradigm that follows the problem solving approach of making the locally optimal choice at each stage with the hop of finding a global optimum.

Pros - simple, easy to implement, run fast
Cons - Very often they don’t cover all the cases

Greedy problems:

  1. Greedy: A global optimum can be arrived at by selecting a local optimum.
  2. Optimal Substructure: An optimal solution to the problem contains an optimal solution to the subproblems.

Problems

  1. Activity Selection Problem
  2. Huffman Coding
  3. Job Sequencing Problem
  4. Fractional Knapsack Problem
  5. Prim’s Minimum Spanning Tree

621. Task Scheduler

Video: https://www.youtube.com/watch?v=ySTQCRya6B0

[Solution]

  1. Maximum possible number of idle slots is defined by the frequency of the most frequent task
  2. Allocate the most frequent number first, maximum idle = (max_freq - 1) * n
  3. total time = amount of task + amount of idle
1
2
3
4
5
6
7
8
9
10
11
12
13
def leastInterval(self, tasks: List[str], n: int) -> int:
    counter = collections.Counter(tasks)
    heap = []
    for k in counter.values():
        heapq.heappush(heap, -k)
    freqMax = heapq.heappop(heap)
    freqMax *= -1
    idle = (freqMax - 1) * n
    while heap and idle > 0:
        freq = heapq.heappop(heap)
        freq *= -1
        idle -= min(freq, freqMax - 1)
    return max(0, idle) + len(tasks)

630. Course Schedule III

Leetcode: https://leetcode.com/problems/course-schedule-iii/

Solution: https://leetcode.com/problems/course-schedule-iii/solution/ Iterative solution is very greedy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def scheduleCourse(self, courses: List[List[int]]) -> int:
    courses.sort(key = lambda x: x[1])
    removed = set()
    count = 0
    curTime = 0
    index = 0
    for duration, deadline in courses:
        if curTime + duration > deadline:
            maxIndex, maxDuration = index, duration
            for i in range(index):
                if courses[i][0] > maxDuration:
                    maxIndex = i
                    maxDuration = courses[i][0]
            if maxDuration > duration:
                # If time winned by removing previous course can let the current course fit
                curTime += duration - maxDuration
            courses[maxIndex][0] = -1
        else:
            curTime += duration
            count += 1
        index += 1
    return count

1054. Distant Barcodes

Leetcode: https://leetcode.com/problems/distant-barcodes/

Solution:
Use a max heap to allocate the max count values first.

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
from heapq import *
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        res = []
        d = {}
        heap = []
        for bar in barcodes:
            if bar not in d:
                d[bar] = 1
            else:
                d[bar] += 1
        for key in d:
            heappush(heap, (-d[key], key))
        # print(heap)
        prev = None
        while heap:
            cur = heappop(heap)
            if prev != None:
                heappush(heap, prev)
            res.append(cur[1])
            cnt = -cur[0] - 1
            if cnt != 0:
                prev = (-cnt, cur[1])
            else:
                prev = None
        return res

767. Reorganize String

Leetcode: https://leetcode.com/problems/reorganize-string/

Note:
Same as above, arrange characters with higher frequency first.

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
from heapq import *
class Solution(object):
    def reorganizeString(self, S):
        count = collections.Counter(S)
        heap = []
        res = ""
        for cnt in count:
            if count[cnt] > len(S) // 2 + 1:
                return ""
            heappush(heap, (-count[cnt], cnt))
        while heap:
            if len(heap) < 2:
                n = heappop(heap)
                if n[0] > 1 or (n[0] == 1 and res and n[1] == res[-1]):
                    return ""
                elif n[0] == 0:
                    return res
            n1, n2 = heappop(heap), heappop(heap)
            
            if not res or (res and n1[0] != 0 and n1[1] != res[-1]):
                res += n1[1]
                heappush(heap, (-(abs(n1[0]) - 1), n1[1]))
                heappush(heap, (n2[0], n2[1]))
            elif n2[1] != res[-1] and n2[0] != 0:
                res += n2[1]
                heappush(heap, (-(abs(n2[0] )- 1), n2[1]))
                heappush(heap, (n1[0], n1[1]))
        if len(res) != len(S):
            return ""
        return res

406. Queue Reconstruction by Height

Leetcode: https://leetcode.com/problems/queue-reconstruction-by-height/

Solution: Since all the people only count the amount of people taller or equal to themselves, the shortest person is irrelavant to the other people in the group. So we can first arrange everybody else and then insert the shortest person into appropriate place. Since the shortest person counts all the taller/equal person in front of him, then the insertion position should be the counts of the shortest person.

1
2
3
4
5
6
7
8
9
10
11
var reconstructQueue = function(people) {
    let res = new Array();
    people.sort((a, b) => {
        if (a[0] !== b[0]) { return b[0] - a[0]}
        else { return a[1] - b[1]}
    });
    people.forEach(peo => {
        res.splice(peo[1], 0, peo);
    });
    return res;
};
1
2
3
4
5
6
def reconstructQueue(self, people):
    people.sort(key=lambda (h, k): (-h, k))
    queue = []
    for p in people:
        queue.insert(p[1], p)
    return queue

Note: In python we can sort with two keys with lambda function. The use of list.insert(element, index) method in python is similiar to splice() in javascript.

45. Jump Game II

Leetcode: https://leetcode.com/problems/jump-game-ii/

Note:

  • Always jump to a place that will take us the farthest
  • curEnd is used to track the furthurest place we can go on the current step
  • Once we reach curEnd, we extend it to curFur, and count how many extensions have we made
1
2
3
4
5
6
7
8
9
def jump(self, nums: List[int]) -> int:
    # greedy
    cnt, curEnd, curFur = 0, 0, 0
    for i in range(len(nums) - 1):
        curFur = max(curFur, nums[i] + i)
        if i == curEnd:
            cnt += 1
            curEnd = curFur
    return cnt

517. Super Washing Machines

Leetcode: https://leetcode.com/problems/super-washing-machines/

134. Gas Station

Leetcode: https://leetcode.com/problems/gas-station/
Video: https://www.youtube.com/watch?v=nTKdYm_5-ZY&list=PLupD_xFct8mETlGFlLVrwbLwcxczbgWRM&index=8&t=0s

[Solution]

  1. One pass: Use memoization to keep track of how much gas do we lack
1
2
3
4
5
6
7
8
9
10
11
12
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
    tank, total, start = 0, 0, 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        total += gas[i] - cost[i]
        if tank < 0:
            start = i + 1
            tank = 0
        i += 1
    if total < 0:
        return -1
    return start

Peak and valley problem

738. Monotone Increasing Digits

Leetcode: https://leetcode.com/problems/monotone-increasing-digits/

  • Find the first decreasing point
  • Reduce the digit at the decreasing point by 1, and fill the rest with 9
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
class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        # go thru the list backwards
        # find the leftest digit to be lowering
        # fill the rest with 9
        strn = str(n)
        index = len(strn) - 1
        low = int(strn[index])
        for i in reversed(range(len(strn) - 1)):
            if int(strn[i]) > low:
                index = i
                low = int(strn[i]) - 1
            else:
                low = int(strn[i])
                
        if index == len(strn) - 1:
            return n
        res = ''
        for i in range(len(strn)):
            if i < index:
                res += strn[i]
            elif i == index:
                res += str(int(strn[i]) - 1)
            else:
                res += '9'
        return int(res)

1838. Frequency of the Most Frequent Element

Video: https://www.youtube.com/watch?v=KhQOPSa09Fs&list=PLLuMmzMTgVK5Igci8P3d88XpoyeIA1Fl-&ab_channel=HuaHua

  • Note: use float to prevent super big sums
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def maxFrequency(self, nums: List[int], k: int) -> int:
    if not nums:
        return 0
    # sort the array
    nums.sort()
    # find j such that nums[i]~nums[j] can be the same within k operations
    # targetSum = nums[j] * (j - i + 1)
    # actualSum = sum(num[i:j + 1])
    # while targetSum - actualSum <= k: valid
    i, j = 0, 0
    res = 0
    actualSum, targetSum = 0, 0
    while j < len(nums):
        actualSum += nums[j]
        while k + actualSum < float(nums[j] * (j - i + 1)) and i < j:
            actualSum -= nums[i]
            i += 1
        res = max(res, j - i + 1)
        j += 1
    return res

53. Maximum Subarray

Leetcode: https://leetcode.com/problems/maximum-subarray/

Greedy Solution:
Pick the locally optimal move at each step, and that will lead to the globally optimal solution
Current maximum window: If max[i - 1] > 0: include [i - 1] element. Else, set maximum to yourself.

1
2
3
4
5
6
7
def maxSubArray(self, nums: List[int]) -> int:
    res = -float('inf')
    for i in range(len(nums)):
        if i > 0 and nums[i - 1] > 0:
            nums[i] = nums[i - 1] + nums[i]
        res = max(res, nums[i])
    return res

122. Best Time to Buy and Sell Stock II

Leetcode: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/

Solution:

  • Remember the lowest previous price before current day
  • Move on to find the next valley
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        l, h = 0, 0
        res = 0
        for i in range(len(prices)):
            if prices[i] > prices[h]:
                h = i
                res += prices[h] - prices[l]
                l = i
            if prices[i] < prices[l]:
                l = i
                h = i
        return res