Greedy

Table of Contents

• 455. Assign Cookies (Easy)
• 1005. Maximize Sum Of Array After K Negations (Easy)
• 860. Lemonade Change (Easy)
• 2037. Minimum Number of Moves to Seat Everyone (Easy)
• 376. Wiggle Subsequence (Medium)
• 738. Monotone Increasing Digits (Medium)
• 122. Best Time to Buy and Sell Stock II (Medium)
• 714. Best Time to Buy and Sell Stock with Transaction Fee (Medium)
• 135. Candy (Hard)
• 406. Queue Reconstruction by Height (Medium)
• 3075. Maximize Happiness of Selected Children (Medium)
• 945. Minimum Increment to Make Array Unique (Medium)
• 53. Maximum Subarray (Medium)
• 134. Gas Station (Medium)
• 968. Binary Tree Cameras (Hard)
• 1589. Maximum Sum Obtained of Any Permutation (Medium)

455. Assign Cookies

• LeetCode | 力扣

• Tags: Array, Two Pointers, Greedy, Sorting

Python

"""
-   Return the maximum number of your content children that can be satisfied.
"""

from typing import List


# Greedy
def findContentChildren(g: List[int], s: List[int]) -> int:
    g.sort()
    s.sort()
    i, j = 0, 0

    while i < len(g) and j < len(s):
        if g[i] <= s[j]:
            i += 1
        j += 1

    return i


# |-------------|-------------|--------------|
# |   Approach  |    Time     |    Space     |
# |-------------|-------------|--------------|
# |   Greedy    | O(N * logN) |    O(1)      |
# |-------------|-------------|--------------|


g = [1, 2, 3]
s = [1, 1]
print(findContentChildren(g, s))  # 1

1005. Maximize Sum Of Array After K Negations

• LeetCode | 力扣

• Tags: Array, Greedy, Sorting

Python

"""
-   Return the maximum sum of the array after changing at most `k` elements.
"""

from heapq import heapify, heapreplace
from typing import List


# Greedy
def largestSumAfterKNegationsGreedy(nums: List[int], k: int) -> int:
    nums.sort(key=abs, reverse=True)

    for i in range(len(nums)):
        if nums[i] < 0 and k > 0:
            nums[i] *= -1
            k -= 1

    if k % 2:
        nums[-1] *= -1

    return sum(nums)


# Heap
def largestSumAfterKNegationsHeap(nums: List[int], k: int) -> int:
    heapify(nums)

    while k and nums[0] < 0:
        heapreplace(nums, -nums[0])
        k -= 1

    if k % 2:
        heapreplace(nums, -nums[0])

    return sum(nums)


print(largestSumAfterKNegationsGreedy([4, 2, 3], 1))  # 5
print(largestSumAfterKNegationsHeap([4, 2, 3], 1))

860. Lemonade Change

• LeetCode | 力扣

• Tags: Array, Greedy

Python

"""
-   Return `True` if and only if you can provide every customer with correct change.
"""

from typing import List


# Greedy
def lemonadeChange(bills: List[int]) -> bool:
    hashmap = {5: 0, 10: 0, 20: 0}

    for i in bills:
        if i == 5:
            hashmap[5] += 1

        if i == 10:
            if hashmap[5] < 1:
                return False

            hashmap[5] -= 1
            hashmap[10] += 1

        if i == 20:
            if hashmap[5] >= 1 and hashmap[10] >= 1:
                hashmap[5] -= 1
                hashmap[10] -= 1
                hashmap[20] += 1

            elif hashmap[5] >= 3:
                hashmap[5] -= 3
                hashmap[20] += 1

            else:
                return False

    return True


print(lemonadeChange([5, 5, 5, 10, 20]))  # True

2037. Minimum Number of Moves to Seat Everyone

• LeetCode | 力扣

• Tags: Array, Greedy, Sorting, Counting Sort

Python

"""
-   Return the minimum number of moves needed to seat everyone.
"""

from typing import List


# Greedy
def minMovesToSeat(seats: List[int], students: List[int]) -> int:
    seats.sort()
    students.sort()
    moves = 0

    for i, j in zip(seats, students):
        moves += abs(i - j)

    return moves


print(minMovesToSeat([3, 1, 5], [2, 7, 4]))  # 4

376. Wiggle Subsequence

• LeetCode | 力扣

• Tags: Array, Dynamic Programming, Greedy

Python

"""
-   Return the length of the longest wiggle subsequence.
-   `up[n]` stores the length of the longest wiggle subsequence ending at `n` with a rising wiggle.
-   `down[n]` stores the length of the longest wiggle subsequence ending at `n` with a falling wiggle.
-   Initialize `up[0] = 1` and `down[0] = 1`.
-   Example: `nums = [1, 7, 4, 9, 2, 5]`

| `nums[n]` | `nums[n-1]` | `up[n-1]` | `down[n-1]` | `up[n]` | `down[n]` |
| :-------: | :---------: | :-------: | :---------: | :-----: | :-------: |
|     1     |      -      |     -     |      -      |    1    |     1     |
|     7     |      1      |     1     |      1      |    2    |     1     |
|     4     |      7      |     2     |      1      |    2    |     3     |
|     9     |      4      |     2     |      3      |    4    |     3     |
|     2     |      9      |     4     |      3      |    4    |     5     |
|     5     |      2      |     4     |      5      |    6    |     5     |
"""

from typing import List


# DP
def wiggleMaxLengthDP(nums: List[int]) -> int:
    if len(nums) <= 1:
        return len(nums)

    up = [0 for _ in range(len(nums))]
    down = [0 for _ in range(len(nums))]

    up[0], down[0] = 1, 1

    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            up[i] = down[i - 1] + 1
            down[i] = down[i - 1]
        elif nums[i] < nums[i - 1]:
            down[i] = up[i - 1] + 1
            up[i] = up[i - 1]
        else:
            up[i] = up[i - 1]
            down[i] = down[i - 1]

    return max(up[-1], down[-1])


# Greedy
def wiggleMaxLengthGreedy(nums: List[int]) -> int:
    if len(nums) < 2:
        return len(nums)

    prev_diff = nums[1] - nums[0]
    count = 2 if prev_diff != 0 else 1

    for i in range(2, len(nums)):
        diff = nums[i] - nums[i - 1]
        if (diff > 0 and prev_diff <= 0) or (diff < 0 and prev_diff >= 0):
            count += 1
            prev_diff = diff

    return count


# |-------------|-----------------|--------------|
# |  Approach   |      Time       |    Space     |
# |-------------|-----------------|--------------|
# |    DP       |      O(n)       |     O(n)     |
# |  Greedy     |      O(n)       |     O(1)     |
# |-------------|-----------------|--------------|

nums = [1, 7, 4, 9, 2, 5]
print(wiggleMaxLengthDP(nums))  # 6
print(wiggleMaxLengthGreedy(nums))  # 6

738. Monotone Increasing Digits

• LeetCode | 力扣

• Tags: Math, Greedy

Python

"""
-   Return the largest number that is less than or equal to `n` with monotone increasing digits.
"""


# Greedy
def monotoneIncreasingDigits(n: int) -> int:
    strNum = list(str(n))

    for i in range(len(strNum) - 2, -1, -1):
        if int(strNum[i]) > int(strNum[i + 1]):
            strNum[i] = str(int(strNum[i]) - 1)
            strNum[i + 1 :] = ["9"] * (len(strNum) - (i + 1))

    return int("".join(strNum))


n = 332
print(monotoneIncreasingDigits(n))  # 299

122. Best Time to Buy and Sell Stock II

• LeetCode | 力扣

• Tags: Array, Dynamic Programming, Greedy

PythonCPP

"""
-   Return the maximum profit you can achieve.
"""

from typing import List


# DP
def maxProfitDP1(prices: List[int]) -> int:
    n = len(prices)
    if n <= 1:
        return 0

    dp = [[0] * 2 for _ in range(n)]
    dp[0][0] = -prices[0]
    dp[0][1] = 0

    for i in range(1, n):
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])

    return dp[-1][1]


# DP - Optimized
def maxProfitDP2(prices: List[int]) -> int:
    n = len(prices)
    if n <= 1:
        return 0

    hold = -prices[0]
    profit = 0

    for i in range(1, n):
        hold = max(hold, profit - prices[i])
        profit = max(profit, hold + prices[i])

    return profit


# Greedy
def maxProfitGreedy(prices: List[int]) -> int:
    profit = 0

    for i in range(1, len(prices)):
        profit += max(prices[i] - prices[i - 1], 0)

    return profit


# |------------|------- |---------|
# |  Approach  |  Time  |  Space  |
# |------------|--------|---------|
# |     DP1    |  O(n)  |   O(n)  |
# |     DP2    |  O(n)  |   O(1)  |
# |   Greedy   |  O(n)  |   O(1)  |
# |------------|--------|---------|


prices = [7, 1, 5, 3, 6, 4]
print(maxProfitDP1(prices))  # 7
print(maxProfitDP2(prices))  # 7
print(maxProfitGreedy(prices))  # 7

