Greedy Algorithms

• A greedy algorithm builds up a solution by choosing the option that looks the best at every step.
• Sometimes a greedy algorithm does not give you an optimal solution. For eg, To find the cheapest route visiting a set of cities, choosing to visit the cheapest city you haven’t been to yet doesn’t produce the cheapest overall itinerary.
• Validating that a greedy strategy always gets the best answer is tricky. Either prove that the answer produced by the greedy algorithm is as good as an optimal answer, or run through a rigorous set of test cases to convince your interviewer (and yourself) that its correct.

Qns 1

First, I wanna know how much money I could have made yesterday if I’d been trading Apple stocks all day.

So I grabbed Apple’s stock prices from yesterday and put them in a list called stock_prices, where:

• The indices are the time (in minutes) past trade opening time, which was 9:30am local time.
• The values are the price (in US dollars) of one share of Apple stock at that time.

So if the stock cost $500 at 10:30am, that means stock_prices[60] = 500.

Write an efficient function that takes stock_prices and returns the best profit I could have made from one purchase and one sale of one share of Apple stock yesterday.

No “shorting” — you need to buy before you can sell. Also, you can’t buy and sell in the same time step — at least 1 minute has to pass.

Gotchas: You cannot just take the difference between the highest price and lowest price as the highest price might come before the lowest price. You have to buy before you sell.

Solution: Keep track of the lowest value so far. Then as you traverse through all the stock prices, calculate the profit you can get. Compare and update maxProfit variable accordingly.

Leetcode Extension:

122. Best Time to Buy and Sell Stock II

Say you have an array prices for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Given that we can complete as many transactions as possible, we can keep buying and selling at every point where we can make a gain.

The approach 3 of the solution given by leetcode is good.

Leetcode Extension:

123. Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Example 4:

Input: prices = [1]
Output: 0

The idea is to visualise the given input prices to be segmented into two parts, T1 and T2 as seen above. We then compute the max profit we can get on both segments T1 and T2 as we move from one index k strating from 0 to the end of the array.

We have 2 int arrays. Profit1[k] track the max profit earned on the left segment of the current index k and Profit2[k] store the max profit earned on the right segment of the current index k. (Both are inclusive).

At the end, when we have finished computing, we can just find the index that has the highest sum of Profit1[j] + Profit2[j].

We compute it normally like buy stock part I except that we also do for RHS.

188. Best Time to Buy and Sell Stock IV

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Notice that you may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

DP Solution

https://www.youtube.com/watch?v=Pw6lrYANjz4

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/discuss/54113/A-Concise-DP-Solution-in-Java

Leet Code Solution

Leet Code Discussion Solution

Over here, we see that we can store the results when we were calculating for profit[t][d-1] as there are some repeated computation.

dp[i][j] = maximum profit from at most i transactions using prices[0..j]

A transaction is defined as one buy + sell.

Now on day j, we have two options

1. Do nothing which doesn’t change the acquired profit : dp[i][j] = dp[i][j-1]
2. Sell the stock: In order to sell the stock, you must’ve bought it at an earlier price (positions before j)t=[0..j-1]. Current index is j. Maximum profit that can be attained from the previous pricingt=0->j-1 isMAX(prices[j]-prices[t]+dp[i-1][t-1]) where prices[j]-prices[t] is the profit from buying on day t and selling on day j. dp[i-1][t-1] is the maximum profit that can be made with at most i-1 transactions with prices prices[0..t-1].

Time complexity of this approach is O(n2k).

In order to reduce it to O(nk), we must find t:0->j-1 max(prices[j]-prices[t]+dp[i-1][t-1]) this expression in constant time. If you see carefully,

t:0->j-1, max(prices[j]-prices[t]+dp[i-1][t-1]) is same as

prices[j] + t:0->j-1 max(dp[i-1][t-1]-prices[t])

Second part of the above expression maxTemp = t:0->j-1 max(dp[i-1][t-1]-prices[t]) can be included in the dp loop by keeping track of the maximum value till j-1. Track pricings from made with i-1 number of Xacts and from 1,2…j-1 pricing.

Base case:

dp[0][j] = 0; dp[i][0] = 0

DP loop:

for i : 1 -> k
maxTemp = -prices[0];
for j : 1 -> n-1
dp[i][j] = max(dp[i][j-1], prices[j]+maxTemp);
maxTemp = max(maxTemp, dp[i-1][j-1]-prices[j]);
return dp[k][n-1];

309. Best Time to Buy and Sell Stock with Cooldown

TODO

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

TODO

Qns 2 Given a list of integers, find the highest product you can get from three of the integers.

Qns 3: You have a list of integers, and for each index you want to find the product of every integer except the integer at that index.

Write a function get_products_of_all_ints_except_at_index() that takes a list of integers and returns a list of the products.

For example, given:

