LeetCode 121. Best Time to Buy and Sell Stock



Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.


The problem is seeking the max profit in buying and selling stocks.

This is a simple modeling stocks trading in real life. The essence of the problem is looking for the max value of prices[i2] – prices[i1], i2 > i1.

prices[i2] is the max value in the array. prices[i1] is the minimum value in the array.

It’s easy to solve the problem by keep tracking of the minimum price and max profit when iterating the array.

Video Tutorial

Java Solution

public class Solution { 
    public int maxProfit(int[] prices) { 
        int maxProfit = 0; 
        int minPrice = Integer.MAX_VALUE; 
        for (int i = 0; i < prices.length; i++) { 
            minPrice = Math.min(minPrice, prices[i]); 
            maxProfit = Math.max(maxProfit, prices[i] - minPrice); 
        return maxProfit; 

Leave a Reply

Your email address will not be published. Required fields are marked *