Best time to buy and sell stock

This is a basic array problem found in various coding platforms. While the name of the problem (as well the article) is pretty cheesy the actual requirement is quite straightforward.

You are given an array of non-negative integers stored in an unsorted fashion. The idea is to find out the maximum of the differences that exists between two elements arr[i] and arr[j] with the given constraints as, i<j. Which means if the two starting elements of the array are 9 and 3 then (9-3) = 6 will not be taken as a difference as 9’s position is < 3’s position.

Leetcode describes the problem as below
Best time to buy and sell stock.

As I always believe that any given problem can have many solutions, so what I propose here is merely one of them and I am more than willing to accept any optimisation suggestion and idea from anyone who cares to read this post.

The idea here is to traverse the array only once and find out difference things

• The minimum element in the array
• The maximum which appears after the minimum element.
• The max of difference so far.

To achieve this, we will keep a watch on the elements and update the min as and when we encounter an element which is < the existing min. To start with, the min can be set arr[0].

Then for each element we do the following:

• Check if it is < min, if yes then we update the min and ignore the difference.
• Else, we compute the difference between the current element and the min element.
• If the difference thus obtained is greater than the existing difference then we update the difference.

That’s it. At the end we are left with the max difference.

The code snippet as submitted in leetcode is given below. This algorithm as of today(21/09/2021) ran 99.61% faster than other python3 submissions.

def maxProfit(self, prices: List[int]) -> int:
    min_ = prices[0]
    difference = 0    
    for item in prices:
        if item < min_:
            min_ = item
        else:
            if (item - min_) > difference:
                difference = item - min_

    return difference

Thanks for visiting here. Kindly provide your valuable opinions as comments below.