121. Best Time to Buy and Sell Stock
easyAsked at ShopifyShopify uses this to test whether you recognize 'max profit so far' as a single-pass DP and avoid the O(n^2) two-loop. The interviewer is grading the explanation of the running-minimum invariant.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Shopify loops.
- Glassdoor (2026-Q1)— Shopify Backend Developer + Production Engineer phone screens cite this as a 10-minute warm-up.
- Reddit r/cscareerquestions (2025-10)— Shopify new-grad and intern reports include this with a follow-up about multiple transactions.
Problem
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.
Constraints
1 <= prices.length <= 10^50 <= prices[i] <= 10^4
Examples
Example 1
prices = [7,1,5,3,6,4]5Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6).
Example 2
prices = [7,6,4,3,1]0Explanation: No transaction yields a profit.
Approaches
1. Brute-force all (buy, sell) pairs
For each i < j, compute prices[j] - prices[i] and track max.
- Time
- O(n^2)
- Space
- O(1)
function maxProfitBrute(prices) {
let best = 0;
for (let i = 0; i < prices.length; i++) {
for (let j = i + 1; j < prices.length; j++) {
best = Math.max(best, prices[j] - prices[i]);
}
}
return best;
}Tradeoff: n = 10^5 means 10^10 ops — won't finish. Mention only as the naive baseline.
2. Single pass, running minimum (optimal)
Maintain min_so_far. For each price, profit if sold today is price - min_so_far. Track max of those.
- Time
- O(n)
- Space
- O(1)
function maxProfit(prices) {
let minPrice = Infinity;
let best = 0;
for (const p of prices) {
if (p < minPrice) minPrice = p;
else if (p - minPrice > best) best = p - minPrice;
}
return best;
}Tradeoff: Linear time, constant space. The canonical answer. Key invariant: at every step, min_so_far is the optimal buy day for all sell days <= current. Profit = sell - min_so_far, maximized greedily.
3. DP via Kadane's algorithm reformulation
Reframe as max-subarray on the daily differences. The largest contiguous sum of diffs IS the max single-transaction profit.
- Time
- O(n)
- Space
- O(1)
function maxProfitKadane(prices) {
let cur = 0, best = 0;
for (let i = 1; i < prices.length; i++) {
cur = Math.max(0, cur + prices[i] - prices[i - 1]);
best = Math.max(best, cur);
}
return best;
}Tradeoff: Same O(n) but exposes the connection to Maximum Subarray (LeetCode 53). Useful to mention when the interviewer asks 'how does this relate to other DPs you've seen?'
Shopify-specific tips
Shopify wants the running-minimum version with the explanation. Avoid jumping to Kadane unless asked — most candidates muddle the reformulation under time pressure. The expected follow-up is 'what about multiple transactions?' (LeetCode 122) — the greedy answer is sum all positive daily diffs.
Common mistakes
- Initializing min_so_far = prices[0] and starting the loop at i = 1 — fine if prices is non-empty, but failing the empty-input case requires care.
- Tracking max_so_far separately from min_so_far — you can update best inside the same loop branch.
- Returning a negative profit — must return 0 if no profitable transaction.
- Treating it as a max-min problem (max - min) without ordering — that's wrong if the min comes AFTER the max.
Follow-up questions
An interviewer at Shopify may pivot to one of these next:
- II: Multiple transactions allowed (LeetCode 122) — sum positive diffs.
- III: At most 2 transactions (LeetCode 123) — DP with state for each transaction.
- IV: At most K transactions (LeetCode 188) — DP over K.
- V: With cooldown (LeetCode 309).
- VI: With transaction fee (LeetCode 714).
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why is the running-minimum correct?
Because for any sell day d, the optimal buy day is the minimum price in [0..d-1]. We compute that minimum incrementally as we walk, then check whether selling today beats our running max. We never have to look back.
What if the array is empty?
Return 0 — there's no transaction possible. The running-minimum version handles this naturally if you initialize minPrice = Infinity and best = 0; the loop simply doesn't execute.
Free learning resources
Curated free links for this problem.