Skip to main content

121. Best Time to Buy and Sell Stock

easyAsked at Cisco

Best Time to Buy and Sell Stock at Cisco is a one-pass scan that masquerades as DP. The interviewer is checking whether you maintain a 'minimum-so-far' invariant and compute profit against it at every position, all in one walk.

By Sam K., Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Cisco loops.

  • Glassdoor (2026-Q1)— Cisco SDE-I phone screen reports cite Best Time to Buy and Sell Stock as a recurring warm-up.
  • Levels.fyi (2025-12)— Cisco new-grad interview reports list this as a typical 15-20 minute first round.

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^5
  • 0 <= prices[i] <= 10^4

Examples

Example 1

Input
prices = [7,1,5,3,6,4]
Output
5

Explanation: Buy day 2 (price 1), sell day 5 (price 6). Profit 5.

Example 2

Input
prices = [7,6,4,3,1]
Output
0

Explanation: Prices only decrease; no profit possible.

Approaches

1. Brute-force: try every buy/sell pair

For each i, scan all j > i, track the max (prices[j] - prices[i]).

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++) {
      const profit = prices[j] - prices[i];
      if (profit > best) best = profit;
    }
  }
  return best;
}

Tradeoff: Quadratic; TLEs on 10^5 prices. Useful only to show you understand the objective before optimizing.

2. One-pass with running minimum (optimal)

Walk left to right. Maintain `minSoFar`. At each position, the best profit you could have made ending today is prices[i] - minSoFar. Track the global max.

Time
O(n)
Space
O(1)
function maxProfit(prices) {
  let minSoFar = prices[0];
  let best = 0;
  for (let i = 1; i < prices.length; i++) {
    if (prices[i] < minSoFar) minSoFar = prices[i];
    const profit = prices[i] - minSoFar;
    if (profit > best) best = profit;
  }
  return best;
}

Tradeoff: Single pass, O(1) space, two scalar variables. The framing — 'minSoFar is the best buy-day for any sell-day at or after the current position' — is the entire algorithm. Cisco interviewers expect this exact pattern.

Cisco-specific tips

Cisco interviewers grade this on whether you reach for the one-pass scan immediately. State the invariant out loud: 'At position i, the best profit ending today is prices[i] - min(prices[0..i-1]). I maintain that running minimum in one variable.' That sentence is the entire interview signal. Don't overcomplicate with DP arrays — two scalars suffice.

Common mistakes

  • Initializing `best` to -Infinity — must be 0 because the problem says 'return 0 if no profit is possible.'
  • Updating minSoFar AFTER computing profit instead of BEFORE — buys on the same day you sell, which is forbidden ('different day in the future').
  • Allocating an O(n) DP array when two scalars suffice — wastes memory.

Follow-up questions

An interviewer at Cisco may pivot to one of these next:

  • Best Time to Buy and Sell Stock II (LC 122) — unlimited transactions, greedy sum of positive deltas.
  • Best Time to Buy and Sell Stock III (LC 123) — at most TWO transactions; DP with 4 states.
  • Best Time to Buy and Sell Stock IV (LC 188) — at most K transactions; DP with 2*K states.
  • Best Time to Buy and Sell Stock with Cooldown (LC 309) — state machine DP.
  • What if you could only sell at the END of the week, not any day? — bounded by 7-day window, same scan.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Is this 'DP' or 'greedy'?

Technically both. The DP framing: dp[i] = max profit ending at day i = max(dp[i-1], prices[i] - minSoFar). Since dp[i] only depends on dp[i-1] and a running minimum, you collapse the array to a single variable. The greedy framing: 'buy at the lowest price seen so far, sell now if it's profitable.' Pick whichever vocabulary the interviewer prefers.

What if prices are negative?

Same algorithm; runningMin would just track the most-negative price. The problem says prices[i] >= 0 so it doesn't come up at Cisco, but mentioning the edge case shows engineering polish.

Free learning resources

Curated free links for this problem.

More Cisco coding interview questions

See all Cisco problems →

Companies that also ask Best Time to Buy and Sell Stock