Skip to main content

17. Best Time to Buy and Sell Stock

easyAsked at Datadog

Find the max profit from one buy and one sell. Datadog frames this as 'find the largest spike in a metric stream' — single pass, constant memory, identical to their min-tracking aggregator.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite, framed as 'find max spread in a series.'
  • Blind (2025-11)— Recurring Datadog phone screen.

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 at 1, sell at 6.

Example 2

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

Explanation: No profitable transaction.

Approaches

1. Brute-force all (buy, sell) pairs

Two nested loops checking every pair.

Time
O(n^2)
Space
O(1)
function maxProfit(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: Quadratic — won't survive a 10^5-point Datadog query.

2. Single pass min-tracking (optimal)

Track the lowest price seen so far. At each day, max-profit-if-sell-today = current - min-so-far.

Time
O(n)
Space
O(1)
function maxProfit(prices) {
  let minSoFar = Infinity;
  let best = 0;
  for (const p of prices) {
    if (p < minSoFar) minSoFar = p;
    else if (p - minSoFar > best) best = p - minSoFar;
  }
  return best;
}

Tradeoff: Single pass, O(1) state. The min-so-far variable is exactly the state Datadog carries through their streaming aggregators.

Datadog-specific tips

Datadog will follow up with: 'Now do this over a streaming window — give me max profit in the last N minutes.' Show that single-min-tracking doesn't work for windowed queries; you need a monotonic deque keyed by price ascending. Bonus signal: discuss what happens when the stream is unbounded — when do you reset?

Common mistakes

  • Tracking max price too — unnecessary; only min matters because you can always recompute the spread vs current.
  • Initializing best to -Infinity — the problem requires a non-negative return.
  • Updating min AFTER computing profit — could buy and sell on the same day.

Follow-up questions

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

  • Stock II (LC 122) — unlimited transactions.
  • Stock III (LC 123) — at most two transactions.
  • Streaming max-spread over a sliding window — monotonic deque.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why does single-min-tracking work?

If today's price is the maximum sell price, you'd want to buy at the cheapest day before today. That's exactly the running minimum.

What if you can short-sell?

Then you also need running MAX-so-far. The problem disallows it; long-only means only min-tracking matters.

Practice these live with InterviewChamp.AI

Drill Best Time to Buy and Sell Stock and other Datadog interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →