Best Time to Buy and Sell Stock

Given daily stock prices, choose one day to buy and a later day to sell. Return the maximum profit, or 0 if no profit is possible.

A way to picture it

You're a time traveller with one trade. You walk forward through the calendar, always remembering the cheapest day you've passed. On each new day you ask one question: if I'd bought on that cheapest day, what would I make selling today?

How to approach it

The best sale on any day only depends on the lowest price before it. Track that minimum as you go, and the answer is the biggest (price − minimum) you ever see.

Example

Input: {"prices":[7,1,5,3,6,4]}. Output: 5.

Complexity: O(n) time and O(1) space. One pass, two variables.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.