#include <array>
#include <cassert>
#include <climits>
#include <vector>
using namespace std;

class Solution {
   public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<array<int, 2>> memo(n, {-1, -1});

        auto dfs = [&](this auto&& dfs, int i, bool hold) -> int {
            if (i < 0) {
                return hold ? INT_MIN : 0;
            }
            int& res = memo[i][hold];
            if (res != -1) {
                return res;
            }
            if (hold) {
                return res = max(dfs(i - 1, true),                // skip
                                 dfs(i - 1, false) - prices[i]);  // buy
            } else {
                return res = max(dfs(i - 1, false),              // skip
                                 dfs(i - 1, true) + prices[i]);  // sell
            }
        };

        return dfs(n - 1, false);
    }
};

int main() {
    Solution solution;
    vector<int> prices = {7, 1, 5, 3, 6, 4};
    assert(solution.maxProfit(prices) == 7);
    return 0;
}

714. Best Time to Buy and Sell Stock with Transaction Fee

• LeetCode | 力扣

• Tags: Array, Dynamic Programming, Greedy

Python

"""
-   Return the maximum profit you can achieve with the given transaction fee.
"""

from typing import List


# 1. DP
def maxProfitDP(prices: List[int], fee: int) -> int:
    n = len(prices)
    if n <= 1:
        return 0

    dp = [[0] * 2 for _ in range(n)]

    dp[0][0] = -prices[0] - fee
    dp[0][1] = 0

    for i in range(1, n):
        dp[i][0] = max(
            dp[i - 1][0],  # hold
            dp[i - 1][1] - prices[i] - fee,  # buy
        )
        dp[i][1] = max(
            dp[i - 1][1],  # hold
            dp[i - 1][0] + prices[i],  # sell
        )

    return max(dp[-1])


# 2. Greedy
def maxProfitGreedy(prices: List[int], fee: int) -> int:
    n = len(prices)
    if n == 0:
        return 0

    buy = prices[0]
    profit = 0

    for i in range(1, n):
        if prices[i] < buy:
            buy = prices[i]
        elif prices[i] > buy + fee:
            profit += prices[i] - buy - fee
            buy = prices[i] - fee

    return profit


prices = [1, 3, 2, 8, 4, 9]
fee = 2
print(maxProfitDP(prices, fee))  # 8
print(maxProfitGreedy(prices, fee))  # 8

135. Candy

• LeetCode | 力扣

• Tags: Array, Greedy

Python

"""
-   Return the minimum number of candies you must give.
"""

from typing import List


# Greedy
def candy(ratings: List[int]) -> int:
    # TC: O(n)
    # SC: O(n)
    n = len(ratings)

    if n <= 1:
        return n

    candy = [1 for _ in range(n)]

    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            candy[i] = candy[i - 1] + 1

    for j in range(n - 2, -1, -1):
        if ratings[j] > ratings[j + 1]:
            candy[j] = max(candy[j], candy[j + 1] + 1)

    return sum(candy)


ratings = [1, 0, 2]
print(candy(ratings))  # 5

406. Queue Reconstruction by Height

• LeetCode | 力扣

• Tags: Array, Binary Indexed Tree, Segment Tree, Sorting

Python

"""
-   Reconstruct the queue.
"""

from typing import List


# Greedy
def reconstructQueue(people: List[List[int]]) -> List[List[int]]:
    queue = []
    people.sort(key=lambda x: (-x[0], x[1]))

    for i in people:
        queue.insert(i[1], i)

    return queue


people = [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]
print(reconstructQueue(people))
# [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

3075. Maximize Happiness of Selected Children

• LeetCode | 力扣

• Tags: Array, Greedy, Sorting

Python

from typing import List


# Greedy
def maximumHappinessSum(happiness: List[int], k: int) -> int:
    selected = 0
    happinessScore = 0
    happiness.sort(reverse=True)

    for score in happiness:
        if selected == k:
            return happinessScore
        happinessScore += max(0, score - selected)
        selected += 1

    return happinessScore


happiness = [1, 2, 3]
k = 2
print(maximumHappinessSum(happiness, k))  # 4

945. Minimum Increment to Make Array Unique

• LeetCode | 力扣

• Tags: Array, Greedy, Sorting, Counting

Python

from typing import List


# Greedy
def minIncrementForUnique(nums: List[int]) -> int:
    nums.sort()
    moves = 0

    for i in range(1, len(nums)):
        if nums[i] <= nums[i - 1]:
            moves += nums[i - 1] + 1 - nums[i]
            nums[i] = nums[i - 1] + 1

    return moves


