Data Structures & Algorithms - Arrays & Strings: Best Time to Buy & Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.

Playground: Leetcode 121

Brute Force Approach

Use nested loops to iterate over all possible [buy_day_index, sell_day_index] pairs, and pick the one where prices[sell_day_index] - prices[buy_day_index] is maximum.

Algorithm

- max_profit = 0;
- for i in range[0, prices.length - 1]:
    - for j in range[i+1, prices.length]:
        - current_profit = prices[j] - prices[i];
        - max_profit = max(max_profit, current_profit);
- return max_profit;

Time Complexity

Since the operations inside the inner loop take constant time, the overall time complexity depends on how many times the inner loop executes in total.

For i = 0, the inner loop will run for (n-1) times.
For i = 1, the inner loop will run for (n-2) times.
For i = 2, the inner loop will run for (n-3) times.
.
.
.
For i = n - 2, the inner loop will run once.

Total = (n-1) + (n-2) + (n-3) + ... + 1 = n(n-1)/2.

Hence, overall time complexity = O(n²).

Space Complexity

We are not using any extra space. Hence, overall space complexity = O(1).

Greedy Approach

If we decide to sell on a particular day, the maximum profit we can make is by having bought the stock earlier at the lowest price seen so far.

Algorithm

- min_buy_price_seen_so_far = prices[0];

- max_profit = 0;
- for i in range = [1, prices.length]:
    - if prices[i] < min_buy_price_seen_so_far:
        // update the minimum buy price seen so far
        - min_buy_price_seen_so_far = prices[i];
    - else if prices[i] > min_buy_price_seen_so_far:
        - current_profit = prices[i] - min_buy_price_seen_so_far;
        // checks if selling on the current day improves the best profit
        - max_profit = max(max_profit, current_profit);

- return max_profit;

Visualization

Time Complexity

We are only iterating over the prices array once. Hence, overall time complexity = O(n).

Space Complexity

We are not using any extra space. Hence, overall space complexity = O(1).