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 buy one share of the stock and sell one share of the stock, design an algorithm to find the best times to buy and sell.


It is a question from Hacking a Google Interview from MIT handout #3 titled “Beating the Stock Market“.

At first glance, you might think that finding the minimum and maximum value would do, but it does have a hidden restriction, that is: You must buy before you can sell.

The question is equivalent to the following:

Find i and j that maximizes Aj – Ai, where i < j.

There is an obvious O(N2) solution, but in fact we can do better in just O(N).

To solve this problem efficiently, you would need to track the minimum value’s index. As you traverse, update the minimum value’s index when a new minimum is met. Then, compare the difference of the current element with the minimum value. Save the buy and sell time when the difference exceeds our maximum difference (also update the maximum difference).

VN:F [1.9.22_1171]
Rating: 4.6/5 (63 votes cast)
Best Time to Buy and Sell Stock, 4.6 out of 5 based on 63 ratings

40 thoughts on “Best Time to Buy and Sell Stock

  1. Nicky

    Actually this is an easy question. People may learn this in data structure course. Though, your solution still good an elegant. Like it.

    VA:F [1.9.22_1171]
    -24
  2. 1337c0d3r

    Yeah it is easy but I also like how easy it is to fall into the trap if you're not careful. Really? Did you learn it in a data structure course? I did not. How would you classify this question? I don't think it's DP (ie, it does not have overlapping sub-problems). Correct me if I'm wrong.

    VA:F [1.9.22_1171]
    +6
    1. opoopo

      Suppose D[i] is the maximum income when sell at price A[i], then
      D[i] = max_{k <= i}{A[i] – A[k]} and if i==0, D[0]=0
      and
      D[i+1] = (A[i+1]-A[i]) + Math.max(D[i],0) //Runtime:O(n)
      finally
      maximum income is max_{i=[0,n)}{D[i]}

      VA:F [1.9.22_1171]
      +1
      1. opoopo

        VA:F [1.9.22_1171]
        +11
  3. www

    hey 1337coder,

    i was given an interview question on this, but they had a following question: if you can keep buying and selling, how to maximize the profit? for example, if it is 6,1,3,2,4,7, we can buy for 1 and sell for 3, and we can buy for 2, and sell for 4,then buy on 4, sell for 7. total maxval =3-1+4-2+7-4 = 7. They would like to have some O(n) solutions.

    VA:F [1.9.22_1171]
    +2
    1. Brady Fang

      VA:F [1.9.22_1171]
      -2
    2. Brady Fang

      I intended to copy the second while loop as:

      VA:F [1.9.22_1171]
      0
    3. ted cheng

      public class Solution {
      public int maxProfit(int[] prices) {
      int max = 0;
      for(int i = 0; i < prices.length – 1; i++) {
      max += Math.max(0, prices[i+1] – prices[i]);
      }

      return max;
      }
      }

      VN:F [1.9.22_1171]
      +1
  4. ashish

    int[] stocks = { 2, 2, 6, 5, 1, 4 } for this input the buy should be at index 4 and sell should be at index 6. however your code return index 0 for buy (which is wrong) and index 2 for sell.

    VA:F [1.9.22_1171]
    -4
  5. jtosson

    #include
    #include
    int main ()
    {
    extern void trade(int * ,int);
    int arr[]={6,1,3,2,4,7};
    trade(arr,sizeof(arr)/sizeof(arr[0]));
    getch();
    return 0;
    }
    void trade(int *p,int size){
    int b=0,s=0,min,profit=0,i,buy=0;
    min=p[0];
    for(i=0;i<size;i++)
    {
    if(p[i]profit)
    {
    buy=b;
    s=i;
    profit=p[i]-min;
    }
    }
    printf(“buy on %d , sell on %d ..profit %d \n”,buy,s,profit);
    }

    VA:F [1.9.22_1171]
    -1
  6. jtosson

    VA:F [1.9.22_1171]
    -1
    1. durbin

      void getMaxProfit(int stocks[], int N) {
      if (N <2) return 0;

      int prev = stocks[0];
      int bought = -1;
      int profit = 0;

      for(int i = 0; i stocks[prev] ) {
      if (bought < 0)
      bought = stock[prev];
      } else if(stocks[i] = 0) {
      assert(stocks[prev] >= bought;
      profit += stocks[prev] >= bought;
      bought = -1;
      }
      }
      prev = i;
      }

      return profit;
      }

      VA:F [1.9.22_1171]
      0
  7. Moussa

    I think it is safe to put the following into a “else” block.

    VA:F [1.9.22_1171]
    0
  8. Ashwin

    @Moussa:
    If we put the code you mentioned in else block. It wont work for input like 1,2,3,4,5,6 where it will never enter the else block. COrrect me if i am wrong.

    VA:F [1.9.22_1171]
    0
  9. xjing

    public class Solution {
    public int maxProfit(int[] prices)
    {
    if (prices==null||prices.length<=0)
    return 0;

    int profit = 0;
    int high = prices[0];
    int low = prices[0];
    for(int i=1;ihigh)
    {
    high =prices[i];
    profit = high-low;
    }
    else if (prices[i] -low >profit)
    {
    high = prices[i];
    profit = high – low;
    }
    else if (prices[i]<low)
    low = prices[i];

    }
    return profit;

    }
    }

    VN:F [1.9.22_1171]
    0
    1. Steven Lee

      The easiest and fastest correct answer is this:

      VN:F [1.9.22_1171]
      0
      1. Steven Lee

        Sorry, copy mistake,

        VN:F [1.9.22_1171]
        -1
          1. Steven Lee

            public class Solution {

            public int maxProfit(int[] prices) {
            // Start typing your Java solution below
            // DO NOT write main() function
            // find a pattern which minimal price is before maxminal price
            if (prices==null||prices.length<=0)
            return 0;
            int result = 0;
            for(int i = 1; i 0 ) {
            result += diff;
            }
            }
            return result;
            }
            }

            VN:F [1.9.22_1171]
            0
  10. asuran

    if you build an array of stocks[i] – stocks[i-1], this problem is converted to Maximum sub-array problem. and you can reduce the space to constant later

    VA:F [1.9.22_1171]
    +1
  11. guest

    I could think of one more appraoch, Buy on a local minimum and sell on the local maximum. Lets say we have price array as [6,1,3,2,4,7]. I’ll buy at 1 and 2 (both local minimums) and sell at 3,7 (both local maximums). Does it sound okay ?

    VA:F [1.9.22_1171]
    0
  12. Amit

    public class Snippet {

    public static void main(String[] args) {
    getBestTime(new int[]{7, 1,2,3,4} );
    }

    static void getBestTime(int stocks[]) {
    int min = 0;
    int max = 0;
    int maxDiff = 0;
    int buy = 0;
    int sell = 0;
    for (int i = 0; i < stocks.length; i++) {
    if (stocks[i] stocks[max])
    max = i;

    int diff = stocks[max] – stocks[min];
    if (diff > maxDiff) {
    buy = min;
    sell = max;
    maxDiff = diff;
    }
    }
    System.out.println(“buy -> ” + stocks[buy] + ” sell -> ” + stocks[sell]);
    }
    }

    VA:F [1.9.22_1171]
    0
  13. Enzix

    if (prices.length > 1) {
    int minVal = prices[0];
    int maxVal = 0;
    int maxDiff = 0;
    for (int i = 0; i < prices.length; i++) {
    if (prices[i] <= minVal) {
    int temp = prices[i];
    for (int j = i + 1; j < prices.length; j++, i++) {
    if (prices[j] maxDiff) {
    maxVal = prices[j];
    minVal = temp;
    maxDiff = Math.abs(prices[j] – temp);
    }
    }
    }
    else if (prices[i] > maxVal)
    maxVal = prices[i];
    }
    return maxVal > 0 ? maxVal – minVal : 0;
    }
    return 0;

    VA:F [1.9.22_1171]
    0
  14. theminimalist

    This shows wrong answer for the following test case apparently :
    Input : [6,1,3,2,4,7]
    Output : 7
    Expected : 6

    Can anyone please explain to me my fault?

    VA:F [1.9.22_1171]
    +1
  15. Luke Scalf

    So how do you account for a day that the stock prices only drop. For example:

    prices = [43, 41, 35, 27, 19, 12, 5, 2]

    Ideally, if you are required to buy and sell in that day. You would want to minimize the loss. Your max profit would be -2 in this array and your buy would be at index 0 and sell would be at index 1. Your algorithm never returns less than 0. In my last interview this came up and they still wanted a O(n) solution. I could make it work easily with 2 nested for loops O(n^2) but couldn’t figure out how to keep it O(n). Any ideas?

    VA:F [1.9.22_1171]
    0
  16. 多くの探検家選択を探検装備のボル表、今度は究極の腕時計を探検運動。FiremanストームChaser腕時計も獲得しアメリカ竜巻研究家の胡文博士の同情。この黒い表面の腕時計をして新しい多機

    多くの探検家選択を探検装備のボル表、今度は究極の腕時計を探検運動。FiremanストームChaser腕時計も獲得しアメリカ竜巻研究家の胡文博士の同情。この黒い表面の腕時計をして新しい多機能クロノ発揮はクロノメーターのほか、余分に提供した速度計と距離計の実用的な機能になるとなり、勇敢な「群れ者”たちの装備の一つ。スーパーコピーまた以前発表したEngineer DiverⅡGMTも登場し、この採用DLCめっきとアナログ時計バンドの限界潜水しジオン·乃瑞潜など113メートルの深海、再び世界記録を破った素手で潜水。そのマイナス40度抗低温の能力も確保でき、潜水勇士寒い深海で正確な時間を把握する。 http://www.newkakaku.com/lb5.htm

    VA:F [1.9.22_1171]
    0

Leave a Reply

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

You may use the <code> tag to embed your code.

*