[1, 7, 3, 4]

your function would return:

[84, 12, 28, 21]

by calculating:

[7 * 3 * 4,  1 * 3 * 4,  1 * 7 * 4,  1 * 7 * 3]

Here’s the catch: You can’t use division in your solution!

Qns 4: Given all three lists, write a function to check that my service is first-come, first-served. All food should come out in the same order customers requested it.

We’ll represent each customer order as a unique integer.

As an example,

Take Out Orders: [1, 3, 5]
 Dine In Orders: [2, 4, 6]
  Served Orders: [1, 2, 4, 6, 5, 3]

would not be first-come, first-served, since order 3 was requested before order 5 but order 5 was served first.

But,

Take Out Orders: [17, 8, 24]
 Dine In Orders: [12, 19, 2]
  Served Orders: [17, 8, 12, 19, 24, 2]

would be first-come, first-served.

Qns 5: Write a function for doing an in-place shuffle of a list. The shuffle must be “uniform,” meaning each item in the original list must have the same probability of ending up in each spot in the final list.

Assume that you have a function get_random(floor, ceiling) for getting a random integer that is >= floor and <= ceiling.

An in-place function modifies data structures or objects outside of its own stack frame ↴ (i.e.: stored on the process heap or in the stack frame of a calling function). Because of this, the changes made by the function remain after the call completes.

“In-place” does not mean “without creating any additional variables!” Rather, it means “without creating a new copy of the input.” In general, an in-place function will only create additional variables that are O(1)O(1) space.

Solution:

If we didn’t have the “in-place” requirement, we could allocate a new list, then one-by-one take a random item from the input list, remove it, put it in the first position in the new list, and keep going until the input list is empty (well, probably a copy of the input list — best not to destroy the input)

How can we adapt this to be in place?

What if we make our new “random” list simply be the front of our input list?

map.getOrDefault()

default V getOrDefault(Object key, V defaultValue)

Returns the value to which the specified key is mapped, or defaultValue if this map contains no mapping for the key.

Qns 6 (LeetCode 316): Remove Duplicate Letters

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example 1:

Input: "bcabc"
Output: "abc"

Example 2:

Input: "cbacdcbc"
Output: "acdb"

The check for whether the current character has already been added into the String needs to be at the top of the code. Otherwise, it fails the test case abacb where it returns acb as the answer.

Qns 7 (Leetcode 910) Smallest Range II

Given an array A of integers, for each integer A[i] we need to choose either x = -K or x = K, and add x to A[i] (only once).

After this process, we have some array B.

Return the smallest possible difference between the maximum value of B and the minimum value of B.

Solution: The solution is to do a linear scan. (Greedy qns tend to involve sorting and doing linear scanning).

The intuition is that the smaller A[i] will do a +k while the bigger A[j] will do a -K.

If A[i] < A[j], we don't need to consider when A[i] goes down while A[j] goes up. This is because the interval (A[i] + K, A[j] - K) is a subset of (A[i] - K, A[j] + K.

That means that it is never worse to choose (up, down) instead of (down, up). We can prove this claim that one interval is a subset of another, by showing both A[i] + K and A[j] - K are between A[i] - K and A[j] + K.

For sorted A, say A[i] is the largest i that goes up. Then A[0] + K, A[i] + K, A[i+1] - K, A[A.length - 1] - K are the only relevant values for calculating the answer: every other value is between one of these extremal values.

(Leetcode 402) Qns 8: Remove K Digits

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

• The length of num is less than 10002 and will be ≥ k.
• The given num does not contain any leading zero.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

Idea:

Brute force:

• Try to remove the k digits anyhow…

Other:

• Note that the ordering of the digits have to be preserved. So cannot do sorting. Need to go from left to right.
• If the first char is 0, need to ignore it at the end when returning.
• Note the pattern. The pattern is that whenever we see values at indices X and X+1, if X+1 is smaller than X, then it means that X is bigger. We should remove X.
• Note that we cannot remove all the topmost biggest values because the number in the leftmost has the heaviest weight. So we should just remove the values as soon as we see that it is a peak. (not whether it is the highest peak)
• Data structure: Stack

Solution:

Qns 9: Group the people given the group size they belong

This question is not too difficult -> Think of hashmap

Map<String, String> map = new HashMap<>();

for (Map.Entry<String, String> entry : map.entrySet()) {
	System.out.println("[Key] : " + entry.getKey() + " [Value] : " + entry.getValue());
}

There are n people whose IDs go from 0 to n - 1 and each person belongs exactly to one group. Given the array groupSizes of length n telling the group size each person belongs to, return the groups there are and the people's IDs each group includes.

You can return any solution in any order and the same applies for IDs. Also, it is guaranteed that there exists at least one solution.

Example 1:

Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation: 
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

Example 2:

