Introduction to the Best Time to Buy and Sell Stock Problem
The "Best Time to Buy and Sell Stock" problem is one of the most iconic algorithmic challenges you will encounter on platforms like LeetCode, in technical interviews, and in coding bootcamps. At its core, the problem asks you to determine the maximum profit you can achieve by buying and selling a single share of a stock, given an array of daily prices. You may only complete one transaction, and you must buy before you sell.
While the problem statement is deceptively simple, it teaches fundamental concepts such as array traversal, tracking running minimums, and recognizing when a brute-force solution can be optimized into a single-pass linear time algorithm. In this tutorial, we will walk through the problem in Go, explore multiple approaches, and discuss best practices for writing clean, idiomatic Go code.
What Is the Best Time to Buy and Sell Stock Problem?
Given an array prices where prices[i] represents the price of a given stock on day i, your goal is to maximize profit by choosing a single day to buy and a different, later day to sell. If no profit is possible, you should return zero.
For example, consider the input [7, 1, 5, 3, 6, 4]. The optimal strategy is to buy on day 1 (price = 1) and sell on day 4 (price = 6), yielding a profit of 5. Note that buying on day 2 and selling on day 3 would only yield a profit of 4, which is suboptimal.
Formal Problem Statement
- Input: an array of integers
pricesrepresenting stock prices on consecutive days. - Output: an integer representing the maximum profit achievable with at most one transaction.
- Constraint: you must buy before you sell; if no profit is possible, return 0.
Why This Problem Matters
This problem matters because it forces you to think about efficiency. A naive solution that compares every pair of buy and sell days runs in O(n²) time, which becomes unacceptable for large datasets. The optimal solution runs in O(n) time and O(1) space, demonstrating how a clever insight can dramatically reduce computational cost.
Beyond interviews, the underlying technique—tracking a running minimum while computing a running maximum—appears in many real-world scenarios. These include streaming analytics, financial dashboards, sensor data processing, and any situation where you need to compute derived metrics over a sequence of values in a single pass.
Approach 1: Brute Force
The brute-force approach is the most intuitive. For each day, consider it as a potential buy day, then iterate over all subsequent days as potential sell days. Track the maximum profit encountered.
package main
import "fmt"
func maxProfitBruteForce(prices []int) int {
maxProfit := 0
n := len(prices)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
profit := prices[j] - prices[i]
if profit > maxProfit {
maxProfit = profit
}
}
}
return maxProfit
}
func main() {
prices := []int{7, 1, 5, 3, 6, 4}
fmt.Println("Max profit (brute force):", maxProfitBruteForce(prices))
}
This solution is correct but inefficient. With nested loops, the time complexity is O(n²), and for an input of one million prices, this could mean a trillion operations. We can do much better.
Approach 2: Single-Pass Linear Scan
The key insight is that we only need to track two values as we iterate through the array: the minimum price seen so far, and the maximum profit achievable. For each day, we calculate what the profit would be if we sold at the current price after buying at the minimum price seen so far. We then update the minimum price if the current price is lower.
package main
import "fmt"
func maxProfit(prices []int) int {
if len(prices) == 0 {
return 0
}
minPrice := prices[0]
maxProfit := 0
for i := 1; i < len(prices); i++ {
if prices[i] < minPrice {
minPrice = prices[i]
} else {
profit := prices[i] - minPrice
if profit > maxProfit {
maxProfit = profit
}
}
}
return maxProfit
}
func main() {
prices := []int{7, 1, 5, 3, 6, 4}
fmt.Println("Max profit:", maxProfit(prices))
}
This approach runs in O(n) time and uses O(1) extra space. It is the canonical solution and the one you should aim to produce in an interview setting.
How the Algorithm Works Step by Step
Let us trace through the input [7, 1, 5, 3, 6, 4] to understand the algorithm:
- Day 0: price = 7, minPrice = 7, maxProfit = 0.
- Day 1: price = 1, lower than minPrice, so minPrice = 1.
- Day 2: price = 5, profit = 5 - 1 = 4, maxProfit = 4.
- Day 3: price = 3, profit = 3 - 1 = 2, maxProfit stays 4.
- Day 4: price = 6, profit = 6 - 1 = 5, maxProfit = 5.
- Day 5: price = 4, profit = 4 - 1 = 3, maxProfit stays 5.
The final answer is 5, which matches our expected result.
Approach 3: Using Go's Built-in Math Functions
For readability, you can leverage Go's math package to compute minimums and maximums. However, note that math.Min and math.Max operate on float64 values, so you will need type conversions. Alternatively, Go 1.21 introduced the min and max built-in functions that work directly with integers.
package main
import "fmt"
func maxProfitBuiltins(prices []int) int {
if len(prices) == 0 {
return 0
}
minPrice := prices[0]
maxProfit := 0
for _, price := range prices[1:] {
minPrice = min(minPrice, price)
maxProfit = max(maxProfit, price-minPrice)
}
return maxProfit
}
func main() {
prices := []int{7, 1, 5, 3, 6, 4}
fmt.Println("Max profit (builtins):", maxProfitBuiltins(prices))
}
This version is more concise and arguably easier to read. The min and max built-ins, available in Go 1.21 and later, eliminate the need for manual comparisons and reduce the chance of bugs.
Handling Edge Cases
Robust code must handle edge cases gracefully. Consider the following scenarios:
- An empty prices array: there is nothing to buy or sell, so return 0.
- A single-element array: you cannot sell after buying, so return 0.
- A strictly decreasing array: no profit is possible, so return 0.
- A strictly increasing array: buy on the first day and sell on the last.
package main
import "fmt"
func maxProfitRobust(prices []int) int {
if len(prices) < 2 {
return 0
}
minPrice := prices[0]
maxProfit := 0
for _, price := range prices {
if price < minPrice {
minPrice = price
}
profit := price - minPrice
if profit > maxProfit {
maxProfit = profit
}
}
return maxProfit
}
func main() {
testCases := [][]int{
{},
{5},
{7, 6, 4, 3, 1},
{1, 2, 3, 4, 5},
{7, 1, 5, 3, 6, 4},
}
for _, tc := range testCases {
fmt.Printf("maxProfit(%v) = %d\n", tc, maxProfitRobust(tc))
}
}
Running this code produces the expected outputs for each edge case, confirming that the algorithm is resilient to unusual inputs.
Writing Testable Code
In professional Go development, you should always write tests. Go's built-in testing framework makes this straightforward. Place your function in a file named stock.go and your tests in stock_test.go.
// stock.go
package stock
func MaxProfit(prices []int) int {
if len(prices) < 2 {
return 0
}
minPrice := prices[0]
maxProfit := 0
for _, price := range prices {
if price < minPrice {
minPrice = price
}
profit := price - minPrice
if profit > maxProfit {
maxProfit = profit
}
}
return maxProfit
}
// stock_test.go
package stock
import "testing"
func TestMaxProfit(t *testing.T) {
tests := []struct {
name string
prices []int
expected int
}{
{"empty array", []int{}, 0},
{"single element", []int{5}, 0},
{"decreasing prices", []int{7, 6, 4, 3, 1}, 0},
{"increasing prices", []int{1, 2, 3, 4, 5}, 4},
{"standard case", []int{7, 1, 5, 3, 6, 4}, 5},
{"buy at lowest", []int{2, 4, 1}, 2},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
result := MaxProfit(tt.prices)
if result != tt.expected {
t.Errorf("MaxProfit(%v) = %d, want %d",
tt.prices, result, tt.expected)
}
})
}
}
Run the tests with go test -v to verify that your implementation handles all cases correctly. Table-driven tests like this are idiomatic in Go and make it easy to add new cases as you discover them.
Best Practices for Solving This Problem in Go
1. Validate Inputs Early
Always check for empty or single-element arrays at the start of your function. This prevents unnecessary work and avoids potential panics when accessing prices[0].
2. Prefer Single-Pass Algorithms
Whenever possible, look for opportunities to solve problems in a single pass. The transition from O(n²) to O(n) is often the difference between a solution that scales and one that does not.
3. Use Idiomatic Go Constructs
Use range loops instead of index-based loops when you do not need the index. Use the min and max built-ins if you are targeting Go 1.21 or later. Keep your functions short and focused.
4. Write Table-Driven Tests
Table-driven tests are a Go convention. They make it trivial to add new test cases and provide clear documentation of expected behavior. Always include edge cases in your test suite.
5. Benchmark Your Solutions
For performance-critical code, use Go's benchmarking tools to measure execution time. This is especially useful when comparing the brute-force and single-pass approaches.
package stock
import "testing"
func BenchmarkMaxProfit(b *testing.B) {
prices := make([]int, 100000)
for i := range prices {
prices[i] = 100000 - i
}
for i := 0; i < b.N; i++ {
MaxProfit(prices)
}
}
Run benchmarks with go test -bench=. to see how your implementation performs under load.
Common Variations of the Problem
Once you understand the basic problem, you can explore variations that appear in interviews and on coding platforms:
- Multiple transactions: You may complete as many transactions as you want, but you cannot hold multiple positions simultaneously.
- At most two transactions: You may complete at most two non-overlapping transactions.
- With cooldown: After selling, you must wait one day before buying again.
- With transaction fee: Each transaction incurs a fixed fee.
Each variation requires a different approach, often involving dynamic programming or state machines. Mastering the basic single-transaction problem is a prerequisite for tackling these more advanced versions.
Conclusion
The Best Time to Buy and Sell Stock problem is a fantastic exercise in algorithmic thinking and Go programming. By starting with a brute-force solution and refining it into a single-pass O(n) algorithm, you learn how to identify inefficiencies and apply elegant optimizations. Along the way, you practice idiomatic Go patterns such as range loops, table-driven tests, and input validation. Whether you are preparing for an interview or building a financial application, the techniques covered in this tutorial will serve you well. Remember to always validate your inputs, write comprehensive tests, and benchmark your code when performance matters. With these practices in place, you will be well-equipped to solve not only this problem but also the many variations that build upon it.