Problem statement

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.
Link to problem

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.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Solutions

Approach 1: Simpleton

The twist in this problem is that it is in series, so we cannot just take min and max and call it a day.

This approach is rather simple, hence the name, and also the first approach that I thought of.

Basically, we iterate over the array while keeping track of our profits and minimum.

Pseudocode

minimum = prices[0]
profit = 0

loop over prices skipping first element
    if currentPrice < minimum
        minimum = currentPrice
    
    if currentPrice - minimum > profit
        profit = currentPrice - minimum

return profit

Implementation in Rust

fn max_profit(prices: Vec<i32>) -> i32 {
    let mut profit: i32 = 0;
    let mut minimum: i32 = prices[0];

    for current_price in prices.iter().skip(1) {
        if current_price < &minimum {
            minimum = *current_price 
        }

        if current_price - minimum > profit {
            profit = current_price - minimum;
        }
    }
    profit
}

Time Complexity: $O(n)$
Runtime on LeetCode: $12$ms

Approach 2: Two Pointers

It uses two pointers, one for buying and another for selling.
Similar to the above approach, we iterate over the entire array but use pointers to keep track of buying/selling.

I found this from neetcode but it’s pretty much the same as my approach, surprisingly it is also slightly slower than the simpleton approach. Guess simple truly is better than complex, right Guido?

Pseudocode

left_ptr = 0  (buy ptr)
right_ptr = 1 (sell ptr)
max_profit = 0

loop over prices until right_ptr is at the end
    if price[left_ptr] < price[right_ptr]
        profit = price[right_ptr] - price[left_ptr]
        if profit > max_profit
            max_profit = profit
    else
        left_ptr = right_ptr
    right_ptr += 1

return max_profit

Implementation in Rust

fn max_profit(prices: Vec<i32>) -> i32 {
    let mut max_profit: i32 = 0;
    let mut left_ptr = 0;
    let mut right_ptr = 1;

    while right_ptr < prices.len() - 1 {
        if prices[left_ptr] < prices[right_ptr] {
            let profit = prices[right_ptr] - prices[left_ptr];

            if profit > max_profit {
                max_profit = profit;
            }
        } else {
            left_ptr = right_ptr;
        }
        right_ptr += 1
    }
    max_profit
}

Time Complexity: $O(n)$
Runtime on leetcode: $25$ms