Best Time To Buy and Sell Stock.

Best Time To Buy and Sell Stock.

Blind 75. array questions.

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.

anyone reading this can easily forget how this algorithm problem is solved. If you don't understand the application of this in the real world, It's easy to forget quickly. So let's understand it in detail.

Why learn this algorithm?

1. Financial Trading Systems:
2. As mentioned by the question itself, implementing strategies to maximise profit in stock markets
3. Identifying potential maximum losses or gains over a period
4. Ecommerce:
5. Adjust prices based on the demand patterns to maximize revenue
6. Determining best times for shipping to minimize costs.
7. Travel Industry:
8. Airline ticket pricing:Optimising when to release seats at different price points.
9. Netflix:
10. Content acquisitions: Determining the best times to buy rights for shows and movies
11. Facebook:
12. Facebook's News Feed Content Optimization:

• User engagement pattern:
• 6 AM: Low
• 12 PM: Medium
• 6 PM: Peak
• 12 AM: Low

1. Strategy:
2. "Buy" (gather) content when engagement is low
3. Sell" (display) content when engagement is high
4. Action:
5. Collect and process more content during low periods
6. Show best content during peak times
7. Benefits:
8. Efficient use of processing power

6.Amazon:

1. Amazon's Beach Umbrella Pricing Strategy:
2. Price/demand pattern:

• January: $20 (Low)
• July: $45 (Peak)
• November: $20 (Low)
• Strategy:
• Buy inventory in November (lowest price)
• Sell at peak in July (highest price)
• Action:
• Stock up in November
• Start selling at $20 in January
• Increase price gradually to $45 by July
• Decrease price after summer
• Benefits:
• Buy low (November)
• Sell high (July)
• Maximize profit

These could be the reasons why company test your knowledge on Buy and Sell Stock Questions.

Now's let's see how we can solve the problem.

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.

     1 2 3 4 5 6 day

     0 1 2 3 4 5 index 

    [7, 1, 5, 3, 6, 4] price

    1. buy @ 7 1st data, iterate over the array

      a. we find we won't make any profit

    2. buy @ 1, 2nd day, iterate 

      a. 3rd day prices goes to 5

        profit = 5-1 = 4

      b. 4th day, price @ 3

        profit = 3 -1 = 2

      c. 5th day, price @ 6

        profit = 6 -1 = 5

      d. 6th day, price @4

        profit = 4 -1 = 3

    --------- here we see a pattern ------

    1. we need to iterate over the prices

    2. a price need to be compared to another price

    3. we need to calculate profit on every time we updates these values

    Obvious way to solve this problem:

    brute force where we run two loops and calculate prices on each iterattion

function bruteForce(prices) {

  let maxProfit = 0

  for (i = 0; i < prices.length; i++) {

    // we need to buy first and sell later

    let buyingAt = prices[i]

    for (j = i + 1; j < prices.length; j++) {

      let sellingAt = prices[j]

      // profit is caluclate from sell - buy

      let currentProfit = sellingAt - buyingAt

      maxProfit = Math.max(maxProfit, currentProfit)

    }

  }

  return maxProfit

}

This is a brute force approach, now let's see how we can take this solution and optimize it.

How to optimize?

We need to understand Kodana's algorithm to optimize this.

How can we optimize a nested loop to a single iteration?

This optimization is inspired by a famous algorithm called Kadane's algorithm. While Kadane's algorithm is typically used to find the maximum subarray sum, we can adapt its core idea to solve our stock problem.

function kodaneAlgorithm(nums){

let currentSum =0

let maxSum = -Infinity

for(let num of nums){

currentSum = Math.max(currentSum, currentSum + num)

maxSum = Math.max(maxSum, currentSum)

}

}

let's see how we can use this algo to solve our current problem:

1. Check to buyIn from 1st day
2. Store out maxProfit i.e 0
3. we need to iterate over the prices
4. if today's price is low
5. update out buyIn
6. if currentProfit = todayPrice - buyIn, is greater than maxProfit
7. update maxProfit

function OptimizeSolution(prices){

let buyIn = prices[0]

let maxProfit = 0

for(let day = 0; day < prices.length; day++){

buyIn = Math.min(buyIn, prices[day])

let currentProfit = prices[day] - buyIn

maxProfit = Math.max(maxProfit, currentProfit)

}

return maxProfit.

}