Input: groupSizes = [2,1,3,3,3,2]
Output: [[1],[0,5],[2,3,4]]

1717. Maximum Score From Removing Substrings

You are given a string s and two integers x and y. You can perform two types of operations any number of times.

• Remove substring "ab" and gain x points.
• For example, when removing "ab" from "cabxbae" it becomes "cxbae".
• Remove substring "ba" and gain y points.
• For example, when removing "ba" from "cabxbae" it becomes "cabxe".

Return the maximum points you can gain after applying the above operations on s.

Example 1:

Input: s = "cdbcbbaaabab", x = 4, y = 5
Output: 19
Explanation:
- Remove the "ba" underlined in "cdbcbbaaabab". Now, s = "cdbcbbaaab" and 5 points are added to the score.
- Remove the "ab" underlined in "cdbcbbaaab". Now, s = "cdbcbbaa" and 4 points are added to the score.
- Remove the "ba" underlined in "cdbcbbaa". Now, s = "cdbcba" and 5 points are added to the score.
- Remove the "ba" underlined in "cdbcba". Now, s = "cdbc" and 5 points are added to the score.
Total score = 5 + 4 + 5 + 5 = 19.

Example 2:

Input: s = "aabbaaxybbaabb", x = 5, y = 4
Output: 20

Constraints:

• 1 <= s.length <= 105
• 1 <= x, y <= 104
• s consists of lowercase English letters.

(Editorial)

Approach 3: Greedy Way (Counting)

Intuition

Notice that in previous approaches, removing substrings from the input string posed as the bottleneck to better performance. Instead of removing the substrings, can we count the number of substrings that can be potentially removed, and count the total score from there?

Let’s consider a case where “ab” is the higher-scoring substring. To find the score, we need to form pairs of the characters a and b, where:

• If we encounter b and have previously seen an a, we can form an "ab" pair.
• If we encounter a and have previously seen a b, we can form a "ba" pair.

But, how do we ensure that the score is maximum? That’s where the greedy strategy comes in:

Let’s use aCount and bCount to keep track of unpaired 'a's and 'b's respectively.

1. When we come across an a, we simply increment aCount. We don't immediately pair it because a future 'b' might form a higher-scoring "ab" pair.
2. When we encounter a b, we have two choices. If there's an unpaired a available (aCount > 0), we immediately form an "ab" pair, decrement aCount, and add points, since this is the most profitable option. Otherwise, we increment bCount for potential future "ba" pairs.
3. When we encounter a non a or b character, it acts as a barrier. We form as many "ba" pairs as possible, add the points, and reset the counters. This segmentation ensures we don't incorrectly pair across these barriers.

However, all of this is valid when “ab” is the higher-scoring substring. What if “ba” is the more profitable one? An easy trick to fix this is to simply reverse the given string s and flip the values of x and y. Since the order of counting does not matter, all "ba" substrings present in s are now "ab" and vice-versa.

class Solution {

    public int maximumGain(String s, int x, int y) {
        // Ensure "ab" always has higher points than "ba"
        if (x < y) {
            // Swap points
            int temp = x;
            x = y;
            y = temp;
            // Reverse the string to maintain logic
            s = new StringBuilder(s).reverse().toString();
        }

        int aCount = 0, bCount = 0, totalPoints = 0;

        for (int i = 0; i < s.length(); i++) {
            char currentChar = s.charAt(i);

            if (currentChar == 'a') {
                aCount++;
            } else if (currentChar == 'b') {
                if (aCount > 0) {
                    // Can form "ab", remove it and add points
                    aCount--;
                    totalPoints += x;
                } else {
                    // Can't form "ab", keep 'b' for potential future "ba"
                    bCount++;
                }
            } else {
                // Non 'a' or 'b' character encountered
                // Calculate points for any remaining "ba" pairs
                totalPoints += Math.min(bCount, aCount) * y;
                // Reset counters for next segment
                // BECAUSE YOU CAN'T REMOVE ANY AB OR BC...
                // SEE THE SIMULATION FOR EASIER UNDERSTANDING
                aCount = bCount = 0;
            }
        }

        // Calculate points for any remaining "ba" pairs at the end
        totalPoints += Math.min(bCount, aCount) * y;

        return totalPoints;
    }
}

Complexity Analysis

Let n be the length of the given string s.

• Time complexity: O(n)
• The algorithm reverses the string in the worst case and iterates over each character of the string exactly once, with each operation taking O(n) time. Therefore, the time complexity of the algorithm is O(n).
• Space complexity: O(1) or O(n)
• In the C++ implementation of the algorithm, the string reversal takes constant space since reverse() flips the string in-place.
• For the Java and Python3 implementations, the string reversal requires O(n) space.
• We do not use any other data structures that scale with the input size. Therefore, the space complexity of the algorithm is O(1) for C++, and O(n) for Java and Python3.

The End for now :)