Gao's LeetCode 101: Greedy Algorithm

# Gao's LeetCode 101: Greedy Algorithm ## 0. Post Details - Reference: [Gao et al., LeetCode 101 - A Grinding Guide, 2001.](https://noworneverev.github.io/leetcode_101/category/4-%E5%8D%83%E5%A5%87%E7%99%BE%E6%80%AA%E7%9A%84%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95) - Post by: Jedd Yang - Date: 2025-02-13 - Keywords: Greedy Algorithm ## 1. Problems ### 455. Assign Cookies > 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. :::success - Approach: Greedy algorithm. - Complexity: Time $O(nlog(n) + mlog(m))$; Space $O(1)$. ::: ```cpp= class Solution { public: int findContentChildren(vector<int> &children, vector<int> &cookies) { sort(children.begin(), children.end()); sort(cookies.begin(), cookies.end()); int child_i = 0, cookie_i = 0; int n_children = children.size(), n_cookies = cookies.size(); while (child_i < n_children && cookie_i < n_cookies) { if (children[child_i] <= cookies[cookie_i]) { ++child_i; } ++cookie_i; } return child_i; } }; ``` ### 135. Candy > There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings. > > You are giving candies to these children subjected to the following requirements: > > Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. Return the minimum number of candies you need to have to distribute the candies to the children. :::success - Approach: Greedy algorithm. Only consider neighboring relationship, traverse each side, update the neighboring relationship during traverse. - Complexity: Time $O(n)$; Space $O(n)$. ::: ```cpp= class Solution { public: int candy(vector<int>& ratings) { int n = ratings.size(); // assign candies to each vector<int> candies(n, 1); // traverse left to right for (int i = 1; i < n; ++i) { if (ratings[i] > ratings[i - 1]) { candies[i] = candies[i - 1] + 1; } } // traverse right to left for (int i = n - 1; i > 0; --i) { if (ratings[i] < ratings[i - 1]) { candies[i - 1] = max(candies[i - 1], candies[i] + 1); } } return accumulate(candies.begin(), candies.end(), 0); } }; ``` ### 435. Non-overlapping Intervals > Given an array of intervals intervals where `intervals[i] = [start_i, end_i]`, 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. :::success - Approach: Greedy algorithm. Prioritize reserve the non-overlapping intervals with least `end_i`. - Complexity: Time $O(nlog(n))$; Space $O(1)$. ::: ```cpp= class Solution { public: int eraseOverlapIntervals(vector<vector<int>>& intervals) { sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b) { return a[1] < b[1]; }); int removed = 0; int prev_end = intervals[0][1]; for (int i = 1; i < intervals.size(); ++i) { if (intervals[i][0] < prev_end) { ++removed; } else { prev_end = intervals[i][1]; } } return removed; } }; ``` ### 605. Can Place Flowers > You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots. > > Given an integer array `flowerbed` containing `0`'s and `1`'s, where `0` means empty and `1` means not empty, and an integer `n`, return `true` if `n` new flowers can be planted in the `flowerbed` without violating the no-adjacent-flowers rule and `false` otherwise. :::success - Approach: Greedy algorithm. Find local plantable area, use `n` to update to see how much are planted. - Complexity: Time $O(n)$; Space $O(1)$. ::: ```cpp= class Solution { public: bool canPlaceFlowers(vector<int>& flowerbed, int n) { int len = flowerbed.size(); for(int i = 0; i < len; ++i){ if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == len - 1 || flowerbed[i + 1] == 0)) { flowerbed[i] = 1; // plant a flower here --n; // decrease the number of flowers left to plant i++; // skip to the next plot, can't plant adjacently } } // std::cout<<n<<endl; return n <= 0; } }; ``` ### 452. Minimum Number of Arrows to Burst Balloons > 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] = [x_start, x_end]` denotes a balloon whose horizontal diameter stretches between `x_start` and `x_end`. 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 `x_start` and `x_end` is burst by an arrow shot at `x` if `x_start <= x <= x_end`. 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. > > Similar to 435. :::danger - Approach: Let `shot` be the total balloon number, decrease by `1` if encounter over-lapping balloons. - Complexity: WA. ::: ```cpp= class Solution { public: int findMinArrowShots(vector<vector<int>>& points) { sort(points.begin(), points.end(), [](vector<int>& a, vector<int>& b){return a[1] < b[1]; }); int len = points.size(); int shot = len; int prev_end = points[0][1]; for (int i = 1; i < len; ++i){ if(points[i][0] <= prev_end){ if(i >= 2 && points[i-1][0] <= points[i-2][1]){ i++; } prev_end = points[i][1]; --shot; // 想法是，每次有重疊就扣掉。 // 但現在問題是它會多扣：a 氣球和 b 氣球重疊，b 氣球和 c 氣球重疊， // 理論上扣 1 次就好因為 b 氣球已經被打爆了，但這個寫法會扣兩次。 // 或許可以寫個判斷式加回來多扣的部分，但太難想。 } } return shot; } }; ``` :::success - Approach: Change perspective, since decrease is hard to code, let's increase it. "When encountering non-overlapping balloons, `shot` increases." Prioritize reserve the non-overlapping intervals with least `x_end`. - Complexity: Time $O(nlog(n))$; Space $O(log(n))$. ::: ```cpp= class Solution { public: int findMinArrowShots(vector<vector<int>>& points) { if (points.empty()) return 0; sort(points.begin(), points.end(), [](vector<int>& a, vector<int>& b){return a[1] < b[1];}); int len = points.size(); int shot = 1; int prev_end = points[0][1]; for (int i = 1; i < len; ++i){ if(points[i][0] > prev_end){ ++shot; prev_end = points[i][1]; } } return shot; } }; ``` ### 763. Partition Labels > You are given a string `s`. We want to partition the string into as many parts as possible so that each letter appears in at most one part. For example, the string `"ababcc"` can be partitioned into `["abab", "cc"]`, but partitions such as `["aba", "bcc"]` or `["ab", "ab", "cc"]` are invalid. > > Note that the partition is done so that after concatenating all the parts in order, the resultant string should be `s`. > > Return a list of integers representing the size of these parts. > [!Important] Train of thoughts > Given a string, we need to partition it such that the arbitrary section of the character doesn't appear in other sections. And then we return the length of each section. Do not sort, lest the order is changed. When an alphabet duplicates, update the partition position. >[!Tip] Hands-on Details > Use hash table to save the last position each alphabet last seen. After all saved, we can then compare, checking if each alphabet is at the position that's recorded in the hash table. If so, cut. > > But how to implement hash table in C++, use unordered_map. > > ```cpp= > //include > #include <unordered_map> > //declaration > std::unordered_map<char, int> lastPosition; > //adding a key-value > lastPosition['a'] = 3; // 'a' appears last at index 3 > ``` > > Further comparison of unordered_map and map. > > | Feature | `unordered_map` | `map` (Ordered Map) | > |------------------|------------------------------|---------------------------| > | Internal Structure | **Hash Table** | **Red-Black Tree (BST)** | > | Order | **No order (unordered)** | **Sorted by key** | > | Complexity (Lookup) | **O(1)** (average) | **O(log n)** | > | Performance | **Faster on average** | **Slower but consistent** | > | Use Case | Quick lookups, no sorting | When sorted order matters | :::success - Approach: Hash table. - Complexity: Time $O(n)$; Space $O(n)$. ::: ```cpp= class Solution { public: vector<int> partitionLabels(string s) { vector<int> cut; unordered_map<char, int> lastPosition; int currentEnd = 0; // 每个 partition 的头 int currentStart = 0; // 每个 partition 的尾 // 创一个 hash table for (int i = 0; i < s.size(); ++i){ lastPosition[s[i]] = i; } // 更新我下刀的位置 for (int i = 0; i < s.size(); ++i){ // 这里有点 Two pointer 的感觉在，就是当前遇到的字母，我用 currentEnd // 去指出这个字母最后出现的位置 currentEnd = max(currentEnd, lastPosition[s[i]]); // 那假如我发现当前的字母就是它最后出现的位置，则给出 partition 的头尾差 if (i == currentEnd){ cut.push_back(i - currentStart + 1); currentStart = i + 1; } } // 打印结果 // for (const auto& pair : lastPosition) { // cout << pair.first << ": " << pair.second << endl; // } return cut; } }; ``` ### 122. Best Time to Buy and Sell Stock II > 題意：給一組 ```n``` 天股價 array，```n``` 天內自由買入賣出，求累積最大利潤。 > 策略： > - 核心：Greedy strategy 为——只要明天价格高于今天价格，就卖出并立即买入。 > - 细节：随着天数，抓最低股价买入，只要明天价格高于今天价格，就卖出。卖出之后就假设当天是新的股价最低点，继续随这天数找股价新低点。 Submission 1, AC. Time complexity O(N), space complexity O(1) ```cpp= class Solution { public: int maxProfit(vector<int>& prices) { int final_profit = 0, pseudo_profit = 0; int buy = prices[0]; for (int i = 0; i < prices.size(); ++i){ // 随着天数，抓最低股价买入 buy = min(buy, prices[i]); // 比之前获利更高，就更新卖的日期 pseudo_profit = max(pseudo_profit, prices[i] - buy); cout <<"buy is " << buy << ", prices[i] is " << prices[i] << ", pseudo_profit is " << pseudo_profit << endl; // 当更新卖的日期，就买入股票 if (pseudo_profit == prices[i] - buy){ buy = prices[i]; final_profit += pseudo_profit; pseudo_profit = 0; } } return final_profit; } }; ``` ### 406. Queue Reconstruction by Height > 題意：給一組 array ```people```，```people[i] = [h_i, k_i]```，```h_i``` 代表第 ```i``` 人身高，```k_i``` 代表有幾人比 ```i```人高或同高，求正確排序 ```people```。 > 策略： > - 核心：Greedy strategy 为——先處理容易決定的高個子，再處理需要更多限制的矮個子。 > - 细节：先排序（身高高到低，標注低到高），再開新的 array 細排。優先處理「高身高」的人，因為高的人對後續矮的人影響較小。再將每個人按照 ```k_i``` 值插入到正確位置，確保對其他人的順序影響最小。 Submission 1, WA. ``` class Solution { public: vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b){ return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]); }); // output: [7,0][7,1][6,1][5,0][5,2][4,4] for (int i = 0; i < people.size(); ++i){ if (i > people[i][1]){ people[people[i][1]] = people[i]; } } return people; } }; ``` Submission 2, AC. Time complexity O(N^2), space complexity O(N) ``` class Solution { public: vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { vector<vector<int>> result; sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b){ return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]); }); // output: [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]] for (const auto& person : people){ result.insert(result.begin() + person[1], person); } // output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] return result; } }; ``` ### 665. Non-decreasing Array > 題意：給定一組大小爲 ```n``` 的 array ```nums```，求是否有辦法至多改一個數字，就讓他變成 non-decreasing order。 > 策略： > - 核心：Greedy strategy 为——遍歷所有的數字，只要發現前一個數字比后一個數字大，兩次（含）以上，就報錯。 > - 细节：除了尋找違規之外，還要考慮改一個數字影響整個 array。 Submission 1, WA. ``` class Solution { public: bool checkPossibility(vector<int>& nums) { int count = 0; for (int i = 1; i < nums.size(); ++i){ if (nums[i - 1] > nums[i]){ // 发现前一个数字比后一个大就加到 count ++count; if (count > 1) return false; // 规定是我只能改一个数字，所以 count > 1 就确定爆掉 } } return true; } }; ``` > 这个代码只寻找 local 的 violation，但没有考虑到我的改动会影响到整个 array 的趋势。所以不是只是说，哦发现违规，改，记起来，下一个——怎么改也是会影响的。例如这个测资就没过：```nums = [3,4,2,3]```，Output ```true```，Expected ```false```。那要如何改呢？我们不是有比较前一个数字跟后一个数字吗？思考我们可以把前一个数字改小，后一个数字改大。 Submission 2, AC. Time complexity O(N), space complexity O(1) 用 submission 1，但加这段 snippet 在 line 8 之后。 ``` // 看要改前一个数字还是后一个数字 if (i == 1 || nums[i - 2] <= nums[i]) { // 前前一个数字比后一个数字小，表示前一个数字太大 nums[i - 1] = nums[i]; // 把前一个数字改小，等于后一个数字 } else { nums[i] = nums[i - 1]; // 把后一个数字改大，等于前一个数字 } ```