Coding

Best time to buy and sell stock

Asked atJGJMAN Group

MakeMyTrip

Microsoft

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an array arr of n integers, where arr[i] represents price of the stock on the ith day. Determine the** maximum profit** achievable by buying and selling the stock at most once.

The stock should be purchased before selling it, and both actions cannot occur on the same day.

Input: arr = [10, 7, 5, 8, 11, 9] Output: 6 Explanation: Buy on day 3 (price = 5) and sell on day 5 (price = 11), profit = 11 - 5 = 6.

Input: arr = [5, 4, 3, 2, 1] Output: 0 Explanation: In this case, no transactions are made. Therefore, the maximum profit remains 0.

**Input: **arr = [3, 8, 1, 4, 6, 2]

1 <= n<= 105
0 <= arr[i] <= 106

cpp

class Solution{
public:
    int stockBuySell(vector<int> arr, int n){
        
    }
};

java

class Solution {
    public int stockBuySell(int[] arr, int n) {
       
    }
}

python

class Solution:
    def stockBuySell(self, arr, n):

javascript

class Solution {
    stockBuySell(arr, n) {
     
    }
}

csharp

class Solution
{
    public int stockBuySell(int[] arr, int n)
    {
       
    }
}

func stockBuySell(arr []int, n int) int {
	
}

Stuck? Show a way to structure it+

01Track the minimum stock price seen before the current day.
02Treat the current day as a possible sale and update the best profit.
03Then update the running minimum for future days.
04Keep zero profit when no profitable transaction exists.

Reference answer

Scan prices from left to right with minimumPrice equal to the lowest price seen so far and bestProfit = 0. For each current price, the best valid transaction selling today buys at minimumPrice, so update bestProfit = max(bestProfit, price - minimumPrice). Then update minimumPrice = min(minimumPrice, price). Because the minimum comes from the current or an earlier day and profit is evaluated in scan order, the buy always precedes the sell. If prices only decline, the answer remains zero, representing no transaction. Time is O(n) and extra space is O(1). This is equivalent to finding the maximum difference prices[j] - prices[i] subject to i < j, without comparing every pair. If a transaction were mandatory, the initialization and declining-price behavior would need to change.

Then expect these follow-ups

How would you return the buy and sell days?
Tests: state tracking
What changes when unlimited transactions are allowed?
Tests: variant recognition

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question