Making maximum profit in stock market: Buying and Selling

Problem Statement:

You are given an array, which contains the prices of a stock in a day.
You have to find the buy, sell pairs, so that you will make a maximum profit, by buying and selling the stock.

For eg: {100, 180, 260, 310, 50, 40, 535, 695}
--> First you can buy at: 100
      Sell at 310 ==> profit = (310-100) = 210
--> Buy at: 40
      Sell at: 695 ==> profit = (695-40) = 655

Algorithm:

Starting from first element, algorithm has to find the buy and sell prices.
Note that we have to buy at less price and sell at high price.
So we have to find the (low buy, high sell) price pairs.

1. First find an element, after which the sequence should be increasing.
2. Next find the element, for which all its left elements are lower from the buy price.
This becomes one pair.
3. Now starting from next price after the above sell price, find the first element, after which the sequence should be increasing.
4. Again, find the next element, for which all its left elements are lower from the buy price.

Continue this process until the array end is reached.

Code:

class StockMarket {
        static public void stockBuySell(int[] price, int n) {
                if(n == 1) return;

                int count = 0;

                //columns corresponds to buy and sell elements
                int[][] ints = new int[n/2+1][2];

                int i = 0;

                while(i < n-1) {
                        while( (i < n-1) && (price[i+1] <= price[i]))
                                i++;

                        if(i == n-1)
                                break;

                        ints[count][0] = i++;

                        while((i < n) && (price[i] >= price[i-1]))
                                i++;

                        ints[count][1] = i-1;

                        count++;
                }

                if(count == 0)
                        System.out.println("You cant make profit on this day");
                else
                        for(int j=0; j<count; j++)
                                System.out.println("Buy: " + price[ints[j][0]] + ", sell: " + price[ints[j][1]]);
        }

        static public void main(String[] args) {
                int[] price = {100, 180, 260, 310, 50, 40, 535, 695};

                stockBuySell(price, price.length);
        }
}

Output:

Buy: 100, sell: 310
Buy: 40, sell: 695

Complexity:

Time Complexity: O(n)

Space Complexity: O(n) (we can avoid this space and do it in O(1) as well, i.e, printing at the end of the while loop)

Linked List: Cycle detection: Floyd Cycle Algorithm

Floyd Cycle Algorithm:

As per this algorithm, if there is a cycle in Linked List, then the fast and slow pointers must meet at some point in the cycle and the start of the cycle can be find by, keeping a pointer at meeting location and moving another pointer from start of linked list, makes the two pointers to reach at the start of the cycle.

Lets prove it...

Proof:

Case 1: Fast pointer made one cycle:

So the slow pointer moved a distance of "x+y"

and fast pointer moved a distance of "x+y+z+y"

and if slow pointer moves a distance of "d", then fast pointer moves a distance of "2d", since is fast pointer moves two times faster than slow pointer.

So: distance traveled by fast ptr = 2 * distance traveled by slow ptr

==> x+y+z+y = 2 * (x+y)

x+2y + z = 2x + 2y

x+z = 2x

==> x = z

This proves that x and z are equal. So keeping one ptr at the meeting point of pointers, and moving other pointer from start will make them to meet at the start of the cycle.

Case 2: Fast pointer made two cycles:

==> fast pointer distance from start = x + y + 2(z+y)

==> slow pointer distance from start = x + y

==> x + y + 2 (z+y) = 2(x+y)

==> x + 3y + 2z = 2x + 2y

==> x = y + 2z

==> x = z  + (y+z)

since, if we start from a point in cycle and move (z+y) distance, we will be at the same point again. It means that with respect cycle, we didnt move at all.

So we can make "y+z" as zero

==> x = z

Similarly we can prove for n number of cycles as well.