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.
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?
{
"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.
Constraints:
We have provided four solutions.
Throughout this editorial, we will refer to the input array as arr and its size as n.
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.
O(n2).
As we are using two nested loops, it will take O(n2). Hence, the time complexity will be O(n2).
O(1).
We used only a constant amount of extra space.
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).
/*
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;
}
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).
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).
O(1).
We used only a constant amount of extra space.
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).
/*
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;
}
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.
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).
O(1).
We used only a constant amount of extra space.
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).
/*
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;
}
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.
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).
O(1).
We used only a constant amount of extra space.
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).
/*
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:
To learn more, register for the FREE webinar.
