Solving LeetCode's Best Time to Buy and Sell Stock Challenge

The Problem:

We are given an array prices, which stores the stock value for each day -represented by the indices. They expect us to return the maximum profit possible by buying stock on one day and selling it on another day. Buy must happen before Sell and they cannot happen on the same day. Buy and Sell can happen can only happen once.

The Solution:

You can of course use the nested loops approach, I will even write it down as it does not defy any time complexity constraints -as they are not given.

• Nested Loops (Cuz its ez)

• Kadane’s Algorithm (useful in many quesitons)

Nested Loops

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        for (int i = 0; i < size(prices); ++i) {
            for (int j = i; j < size(prices); ++j) {
                profit = prices[j] - prices[i] > profit ? prices[j] - prices[i] : profit; //:(
            }
        }
        return profit;
    }
};

I can’t believe I spent almost an hour for this, only to find out that I had accidentally switched i with j.

Time Complexity is O(n²).

Kadane’s Algorithm

I remember this algorithm as the one where we store the return variable and compare var outside the for loop. Then use them as constraints and storage vars inside loops.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = prices[0];
        int profit = 0;
        for (int i = 1; i < size(prices); ++i) {
            if (buy > prices[i]) { // updates the buy price,i.e., fidns the min and saves it in sequence
                buy = prices[i];
            } else if (profit < prices[i] - buy) { // if this iteration has not found a new min
// then it uses the old min to calulate a new profit with the current stock value of the iterated index.
                profit = prices[i] - buy; // jus updates the return if the difference is max till now
            }
        }
        return profit;
    }
};

The core concept leverages the fact that the only element that needs to remembered throughout the program is primarily the buy day. It influences and commands if and when we sell.

Time Complexity is O(n).

---

Kadane’s Algorithm is popular. Try to understand it better → more to myself. You could try it too.