Best time to buy and sell stock

Moderate

0/80

Average time to solve is 30m

Contributed by

139 upvotes

Asked in companies

Problem statement

You are given an array of integers 'prices' of size 'n', where ‘prices[i]’ is the price of a given stock on an ‘i’-th day. You want to maximize the profit by choosing a single day to buy one stock and a different day to sell that stock.

Please note that you can’t sell a stock before you buy one.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains an integer ‘n’ denoting the size of the array ‘prices’.
The second line includes ‘n’ integers denoting the elements of the array ‘prices’.

Output format :

Return the maximum profit you can achieve from this transaction.

Constraints :

1 <= 'n' <= 10 ^ 5
1 <= ‘prices[i]’<= 10 ^ 9

Time Limit: 1 sec

Sample Input 1:

6
7 1 5 4 3 6

Sample Output 1 :

Explanation Of Sample Input 1:

Purchase stock on day two, where the price is one, and sell it on day six, where the price is 6. Profit = 6 - 1 = 5.

Sample Input 2:

5
5 4 3 2 1

Sample Output 2 :

Hint 1

Hint 2

Try out all possible ways to buy and sell the stocks.

Approaches (2)

Approach 1

Approach 2

Brute Force

As seen from the sample input-output examples, a possible approach would be to buy a stock, sell it on every possible day whenever profitable, and keep updating the maximum profit so far.

This will require two nested loops. The outer one will pick up each day, say I, one by one to purchase that stock, and the inner loop will calculate the profit if the stock is sold on each possible day.

The steps are as follows:-

Initialize ‘maxProfit’ with 0.
Use two nested loops. The outer one will consider the day the stock will be purchased, and the inner one will consider the days on which the stock will be sold.
Find the maximum profit by buying and selling at each index. At each iteration, find the profit. Change the value of the ‘maxProfit’ if the yield obtained is greater than the ‘maxProfit’.
Return the maximum profit.

Time Complexity

O(n ^ 2), Where 'n' is the array ‘prices’ length.

We have two nested loops of O(n) complexity each.

Space Complexity

O(1).

We are using some variables that take some constant space.

Hence the space complexity is O(1).

(75% EXP penalty)

(100% EXP penalty)

Best time to buy and sell stock

Console