Coding Interview Prep: 2 Solutions for Best Time To Buy and Sell Stock

Solution 1 — Brute Force

/*
 Brute Force Method (2 for loops)
 Complexity: O(n^2)
 Space: O(1)
 Runtime: 43 ms
  */
var maxProfit_bruteForce = function(prices) {
    let maxProfit = 0;
    for (let i=0; i<prices.length; i++){
        for (let j=i+1; j<prices.length; j++){
            const profit = prices[j]-prices[i];
            if (profit > maxProfit){
                maxProfit = profit;
            }
        }
   }
   return maxProfit;
};

Solution 2 — Sliding Window/Kadane’s Algorithm

/*
Sliding Window
Time Complexity: O(n) where n is the length of the prices array
Space Complexity: O(1) as only a constant amount of extra space is used
*/
var maxProfit = function(prices){
    let left = 0;
    let right = 1;
    let maxProfit = 0;

    while (right < prices.length){
        const profit = prices[right]-prices[left];
        if (prices[right] > prices[left]){
            maxProfit = Math.max(maxProfit, profit);
        } else {
            left = right;
        }
        right++;
    }
    return maxProfit;
}

Kadane’s Algorithm is a dynamic programming technique used to find the maximum subarray sum in an array of numbers. The algorithm maintains two variables: maxProfit and profit. profit represents the maximum sum ending at the current position and maxProfit represents the maximum subarray sum encountered so far.