Best Time to Buy and Sell Stock

Table of Contents

Problem Statement

The problem “Best Time to Buy and Sell Stock” states that you are given an array of prices of length n, where the ith element stores the price of stock on ith day.
If we can make only one transaction, that is, to buy on one day and sell on another upcoming day, what will be the maximum profit earned.

Example

prices[] = {7, 1, 5, 3, 6, 4}

Algorithm

If we buy the stock on ith day, the maximum profit is earned by selling the stock on a day between i + 1 to n, such that the day has the maximum price of the stock and that is greater than price[i].
Consider prices = {7, 1, 5, 3, 6, 4}

So, the maximum profit is earned by buying the stock on day 2 and selling it on day 5, the maximum profit earned is 5.

Naive Approach for Best Time to Buy and Sell Stock

The naive approach to implement the above algorithm is to run two nested loops, one for the buying day and another for finding the maximum profit on upcoming days.

Pseudo Code

int maxProfit = -infinity;
for (int i = 0; i < n; i++) {
  int costPrice = price[i];
  int max = -infinity;
  // Finding the maximum stock price greater than costPrice on upcoming days
  for (int j = i + 1; j < n; j++) {
    if (prices[j] > costPrice) {
      max = maximum(max, a[j]);
    }
  }
  int profit = 0;
  if (max != -infinity) {
    profit = max - costPrice;
  }
  maxProfit = maximum(maxProfit, profit);
}

Complexity Analysis

Time Complexity

O(n^2) , because we are using two nested loops for picking up the day to buy and sell the stock. Thus the time complexity is poltnomial.

Space Complexity

O(1), since we are not storign any information regarding each element in any data structure. We have been using only constant space. Thus the space complexity is linear.
where n is the number of elements in the array.

Optimal Approach for Best Time to Buy and Sell Stock

A better approach is to form an array whose ith element stores the maximum value present in prices array from index i + 1 to n. That is, we are precomputing the work done by inner nested loop in naive approach. So that, we can replace the inner nested loop by directly finding the maximum. The precomputation algorithm works in following manner.

Create an array named maxSP of size equals size of prices array and a variable max and initialize it as the minimum value.
Start from the last index in prices array.
1. If prices[i] is greater than max
  1. Update max as prices[i] and make maxSP[i] as minimum value
2. Else if prices[i] is not greater than max
  1. Update maxSP[i] = max.
After the pre computation, we follow the naive approach and replace the inner nested loop by using the maxSP array that we just created.

Pseudo Code

// Pre computation
int max = -infinity;
for (int i = n - 1; i >= 0; i--) {
  if (prices[i] > max) {
    max = prices[i];
    maxSP[i] = -infinity;
  } else {
    maxSP[i] = max;
  }
}
// Do as in naive approach
int maxProfit = -infinity;
for (int i = 0; i < n; i++) {
  int costPrice = prices[i];
  // Rather than using a loop to calculate max, we can directly get it from maxSP array
  int max = maxSP[i];
  int profit = 0;
  if (max != -infinity) {
    profit = max - costPrice;
  }
  maxProfit = maximum(maxProfit, profit);
}

Code

Java Code for Best Time to Buy and Sell Stock problem

import java.util.Scanner;

class BestTimetoBuyandSellStock {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // Prices array
        int prices[] = new int[]{7, 1, 5, 3, 6, 4};

        // Calculating the max profit
        int ans = maxProfit(prices, prices.length);

        // Print the answer
        System.out.println(ans);
    }

    private static int maxProfit(int[] prices, int n) {
        int maxSP[] = new int[n];
        int max = Integer.MIN_VALUE;

        // Construct the maxSP array
        for (int i = n - 1; i >= 0; i--) {
            if (prices[i] > max) {
                max = prices[i];
                maxSP[i] = Integer.MIN_VALUE;
            } else {
                maxSP[i] = max;
            }
        }

        int profit = 0;
        for (int i = 0; i < n; i++) {
            if (maxSP[i] != Integer.MIN_VALUE) {
                profit = Math.max(profit, maxSP[i] - prices[i]);
            }
        }

        // Return profit
        return profit;
    }
}

C++ Code for Best Time to Buy and Sell Stock problem

#include <bits/stdc++.h>
using namespace std;

int maxProfit(int *prices, int n) {
    int maxSP[n];
    int max = INT_MIN;
    
    // Construct the maxSP array
    for (int i = n - 1; i >= 0; i--) {
        if (prices[i] > max) {
            max = prices[i];
            maxSP[i] = INT_MIN;
        } else {
            maxSP[i] = max;
        }
    }
    
    int profit = 0;
    for (int i = 0; i < n; i++) {
        if (maxSP[i] != INT_MIN) {
            profit = std::max(profit, maxSP[i] - prices[i]);
        }
    }
    
    // Return profit
    return profit;
}

int main() {
    // Prices array
    int prices[] = {7, 1, 5, 3, 6, 4};
    
    // Calculating the max profit
    int ans = maxProfit(prices, sizeof(prices) / sizeof(prices[0]));
    
    // Print the answer
    cout<<ans<<endl;
    return 0;
}

Complexity Analysis

Time Complexity

O(n), as we have traversed over n elements of the array, during the precomputation and calculation of maximum profit. The time complexity is linear.

Space Complexity

O(n), because during the precomputation part we were storing the maximum selling price on a day after the current day. Since it is stored for all the elements in the array. The space complexity is also linear.
where n is the number of elements in the array.