One Pager Cheat Sheet

• The interview question asks to create a stockOptimizer method to maximize profit from an array of stock prices, by buying once and selling once, given the constraint that a stock cannot be sold before it is bought, with input array length <= 100000, non-zero integer rates and a maximum price <= 2147483647, within a time complexity of O(n) and space complexity O(1).
• In order to calculate the greatest possible profit from buying and selling a stock represented by an array of prices, one must iterate through each day, comparing the price of that day and only the prices on subsequent days using nested loops and adhering to the rule of buying before selling, all the while tracking the minimum price so far and the maximum profit obtainable, which is the difference between the current price and the minimum price.
• The code utilizes nested loops with a time complexity of O(n^2), which can slow performance for larger datasets, but can be optimized to an O(n) solution by using only one loop.
• The provided solution has a time complexity of O(n^2) due to the use of nested loops, which means for every additional input, the algorithm needs to perform work proportional to the square of the number of inputs.
• When trying to find an answer, identifying patterns can be helpful, and a useful realization is that we can iterate from the end of an array, focusing first on the selling price before finding the best buying price by updating the maxPrice while moving towards the start, which still provides an O(n) solution.
• The problem involves iterating from the end to the beginning of an array, adjusting the maxProfit (highest profit at a specific hour) and minPrice (lowest price thus far) to calculate the maximum possible profit while ensuring the selling price always comes after the buying price.
• To maximize profit in stock trading, it's beneficial to find the maximum difference (profit) and the maximum price from right to left in an array, keeping the order of prices, and updating the current max price (curMax) and the maximum profit (maxProfit) as we move towards the front of the array with conditional programming logic.
• Through iterations of an algorithm on a sample array prices = [ 10, 7, 6, 2, 9, 4 ], running from the array's end, variables maxProfit and curMax are updated comparing potential profits and maximum price respectively, resulting in a maximum profit of 7, achieved by purchasing at the price of 2 and selling at 9.
• The described reverse-traversal algorithm effectively calculates the best profit in a selling price perspective by considering each day as a potential selling day, and uses curMax and maxProfit for efficient tracking of the best selling price and corresponding profit.
• The algorithm computes the maximum profit from stock trading by tracking the highest selling price (curMax) as it scans the array of daily stock prices in reverse, and continually comparing the potential profit (curProfit) with the current maximum profit (maxProfit) to ensure the highest possible profit is chosen, resulting in maxProfit representing the best attainable profit.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

function stockOptimizer(prices) {

  if (!prices.length) {

    return 0;

  }

  if (prices.length == 1) {

    return 0;

  }

  let curMax = prices[prices.length - 1];

  let maxProfit = 0;

  for (let i = prices.length - 1; i >= 0; i--) {

    const temp = prices[i];

    if (temp > curMax) {

      curMax = temp;

    }

    const curProfit = curMax - temp;

    if (curProfit > maxProfit) {

      maxProfit = curProfit;

    }

  }

  return maxProfit;

}

​

try {

  assert.deepEqual(stockOptimizer([14, 20, 9]), 6);

​

  console.log('PASSED: ' + 'stockOptimizer([14,20,9]) should return 6');

} catch (err) {

  console.log(err);

}

​

Alright, well done! Try another walk-through.

If you had any problems with this tutorial, check out the main forum thread here.