⚡ TL;DR
Solve LeetCode
Best Time to Buy and Sell Stock (LeetCode #121) is a classic dynamic programming problem: given daily stock prices, find the maximum profit from one buy-sell transaction.
Problem Statement
Given an array prices where prices[i] is the price of a stock on day i, find the maximum profit you can achieve. You can only complete one transaction (buy once, sell once). Note you cannot sell before buying.
Examples:
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.
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: No profit possible since prices always decrease.Approach 1: Brute Force (O(n²))
Try every buy-sell pair where buy comes before sell.
int maxProfitBrute(List<int> prices) {
int maxProfit = 0;
int n = prices.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int profit = prices[j] - prices[i];
if (profit > maxProfit) {
maxProfit = profit;
}
}
}
return maxProfit;
}
void main() {
print(maxProfitBrute([7,1,5,3,6,4])); // 5
print(maxProfitBrute([7,6,4,3,1])); // 0
}Time: O(n²) — too slow for interviews
Space: O(1)
Approach 2: Single Pass (Optimal)
Track the minimum price seen so far, and update max profit at each step.
int maxProfit(List<int> prices) {
if (prices.isEmpty) return 0;
int minPrice = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
// Update minimum price seen so far
if (prices[i] < minPrice) {
minPrice = prices[i];
}
// Update max profit if selling today gives better profit
else if (prices[i] - minPrice > maxProfit) {
maxProfit = prices[i] - minPrice;
}
}
return maxProfit;
}
void main() {
print(maxProfit([7,1,5,3,6,4])); // 5
print(maxProfit([7,6,4,3,1])); // 0
print(maxProfit([2,4,1])); // 2
}Time: O(n) — single pass
Space: O(1)
How it works:
- Track lowest price to buy at (
minPrice) - Calculate profit if selling at current price (
prices[i] - minPrice) - Update max profit if current profit is higher
Approach 3: Dynamic Programming (Educational)
For conceptual understanding, define DP state:
dp[i]= maximum profit achievable by dayi
import 'dart:math';
int maxProfitDP(List<int> prices) {
if (prices.isEmpty) return 0;
int n = prices.length;
List<int> dp = List.filled(n, 0);
int minPrice = prices[0];
for (int i = 1; i < n; i++) {
minPrice = min(minPrice, prices[i]);
dp[i] = max(dp[i - 1], prices[i] - minPrice);
}
return dp[n - 1];
}
void main() {
print(maxProfitDP([7,1,5,3,6,4])); // 5
}Time: O(n)
Space: O(n) for DP array — can be optimized to O(1) by tracking only the previous day.
Dart-Specific Tips
List.filled(n, 0)creates a fixed-size listmin(a, b)andmax(a, b)fromdart:mathreturn minimum/maximum of two values (remember toimport 'dart:math';)- Use
isEmptyandisNotEmptyinstead oflength == 0 - Dart lists are 0-indexed like Python/Java
Complexity Comparison
| Approach | Time | Space | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Rarely accepted in interviews |
| Single Pass | O(n) | O(1) | ✅ Best for production code |
| Dynamic Programming | O(n) | O(n) | Educational, can be optimized to O(1) |
Follow-Up Problems
- Best Time to Buy and Sell Stock II (#122) — unlimited transactions (accumulate all positive slopes)
- Best Time with Cooldown (#309) — after sell, must skip one day
- Best Time with Fee (#714) — subtract fee per transaction
Master #121 first — it’s the building block for all harder variants.
FAQ
What is the best approach to solve Best Time to Buy and Sell Stock in Dart?
The recommended approach is the optimal approach, which runs in O(n²) time with O(1) space. The full Dart implementation is shown above.
What is the time complexity of Best Time to Buy and Sell Stock in Dart?
Using the optimal approach, the time complexity is O(n²) and the space complexity is O(1).
