Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
Be sure that you clarify the input and output parameters of the problem:
O(n)
time and O(1)
space will do. Run through a set of example cases:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
EDGE CASE
Input: cost = [1]
Output: 0
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Bottom-Up DP Technique, we will build up our answer. We will store the minimum cost at each date and check for maximum profit sold.
1. Create variables to hold minimum prices and maximum profit
2. As we progress through the array of prices
a. Record the minimum price and build minimum prices array as we proceed through the array
b. Check for a higher profit
3. Return the maximum profit.
General Idea: Bottom-Up DP Technique, we will build up our answer. We will maintain only the minimum cost at each date and check for maximum profit sold.
1. Create variables to hold minimum price and maximum profit
2. As we progress through the array of prices
a. Record the minimum price found as we proceed through the array
b. Check for a higher profit
3. Return the maximum profit.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
Solution 1: Bottom-Up DP Technique, we will build up our answer. We will store the minimum cost at each date and check for maximum profit sold.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# Create variables to hold minimum prices and maximum profit
maxProfit = 0
memoMinPrice = [prices[0]]
# As we progress through the array of prices
for i in range(len(prices)):
# Record the minimum price and build minimum price as we proceed through the array
memoMinPrice.append(min(prices[i], memoMinPrice[i]))
# Check for a higher profit
maxProfit = max(maxProfit, prices[i] - memoMinPrice[i])
# Return the maximum profit.
return maxProfit
class Solution {
public int maxProfit(int[] prices) {
// Create variables to hold minimum prices and maximum profit
int[] memoMinPrice = new int[prices.length + 1];
memoMinPrice[0] = prices[0];
int maxProfit = 0;
// As we progress through the array of prices
for (int i = 0; i < prices.length; i++) {
// Record the minimum price found as we proceed through the array
memoMinPrice[i + 1] = (Math.min(memoMinPrice[i], prices[i]));
// Check for a higher profit
maxProfit = Math.max(maxProfit, prices[i] - memoMinPrice[i]);
}
// Return the maximum profit.
return maxProfit;
}
}
Solution 2: Bottom-Up DP Technique, we will build up our answer. We will maintain only the minimum cost at each date and check for maximum profit sold.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# Create variables to hold minimum prices and maximum profit
maxProfit = 0
minPrice = prices[0]
# As we progress through the array of prices
for price in prices:
# Record the minimum price found as we proceed through the array
minPrice = min(price, minPrice)
# Check for a higher profit
maxProfit = max(maxProfit, price - minPrice)
# Return the maximum profit.
return maxProfit
class Solution {
public int maxProfit(int[] prices) {
// Create variables to hold minimum prices and maximum profit
int minValue = prices[0];
int maxProfit = 0;
// As we progress through the array of prices
for (int i = 0; i < prices.length; i++) {
// Record the minimum price found as we proceed through the array
minValue = Math.min(minValue, prices[i]);
// Check for a higher profit
maxProfit = Math.max(maxProfit, prices[i] - minValue);
}
// Return the maximum profit.
return maxProfit;
}
}
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the number of item in the array
Solution 1: Bottom-Up DP Technique, we will build up our answer. We will store the minimum cost at each date and check for maximum profit sold.
O(N)
, because we need to build up to check each item in the array.O(N)
, because we held array of information regarding minPrice at each index.Solution 2: Bottom-Up DP Technique, we will build up our answer. We will maintain only the minimum cost at each date and check for maximum profit sold.
O(N)
, because we need to build up to check each item in the array.O(1)
, because we held 2 pieces of information minPrice and maxProfit.