You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
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.
Example 2:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
1 <= prices.length <= 1050 <= prices[i] <= 104The key idea in #121 Best Time to Buy and Sell Stock is to determine the maximum profit that can be achieved from a single buy and sell transaction. Since the prices are given as an Array, a brute force approach would try every pair of days where the buy day comes before the sell day. While this works conceptually, it leads to unnecessary comparisons and becomes inefficient for large inputs.
A more optimal strategy uses a single-pass greedy / dynamic programming insight. As you iterate through the array, track the minimum price seen so far and compare it with the current day's price to estimate the potential profit. By continuously updating the best profit encountered, you avoid recomputing earlier possibilities.
This method effectively transforms the problem into maintaining two running values: the lowest buying price and the maximum profit achievable so far. The approach runs in O(n) time with O(1) extra space, making it efficient for interview settings.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force (check all buy-sell pairs) | O(n^2) | O(1) |
| Single Pass Greedy / DP Insight | O(n) | O(1) |
NeetCode
In this approach, we traverse the prices array while keeping track of the minimum price seen so far and calculate the maximum profit we could achieve if we sold on that day. The maximum profit is updated accordingly through each iteration.
This approach makes a single pass through the array (O(n) time complexity) and uses constant space (O(1) space complexity).
Time Complexity: O(n), where n is the number of days.
Space Complexity: O(1).
1#include <iostream>
2#include <vector>
3
4int maxProfit(std::vector<int>& prices) {
5 if (prices.empty()) return 0;
6 int min_price = prices[0];
7 int max_profit = 0;
8 for (int i = 1; i < prices.size(); i++) {
9 min_price = std::min(min_price, prices[i]);
10 max_profit = std::max(max_profit, prices[i] - min_price);
11 }
12 return max_profit;
13}
14
int main() {
std::vector<int> prices = {7, 1, 5, 3, 6, 4};
std::cout << "Max Profit: " << maxProfit(prices) << std::endl;
return 0;
}This C++ solution uses a similar logic, utilizing STL functions like std::min and std::max to update the minimum price and maximum profit respectively while iterating through the array.
This approach considers all possible pairs of buy and sell days, calculating the profit for each combination. It is straightforward but inefficient due to its O(n^2) time complexity, which is impractical for large inputs.
Time Complexity: O(n^2), where n is the number of days.
Space Complexity: O(1).
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is commonly asked in coding interviews at FAANG and other top tech companies. It tests a candidate’s ability to recognize greedy patterns, optimize brute force solutions, and work efficiently with arrays.
The problem primarily uses an array of stock prices. No additional complex data structures are required because the optimal solution only keeps track of a running minimum price and the maximum profit encountered so far.
The optimal approach uses a single pass through the array while tracking the minimum price seen so far. At each step, you calculate the potential profit if the stock were sold that day and update the maximum profit. This greedy idea leads to O(n) time and O(1) space complexity.
The problem can be interpreted as a dynamic programming pattern where the best profit up to each day depends on earlier information. However, the DP state can be simplified into tracking the minimum price and current best profit, reducing space to O(1).
This C implementation uses nested loops to check all possible buy and sell day pairs, computing the profit and tracking the highest encountered. It serves as an illustration of the brute force method.