Stock Buy Sell

Given daily prices of a stock, what’s the maximum possible profit one can generate by first buying one share of that stock on a certain day and then selling that share at least one day later?

Example One

Input: [ 2, 3, 10, 6, 4, 8, 1]

Output: 8

For a maximum possible profit of 8 one can buy a share on day 0 at the price of 2 and then sell it on day 2 at the price of 10. Note that one isn’t allowed to first sell (“sell short”) for 10 and then buy (“buy to cover”) later for 1 which could have generated a higher profit.

Notes

Input Parameters: The function has one argument, an integer array with daily prices.

Output: Return an integer, the maximum possible total profit from buying and then selling a share. If no profit can be generated, return -1.

Constraints:

● 2 <= number of elements in the input array <= 10^5

● 1 <= any element in the input array <= 10^9

Solutions:

We provided four solutions.

1) brute_force_solution.java

Calculating maximum possible profit is as simple as finding the maximum difference between two elements such that the larger element appears after the smaller number. We will try the following approach:

Use two loops. In the outer loop, pick elements one by one and in the inner loop calculate the difference of the picked element with every other element in the array and compare the difference with the maximum difference calculated so far.

Time Complexity:

O(n^2) where n denotes the length of the input array.

As we are using two nested loops, it will take O(n^2). Hence complexity will be O(n^2).

Auxiliary Space Used:

O(1).

As we are not storing anything extra other than some integer variables which will take constant space.

Space Complexity:

O(n) where n denotes the length of the input array.

As auxiliary space used is O(1) and to store input it will take O(n), to store output it will take constant space as output is a single integer. Hence total space complexity will be O(1) + O(n) + O(1) = O(n).

// -------- START --------
    public static int find_maximum_profit(List arr) {
        // Size of arr
        int arr_size = arr.size();
        // Initialise max_diff
        int max_diff = arr.get(1) - arr.get(0);
        // Iterate over all elements
        for (int i = 0; i < arr_size; i++) {
            // Iterate over elements in array present after current element
            for (int j = i + 1; j < arr_size; j++) { 
                // Calculate diff if selling price (arr.get(j)) is greater than buying price (arr.get(i))
                if (arr.get(j) - arr.get(i) > max_diff) {
                    max_diff = arr.get(j) - arr.get(i);
                }
            }
        }
        // If no profit then return -1 else profit
        return max_diff>0?max_diff:-1;
    }
    // -------- END --------

2) optimal_solution1.java

In this method, instead of taking the difference of the picked element with every other element, we take the difference with the minimum element found so far. So we need to keep track of 2 things:

1) The maximum difference found so far (max_diff).

2) The minimum number visited so far (min_element).

Time Complexity:

O(n) where n denotes the length of integer array arr.

As we are using a single loop to calculate the maximum difference (maximum profit) and we are maintaining the minimum element found so far and maximum possible difference, it will take O(n). Hence complexity will be O(n).

Auxiliary Space Used:

O(1).

As we are not storing anything extra other than some integer variables which will take constant space.

Space Complexity:

O(n) where n denotes the length of integer array arr.

As auxiliary space used is O(1) and to store input it will take O(n) for storing arr of size n, to store output it will take constant space as output is a single integer. Hence total space complexity will be O(1) + O(n) + O(1) = O(n).

// -------- START --------
    public static int find_maximum_profit(List arr) {
        // Size of arr
        int arr_size = arr.size();

        // Initialise max_diff
        int max_diff = arr.get(1) - arr.get(0);

        // Initialise minimum element
        int min_element = arr.get(0);

        // Iterate over all arr elements from starting and maintain minimum element from left
        for (int i = 1; i < arr_size; i++) {
            // Buying price (min_element) and selling price (arr.get(i))
            if (arr.get(i) - min_element > max_diff) {
                max_diff = arr.get(i) - min_element;
                }
            if (arr.get(i) < min_element) {
                min_element = arr.get(i);
            }
        }
        // Return -1 if no profit else profit
        return max_diff>0?max_diff:-1;
    }
    // -------- END --------

3) optimal_solution2.java

In optimal_solution1, we were maintaining the minimum element found so far to calculate the maximum possible difference, here we will keep track of the maximum element from the right side.

Time Complexity:

O(n) where n denotes the length of integer array arr.

As we are using a single loop and iterating over it from the reverse side to calculate the maximum difference (maximum profit) and we are maintaining the maximum element found so far and maximum possible difference, it will take O(n). Hence complexity will be O(n).

Auxiliary Space Used:

O(1).

As we are not storing anything extra other than some integer variables which will take constant space.

Space Complexity:

O(n) where n denotes the length of integer array arr.

As auxiliary space used is O(1) and to store input it will take O(n) for storing arr of size n, to store output it will take constant space as output is a single integer. Hence total space complexity will be O(1) + O(n) + O(1) = O(n).

// -------- START --------
    public static int find_maximum_profit(List arr) {
        // Size of arr
        int n = arr.size();

        // Initialize Result
        int maxDiff = -1;

        // Initialize max element from right side
        int maxRight = arr.get(n-1);

        // Iterate over arr in reverse order and maintain max element from right
        for (int i = n-2; i >= 0; i--) {

            // Buying price (arr.get(i)) and selling price (maxRight)
            if (arr.get(i) > maxRight) {
                maxRight = arr.get(i);
            }
            else { 
                int diff = maxRight - arr.get(i);
                if (diff > maxDiff) { 
                    maxDiff = diff;
                }
            }
        }
        // Return -1 if no profit else profit
        return maxDiff>0?maxDiff:-1;
    }
// -------- END --------

4) optimal_solution3.java

We want to calculate the maximum possible profit by buying and selling stock exactly once, in simple words to calculate the maximum difference between two elements such that the larger element appears after the smaller number. We can follow the below-mentioned approach:

First, find the difference between the adjacent elements of the array and store all differences in an auxiliary array diff[] of size n-1. Now, this problem turns into finding the maximum sum subarray of this difference array. We can also optimise it further to make it work in O(1) extra space. Instead of creating an auxiliary array, we can calculate diff and maximum sum in the same loop.

Time Complexity:

O(n) where n denotes the length of integer array arr.

As we are using a single loop and iterating over it, it will take O(n). Hence complexity will be O(n).

Auxiliary Space Used:

O(1).

As we are not storing anything extra other than some integer variables which will take constant space.

Space Complexity:

O(n) where n denotes the length of integer array arr.

As auxiliary space used is O(1) and to store input it will take O(n) for storing arr of size n, to store output it will take constant space as output is a single integer. Hence

total space complexity will be O(1) + O(n) + O(1) = O(n).

‍

// -------- START --------
    public static int find_maximum_profit(List arr) {
        // Size of arr
        int arr_size = arr.size();

        // Initialise diff, curr_sum, max_sum
        int diff = arr.get(1) - arr.get(0);
        int curr_sum = diff;
        int max_sum = curr_sum;

        for(int i = 1; i < arr_size - 1; i++) {
            // Calculate current diff
            diff = arr.get(i + 1) - arr.get(i);

            // Calculate current sum
            if (curr_sum > 0) {
                curr_sum += diff;
            }
            else {
                curr_sum = diff;
            }

            // Update max sum, if needed
            if (curr_sum > max_sum) {
                max_sum = curr_sum;
            }
        }
        // Return -1 if no profit else profit
        return max_sum>0?max_sum:-1;
    }
    // -------- END --------

‍

‍