---
# System prepended metadata

title: 121. Best Time to Buy And Sell Stock
tags: [Array]

---

## Problem

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

:::spoiler **Optimal Space & Time Complexity**
```
- Time complexity:
- Space complexity:
```
:::

<br>

## Thoughts & Solutions

### 東
![](https://hackmd.io/_uploads/rJS27djan.png)


:::spoiler Code
```javascript=
var maxProfit = function(prices) {
    let maxProfit = 0;
    let buyIdx = 0;
    let sellIdx = 1;
    while ((buyIdx < sellIdx) && (sellIdx < prices.length)){
        const buyPrice = prices[buyIdx];
        const sellPrice = prices[sellIdx];
        let currProfit = sellPrice - buyPrice;
        
        if(currProfit > maxProfit){
            maxProfix = currProfit;
        }
        
        const profitForMoveBuyRight = currProfit - buyPrice + prices[buyIdx + 1];
        const profitForMoveSellRight = currProfit - sellPrice + prices[sellIdx + 1];
        if(profitForMoveBuyRight > profitForMoveSellRight){
            buyIdx++;
        } else {
            sellIdx++;
        }
    }
    return maxProfit;
};
```
:::

<hr/>

### Hao
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/solutions/1735550/python-javascript-easy-solution-with-very-clear-explanation/

1. 直覺會覺得使用左右指針來做，left 找最小值，right 找最大值
2. 更新的邏輯
    1. Fix left
        1. Right > left => update maxProfit
        2. Right < left => left = right
            * 解題重點：可以直接更新是因為這個為目前所見最小值！
    2. Loop ends when right < prices.length

:::spoiler Code
```javascript=

```
:::

<hr/>

### YC
- left-right pointer
    - left pointer is for min value 
- maxProfit: `prices[left] < prices[right]`
- update the pointer:
    - left pointer: when `prices[left] > prices[right]`
    - right pointer: in each loop

:::spoiler Code
```javascript=
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let left = 0;
    let right = 1;
    let maxProfit = 0;
    while(right < prices.length){
        if(prices[left] < prices[right]){
            const profit = prices[right] - prices[left];
            maxProfit = Math.max(maxProfit, profit);
        }
        else{
            left = right;
        }

        right++;
    }
    return maxProfit;
};
```
:::

<hr/>

### Sol

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

1. The difference between two numbers, I need two pointers.
2. How to compare the two pointers?
- [7, 1]: 7 > 1, I can directly skip 7; 1 would get a greater profit.
- [1, 5]: 1 < 5, this could be the maximum profit.

:::spoiler Code
```javascript=
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let maxProfit = 0;
    let first = 0;
    let second = 1;
    while(second < prices.length){
       if(prices[first]< prices[second]){
            const profit = prices[second] - prices[first];
            if(profit > maxProfit) {
                maxProfit = profit;
            }
        }else{
            first = second;
        }
        second++;
    }
    return maxProfit;
};

```
:::

<br>

## Supplement / Discussion


## Live Coding

:::spoiler (東)
```
var maxProfit = function(prices) {
    let maxProfit = 0;
    let buyIdx = 0;
    let sellIdx = prices.length - 1;
    while (buyIdx < sellIdx){
        const currBuyPrice = prices[buyIdx];
        const currSellPrice = prices[sellIdx];
        const currProfit = currSellPrice - currBuyPrice;
        
        if(currProfit > maxProfit){
            maxProfit = currProfit;
        }
        
        const profitForMoveBuyRight = currSellPrice - prices[buyIdx + 1] 
        const profitForMoveSellLeft = -currBuyPrice + prices[sellIdx - 1] 
        
        if(profitForMoveBuyRight > profitForMoveSellLeft){
            buyIdx++;
        } else {
            sellIdx--;
        }
    }
    return maxProfit;
};```
:::
