⚡ TL;DR
Solve Best Time to Buy and Sell Stock in Go with working code. One-Pass Min Tracking (Optimal) approach with O(n) time, plus complexity analysis and interview tips.
Best Time to Buy and Sell Stock (#121 — Easy): Given an array prices where prices[i] is the price of a stock on day i, choose one day to buy and a different later day to sell to maximize profit. Return that maximum profit, or 0 when no profitable trade exists.
Problem Statement
Given an array prices where prices[i] is the price of a stock on day i, choose one day to buy and a different later day to sell to maximize profit. Return that maximum profit, or 0 when no profitable trade exists.
Example:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1), sell on day 5 (price = 6), profit = 6 − 1 = 5.Approach: One-Pass Min Tracking (Optimal)
Time: O(n) | Space: O(1)
Walk the prices once while remembering the cheapest price seen so far. At each day the best possible trade selling today is today’s price minus that minimum, so update the answer on the fly.
package main
import ("fmt")
func maxProfit(prices []int) int {
minPrice := prices[0]
best := 0
for _, price := range prices[1:] {
if price < minPrice {
minPrice = price
} else if price-minPrice > best {
best = price - minPrice
}
}
return best
}
func main() {
fmt.Println(maxProfit([]int{7, 1, 5, 3, 6, 4}))
}
Approach: Brute Force
Time: O(n²) | Space: O(1)
Try every buy-day/sell-day pair, keep the largest positive difference, and return it. Straightforward but quadratic, which fails on large inputs.
package main
import ("fmt")
func maxProfitBrute(prices []int) int {
best := 0
for i := 0; i < len(prices); i++ {
for j := i + 1; j < len(prices); j++ {
if prices[j]-prices[i] > best {
best = prices[j] - prices[i]
}
}
}
return best
}
func main() {
fmt.Println(maxProfitBrute([]int{7, 1, 5, 3, 6, 4}))
}
Key Takeaways
- Start with the brute-force approach to understand the problem
- One-Pass Min Tracking (Optimal) gives the optimal O(n) solution
- Practice this pattern — it appears frequently in coding interviews
FAQ
What is the best approach to solve Best Time to Buy and Sell Stock in Go?
The recommended approach is One-Pass Min Tracking (Optimal), which runs in O(n) time with O(1) space. The full Go implementation is shown above.
What is the time complexity of Best Time to Buy and Sell Stock in Go?
Using One-Pass Min Tracking (Optimal), the time complexity is O(n) and the space complexity is O(1).
Happy coding!
