The buy and sell stocks problem is a popular DSA interview question. You can expect this problem at interviews in companies like Amazon and Facebook. Here, we’ll show you two ways of solving the problem — brute force and optimal — along with the respective time and space complexities.

Stock Buy Sell Problem Statement

Given daily prices of a stock, what is 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

{
"arr": [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

• The function has one argument: An integer array with daily prices.
• 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⁵
• 1 <= any element in the input array <= 10⁹

We have provided four solutions.

Throughout this editorial, we will refer to the input array as arr and its size as n.

Stock Buy Sell Solution 1: Brute Force

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²).

As we are using two nested loops, it will take O(n²). Hence, the time complexity will be O(n²).

Auxiliary Space Used

O(1).

We used only a constant amount of extra space.

Space Complexity

O(n).

Space used for input: O(n).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(n).

Code For Stock Buy Sell Solution 1: Brute Force

    /*
    Asymptotic complexity in terms of size of input array 'arr' (= 'n'):
    * Time: O(n ^ 2).
    * Auxiliary space: O(1).
    * Total space: O(n).
    */

    static Integer find_maximum_profit(ArrayList<Integer> arr) {

        int arr_size = arr.size();
        int max_diff = arr.get(1) - arr.get(0);

        for (int i = 0; i < arr_size; i++) {
            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;
    }

Stock Buy Sell Solution 2: Optimal 1

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).

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, the complexity will be O(n).

Auxiliary Space Used

O(1).

We used only a constant amount of extra space.

Space Complexity

O(n).

Space used for input: O(n).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(n).

Code For Stock Buy Sell Solution 2: Optimal 1

    /*
    Asymptotic complexity in terms of size of input array 'arr' (= 'n'):
    * Time: O(n).
    * Auxiliary space: O(1).
    * Total space: O(n).
    */

    static Integer find_maximum_profit(ArrayList<Integer> arr) {

        int arr_size = arr.size();
        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;
    }

Stock Buy Sell Solution 3: Optimal 2

In this method, 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).

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, the complexity will be O(n).

Auxiliary Space Used

O(1).

We used only a constant amount of extra space.

Space Complexity

O(n).

Space used for input: O(n).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(n).

Code For Stock Buy Sell Solution 3: Optimal 2

    /*
    Asymptotic complexity in terms of size of input array 'arr' (= 'n'):
    * Time: O(n).
    * Auxiliary space: O(1).
    * Total space: O(n).
    */

    static Integer find_maximum_profit(ArrayList<Integer> arr) {

        int n = arr.size();
        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;
    }

Stock Buy Sell Solution 4: Optimal 3

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 optimize 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).

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

Auxiliary Space Used

O(1).

We used only a constant amount of extra space.

Space Complexity

O(n).

Space used for input: O(n).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(n).

Code For Stock Buy Sell Solution 4: Optimal 3

    /*
    Asymptotic complexity in terms of size of input array 'arr' (= 'n'):
    * Time: O(n).
    * Auxiliary space: O(1).
    * Total space: O(n).
    */

    static Integer find_maximum_profit(ArrayList<Integer> arr) {

        int arr_size = arr.size();

        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++) {
            diff = arr.get(i + 1) - arr.get(i);

            if (curr_sum > 0) {
                curr_sum += diff;
            }
            else {
                curr_sum = diff;
            }

            if (curr_sum > max_sum) {
                max_sum = curr_sum;
            }
        }
        // Return -1 if no profit else profit
        return max_sum > 0 ? max_sum : -1;
    }

We hope that these solutions to stock buy sell problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

‍To learn more, register for the FREE webinar.