DSA Visualizations | Hello Interview

Limited Time Offer: 40% off Hello Interview Premium 🎉

40% off Hello Interview Premium 🎉

Back to Main

Learn DSA

Overview

Two Pointers

Sliding Window

Intervals

Stack

Linked List

Binary Search

Heap

Depth-First Search

Breadth-First Search

Backtracking

Graphs

Dynamic Programming

Greedy Algorithms

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Trie

Prefix Sum

Matrices

Pricing

Become a Coach

Pricing Become a Coach

Get Premium

Overview

Gas Station

Best Time to Buy and Sell Stock

DESCRIPTION (credit Leetcode.com)

Write a function to determine the maximum profit you can obtain from a series of stock prices given in an array prices, where prices[i] represents the stock price on the ith day. You are allowed to buy and then sell the stock once, as long as as the sell date is after the buy date. If no profit can be made, the function should return 0.

EXAMPLES

Input:


prices = [3,4,6,2,5,8]

Output:

Explanation: Buy on day 4 (price = 2) and sell on day 6 (price = 8), profit = 8-2 = 6.

Input:


prices = [9,7,5,3,1]

Output:

Explanation: Prices are in descending order, so there's no opportunity to make a profit, thus the maximum profit = 0.

Solution


def maxProfit(prices):
  if not prices:
    return 0

  min_price = prices[0]
  max_profit = 0

  for price in prices:
    min_price = min(min_price, price)
    max_profit = max(max_profit, price - min_price)

  return max_profit

best time to buy and sell stock

0 / 7

Explanation

The problem is asking for the maximum profit that can be made by buying and selling a stock. The key to solving this problem is to find the minimum price to buy and the maximum price to sell.

We can solve this problem by using a greedy approach. We iterate through the array, and at each day, we'll see how much profit we can make by greedily selling the stock at that day. At the end of the iteration, the maximum of those profits will be the maximum profit we can make.

To help us calculate the maximum profit, we need two variables: min_price, which represents the minimum price we have seen so far, and max_profit, which represents the maximum profit we can make so far. At each day, we can calculate the max profit on each day by subtracting the minimum price from the current price. If that leads to a profit greater than the maximum profit we have found so far, we can update max_profit.


def maxProfit(prices):
  if not prices:
    return 0

  min_price = prices[0]
  max_profit = 0

  for price in prices:
    min_price = min(min_price, price)
    max_profit = max(max_profit, price - min_price)

  return max_profit

price = 5

0 / 1

Updating max_profit as we iterate.

Complexity Analysis

Time complexity: O(n). We only iterate through the array once.
Space complexity: O(1)

Next: Gas Station

Your account is free and you can post anonymously if you choose.

Sort By

Best Time to Buy and Sell Stock

DESCRIPTION (credit Leetcode.com)

EXAMPLES

Solution

Explanation

Complexity Analysis

Questions

Links

Legal

Contact