# Greedy

#### [122. Best Time to Buy and Sell Stock II](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/)

Add all slope of between the peeks and valleys when the second number is larger than the first one.

![](https://249794273-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Laur3QE_YAExtEZegFt%2F-M91lxrPIXa1psRdVk01%2F-M91pSyUPe03pL_HBmQb%2Fimage.png?alt=media\&token=e002042e-b1f6-43d7-8bc0-8701264abec3)

*T: O(n)  S: O(1)*

```java
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] - prices[i - 1] >= 0) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
```

```cpp
// Peak/Valley solution
int maxProfit(vector<int>& prices) {
    int peak = prices[0], valley = prices[0];
    int i = 0;
    int sum = 0;
    while (i < prices.size() - 1) {
        while (i < prices.size() - 1 && prices[i] >= prices[i + 1]) i++;
        valley = prices[i];
        while (i < prices.size() - 1 && prices[i] <= prices[i + 1]) i++;
        peak = prices[i];
        sum += peak - valley;
    }
    return sum;
}
```

#### [55. Jump Game](https://leetcode.com/problems/jump-game/)

Maintain the `farest` point it can jump, if `i` is larger than `farest` it means it is not possible to jump to `i`.&#x20;

*T: O(n) S: O(1)*

```java
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) return true;
        int farest = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > farest) return false;
            farest = Math.max(farest, i + nums[i]);
        }
        return true;
    }
```

#### [45. Jump Game II](https://leetcode.com/problems/jump-game-ii/)

Initiate the maximum position that one could reach starting from the current index i or before: `max_pos = nums[0]`. Initiate number of steps: at least one, if array has more than 1 cell.

Iterate over number of elements in the input array:&#x20;

* If max\_step < i, one needs one more jump: `jumps += 1`. To minimize the number of jumps, choose the longest possible one: max\_steps = max\_pos.
* Update `max_pos = max(max_pos, i + nums[i])`.

```java
    public int jump(int[] nums) {
        if (nums.length < 2) return 0;
        int maxPos = nums[0], maxSteps = nums[0];
        int step = 1;
        for (int i = 1; i < nums.length; i++) {
            if (maxSteps < i) {
                step++;
                maxSteps = maxPos;
            }
            maxPos = Math.max(maxPos, i + nums[i]);
        }
        return step;
    }
```

#### [134. Gas Station](https://leetcode.com/problems/gas-station/)&#x20;

"The algorithm is pretty easy to understand. Imagine we take a tour around this circle, the only condition that we can complete this trip is to have more fuel provided than costed in total. That's what the first loop does.&#x20;

If we do have more fuel provided than costed, that means we can always find a start point around this circle that we could complete the journey with an empty tank. Hence, we check from the beginning of the array, if we can gain more fuel at the current station, we will maintain the start point, else, which means we will burn out of oil before reaching to the next station, we will start over at the next station." @pigwall

*T: O(n)  S: O(1)*

```java
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0;
        int n = gas.length;
        for (int i = 0; i < n; i++) {
            total += gas[i] - cost[i];
        }
        if (total < 0) return -1;
        int startpos = 0, accumulate = 0;
        for (int i = 0; i < n; i++) {
            accumulate += gas[i] - cost[i];
            if (accumulate < 0) {
                accumulate = 0;
                startpos = i + 1;
            }
        }
        return startpos;
    }
```

#### [763. Partition Labels](https://leetcode.com/problems/partition-labels/)

Record all last indicies of each character. Consider the first label, say it's `'a'`. The first partition must include the last occurrence of `'a'`. However, before the last `'a'` there might be a different label makes the partition bigger. For example, in `"abccaddbeffe"`, the minimum first partition is `"abccaddb"`. This gives us the idea for the algorithm: **For each letter encountered, process the last occurrence of that letter, extending the current partition \[anchor, j] appropriately**.

```java
public List<Integer> partitionLabels(String S) {
    int[] last = new int[26];
    for (int i = 0; i < S.length(); i++) {
        last[S.charAt(i) - 'a'] = i;
    }
    List<Integer> res = new ArrayList<>();
    int j = 0, anchor = 0;
    for (int i = 0; i < S.length(); i++) {
        j = Math.max(j, last[S.charAt(i) - 'a']);
        if (i == j) {
            res.add(i - anchor + 1);
            anchor = i + 1;
        }
    }
    return res;
}
```

#### [843. Guess the Word](https://leetcode.com/problems/guess-the-word/)

Narrow down the answer by guessing the score and update the list to ONLY keep the ones that have exact x matches with word. In this way, we narrow the candidates after we call master.guess(), and guarantee that secret is in candidates left. [Full explanation.](https://leetcode.com/problems/guess-the-word/discuss/556075/How-to-explain-to-interviewer-843.-Guess-the-Word)

T: O(n^2)

```java
public void findSecretWord(String[] wordlist, Master master) {
    Arrays.sort(wordlist);
    List<String> list = new ArrayList<>(Arrays.asList(wordlist));
    int score = -1;
    for (int i = 0; i < 10; i++) {
        score = master.guess(list.get(0));
        if (score == 6) return;
        list = updateList(list, list.get(0), score);
    }
}

private List<String> updateList(List<String> list, String target, int score) {
    List<String> res = new ArrayList<>();
    for (String s : list) {
        if (getSimilarityScore(s, target) == score) {
            res.add(s);
        }
    }
    return res;
}

private int getSimilarityScore(String s, String target) {
    int count = 0;
    for (int i = 0; i < Math.min(s.length(), target.length()); i++) {
        if (s.charAt(i) == target.charAt(i)) count++;
    }
    return count;
}
```

[316. Remove Duplicate Letters](https://leetcode.com/problems/remove-duplicate-letters/)

```java
public String removeDuplicateLetters(String s) {
    if (s.length() == 0) {
        return "";
    }

    int[] count = new int[26];
    for (char c : s.toCharArray()) {
        count[c - 'a']++;
    }

    int pos = 0;  // position of the smallest lex character
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) < s.charAt(pos)) {
            pos = i;
        }
        if (--count[s.charAt(i) - 'a'] == 0) {
            break;
        }
    }

    char ch = s.charAt(pos);
    String remaining = s.substring(pos + 1).replaceAll(String.valueOf(ch), "");
    return ch + removeDuplicateLetters(remaining);  
}
```

[1029. Two City Scheduling](https://leetcode.com/problems/two-city-scheduling/)

```java
int twoCitySchedCost(vector<vector<int>>& costs) {
    vector<int> refund;
    int N = costs.size()/2;
       int minCost = 0;
       for(vector<int> cost : costs){
        minCost += cost[0];
        refund.push_back(cost[1] - cost[0]); 
    }
    sort(refund.begin(), refund.end());
    for(int i = 0; i < N; i++){
        minCost += refund[i];
    }
    return minCost;
}
```

[1419. Minimum Number of Frogs Croaking](https://leetcode.com/problems/minimum-number-of-frogs-croaking/)

```java
class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
        int[] count = new int[5]; // c, r, o, a, k
        int frogs = 0;
        int maxFrogs = 0;
        
        for (char ch : croakOfFrogs.toCharArray()) {
            if (ch == 'c') {
                count[0]++;
                frogs++;
                maxFrogs = Math.max(maxFrogs, frogs);
            } else if (ch == 'r') {
                if (count[0] == 0) return -1;
                count[0]--;
                count[1]++;
            } else if (ch == 'o') {
                if (count[1] == 0) return -1;
                count[1]--;
                count[2]++;
            } else if (ch == 'a') {
                if (count[2] == 0) return -1;
                count[2]--;
                count[3]++;
            } else if (ch == 'k') {
                if (count[3] == 0) return -1;
                count[3]--;
                frogs--;
            } else {
                return -1; // invalid char
            }
        }
        
        // All counts except 'k' should be zero at the end
        if (frogs == 0) {
            return maxFrogs;
        } else {
            return -1; // incomplete croak
        }
    }
}

```

[1353. Maximum Number of Events That Can Be Attended](https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/)

Let the current day be $$i$$. At each day, we perform the following steps:

* Add to the candidate queue (the min-heap) all meetings whose start day is less than or equal to $$i$$. At this point, the heap contains all meetings available to attend on day $$i$$ or earlier.
* Remove from the heap all meetings whose end day is less than $$i$$, as they can no longer be attended.
* If the heap is not empty, we attend the meeting with the earliest end time (which is at the top of the heap), increment the count of attended meetings by $$1$$, and remove it from the heap.

Finally, return the total number of meetings attended.

{% tabs %}
{% tab title="First Tab" %}

```java
class Solution {
    public int maxEvents(int[][] events) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int max = 0;
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        for (int[] e : events) {
            max = Math.max(max, e[1]);
        }
        int res = 0;
        for (int day = 1, j = 0; day <= max; day++) {
            while (j < events.length && events[j][0] <= day) {
                pq.offer(events[j][1]);
                j++;
            }
            while (!pq.isEmpty() && pq.peek() < day) {
                pq.poll();
            }
            if (!pq.isEmpty()) {
                pq.poll();
                res++;
            }
        }
        return res;
    }
}
```

{% endtab %}
{% endtabs %}

[1005. Maximize Sum Of Array After K Negations](https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/)

{% tabs %}
{% tab title="Sort" %}

```cpp
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
       // Sort to process smallest (most negative) numbers first
        sort(nums.begin(), nums.end());
        
        // Negate negative numbers first (greedy approach)
        for (int i = 0; i < nums.size() && k > 0; ++i) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            } else {
                break; // No more negative numbers
            }
        }
        
        // If k is still positive and odd, negate the smallest element
        if (k > 0 && k % 2 == 1) {
            sort(nums.begin(), nums.end()); // Re-sort after negations
            nums[0] = -nums[0]; // Negate smallest element
        }
        
        // Calculate sum
        int sum = 0;
        for (int n : nums) {
            sum += n;
        }
        return sum;
    }
};
```

{% endtab %}

{% tab title="HashMap" %}

```cpp
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        map<int, int> freq; // value -> frequency
        
        // Count frequencies
        for (int num : nums) {
            freq[num]++;
        }
        
        // Process from smallest to largest
        for (auto& [val, count] : freq) {
            if (k == 0) break;
            
            if (val < 0) {
                // Negate as many negative numbers as possible
                int toNegate = min(k, count);
                freq[-val] += toNegate; // Add negated values
                count -= toNegate;      // Reduce current count
                k -= toNegate;
                
                if (count == 0) {
                    freq.erase(val); // Remove if no instances left
                }
            }
        }
        
        // If k is still positive and odd, negate smallest positive
        if (k > 0 && k % 2 == 1) {
            auto smallest = freq.begin();
            int smallestVal = smallest->first;
            int smallestCount = smallest->second;
            
            // Remove one instance of smallest
            if (smallestCount == 1) {
                freq.erase(smallest);
            } else {
                smallest->second--;
            }
            
            // Add one instance of its negation
            freq[-smallestVal]++;
        }
        
        // Calculate final sum
        int sum = 0;
        for (const auto& [val, count] : freq) {
            sum += val * count;
        }
        return sum;
    }
};
```

{% endtab %}
{% endtabs %}