nums = [1, 2, 2]
print(minIncrementForUnique(nums))  # 1

53. Maximum Subarray

• LeetCode | 力扣

• Tags: Array, Divide And Conquer, Dynamic Programming

Python

from typing import List


# DP Kadane
def maxSubArrayDP(nums: List[int]) -> int:
    dp = [0 for _ in range(len(nums))]

    dp[0] = nums[0]
    maxSum = nums[0]

    for i in range(1, len(nums)):
        dp[i] = max(
            dp[i - 1] + nums[i],  # continue the previous subarray
            nums[i],  # start a new subarray
        )
        maxSum = max(maxSum, dp[i])

    return maxSum


# Greedy
def maxSubArrayGreedy(nums: List[int]) -> int:
    max_sum = nums[0]
    cur_sum = 0

    for num in nums:
        cur_sum = max(cur_sum + num, num)
        max_sum = max(max_sum, cur_sum)

    return max_sum


# Prefix Sum
def maxSubArrayPrefixSum(nums: List[int]) -> int:
    prefix_sum = 0
    prefix_sum_min = 0
    res = float("-inf")

    for num in nums:
        prefix_sum += num
        res = max(res, prefix_sum - prefix_sum_min)
        prefix_sum_min = min(prefix_sum_min, prefix_sum)

    return res


nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArrayDP(nums))  # 6
print(maxSubArrayGreedy(nums))  # 6
print(maxSubArrayPrefixSum(nums))  # 6

134. Gas Station

• LeetCode | 力扣

• Tags: Array, Greedy

PythonCPP

from typing import List


# Greedy
def canCompleteCircuit(gas: List[int], cost: List[int]) -> int:
    curSum = 0
    totalSum = 0
    start = 0

    for i in range(len(gas)):
        curSum += gas[i] - cost[i]
        totalSum += gas[i] - cost[i]

        if curSum < 0:
            start = i + 1
            curSum = 0

    if totalSum < 0:
        return -1

    return start


gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
print(canCompleteCircuit(gas, cost))  # 3

#include <cassert>
#include <vector>
using namespace std;

class Solution {
   public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int totalTank = 0, currTank = 0;
        int start = 0;
        int n = gas.size();

        for (int i = 0; i < n; i++) {
            int diff = gas[i] - cost[i];
            totalTank += diff;
            currTank += diff;

            if (currTank < 0) {
                start = i + 1;
                currTank = 0;
            }
        }

        return (totalTank >= 0) ? start : -1;
    }
};

int main() {
    Solution obj;
    vector<int> gas{1, 2, 3, 4, 5};
    vector<int> cost{3, 4, 5, 1, 2};
    int res = obj.canCompleteCircuit(gas, cost);
    assert(res == 3);
    return 0;
}

968. Binary Tree Cameras

• LeetCode | 力扣

• Tags: Dynamic Programming, Tree, Depth First Search, Binary Tree

Python

from typing import Optional

from binarytree import Node as TreeNode
from binarytree import build


def minCameraCover(root: Optional[TreeNode]) -> int:
    res = 0

    def dfs(node, hasParent):
        if not node:
            return -1

        nonlocal res
        left, right = dfs(node.left, True), dfs(node.right, True)

        if left == -1 and right == -1:
            if hasParent:
                return 0
            res += 1
            return 2
        if left == 0 or right == 0:
            res += 1
            return 2
        if left == 2 or right == 2:
            return 1
        if hasParent:
            return 0
        res += 1
        return 2

    dfs(root, False)

    return res


root = build([0, 0, None, 0, 0])
print(root)
print(minCameraCover(root))  # 1

1589. Maximum Sum Obtained of Any Permutation

• LeetCode | 力扣

• Tags: Array, Greedy, Sorting, Prefix Sum

Python

from typing import List


# Greedy
def maxSumRangeQuery(nums: List[int], requests: List[List[int]]) -> int:
    n = len(nums)
    freq = [0 for _ in range(n + 1)]

    for start, end in requests:
        freq[start] += 1
        if end + 1 < n:
            freq[end + 1] -= 1

    for i in range(1, n):
        freq[i] += freq[i - 1]

    freq.pop()

    freq.sort(reverse=True)
    nums.sort(reverse=True)

    max_sum = 0
    mod = 10**9 + 7

    for i, j in zip(nums, freq):
        max_sum += i * j
        max_sum %= mod

    return max_sum


nums = [1, 2, 3, 4, 5]
requests = [[1, 3], [0, 1]]
print(maxSumRangeQuery(nums, requests))  # 19

Comments