TIC
The Interns Company

Best Time to Buy and Sell Stock

EasyAcceptance: 52.6%
ArrayDynamic Programming

Problem Statement

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

Input Format:

  • An array of integers prices representing stock prices on consecutive days

Output Format:

  • Return the maximum profit that can be achieved. If no profit is possible, return 0.

Examples:

Example 1:

Input:

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

Output:

5

Explanation:

Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input:

prices = [7,6,4,3,1]

Output:

0

Explanation:

In this case, no transactions are done and the max profit = 0.

Example 3:

Input:

prices = [2,4,1]

Output:

2

Explanation:

Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Solutions

One Pass Approach

Time: O(n)
Space: O(1)

Use a single pass through the array, keeping track of the minimum price seen so far and the maximum profit that can be achieved.

Kadane's Algorithm Approach

Time: O(n)
Space: O(1)

Treat this as a variant of the maximum subarray problem by calculating the differences between consecutive prices and finding the maximum subarray sum.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. Initialize minPrice = 7, maxProfit = 0
  2. i=1: price=1, 1 < 7, so update minPrice = 1
  3. i=2: price=5, 5 - 1 = 4 > maxProfit, so update maxProfit = 4
  4. i=3: price=3, 3 - 1 = 2 < maxProfit, no update
  5. i=4: price=6, 6 - 1 = 5 > maxProfit, so update maxProfit = 5
  6. i=5: price=4, 4 - 1 = 3 < maxProfit, no update
  7. Return maxProfit = 5

Hints

Hint 1
You need to find the largest peak following the smallest valley.
Hint 2
You can maintain two variables - minimum price so far and maximum profit so far.
Hint 3
Iterate through the array once, updating these variables as you go.

Video Tutorial

Best Time to Buy and Sell Stock - One Pass Solution

YouTube•Learn the Best Time to Buy and Sell Stock solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the stock prices as a line chart, highlight the buy and sell points for maximum profit.

Key visualization elements:

  • minimum price
  • current price
  • maximum profit

Asked By

AmazonMicrosoftFacebookGoogleAppleAdobeBloombergGoldman Sachs

Implementation Notes

This is a fundamental problem that tests understanding of array traversal and greedy algorithms. The key insight is that we only need to keep track of the minimum price seen so far to calculate the maximum profit at each step.