Maximum Profit
You and your friend have decided to start an international trading business. You want to earn a profit through some ol' fashioned arbitrage: You'll buy widgets in one country and sell them in another at a higher price. Your friend has already found the current market prices for widgets in cities around the world, and you'd like to use this data to pick which cities to buy and sell widgets in.
Write a function max_profit(prices) that efficiently finds the two cities that maximize your profit (i.e. largest difference in prices).
Input: A dictionary with cities as keys and prices as values Output: An array containing the names of the cities (min, max)
If the prices dictionary is empty, return None/null (depending on the programming language used). If there is 0 profit to be earned, return None/null as well. If you are using C++, return {"", ""} in such cases.
Example
Pythonprices = {'London': 72, 'New York': 70, 'Tokyo': 67, 'Miami': 62} max_profit(prices) # => ['Miami', 'London']
You can think of this as two sub-problems: Finding the lowest price, and finding the highest price.
While you could compare every pair of cities, it's more efficient to find the min and max values.
You can keep track of the lowest and highest values and update them as you iterate through the list.
Does your solution work in O(N) time and O(1) space? If not, you can be more efficient!
What happens if the price is the same in every city? Does your function still return different cities?
For our solution, we'll simply iterate through the prices list and simultaneously keep track of the minimum and maximum values we've seen so far. This only requires one iteration, so it's more efficient than the 'brute force' approach of calculating the profit for each pair of cities, which would require O(n^2) time.
def max_profit(prices):
# Check if the dictionary is empty
if not prices:
return None
min_city = None
max_city = None
min_price = float("inf")
max_price = -1
for city, price in prices.items():
if price < min_price:
min_price = price
min_city = city
if price > max_price:
max_price = price
max_city = city
# Check if there is no profit opportunity
if min_price == max_price:
return None
return [min_city, max_city]A more concise—but slightly less efficient solution—would be to sort the cities according to their prices and then return the first and last elements. In some languages like Python, you can also use the built-in min and max functions to compare dictionary values:
Pythondef max_profit(prices):
# Check if the dictionary is empty
if not prices:
return None
min_city = min(prices, key=prices.get)
max_city = max(prices, key=prices.get)
# Check if no profits earned
if min_city == max_city:
return None
return [min_city, max_city]
Time Complexity: Iterating over prices.items() takes O(n) time, where n is the number of cities in the prices dictionary. Within the loop, there are constant-time operations, so the overall time complexity is O(n).
Space Complexity: The space complexity is also O(1) because the size of the auxiliary array returned ([min_city, max_city]) is constant and independent of the input size.
from typing import Dict, List, Optional def max_profit(prices: Dict[str, int]) -> Optional[List[str]]: pass # your code goes here max = [None, 0] min = [None, float("inf")] for city, price in prices.items(): if price > max[1]: max[0], max[1] = city, price if price < min[1]: min[0], min[1] = city, price if max[1] - min[1] > 0: return [min[0], max[0]] return None # debug your code below prices = {'London': 72, 'New York': 70, 'Tokyo': 67, 'Miami': 62} print(max_profit(prices))