# Best Time to Buy and Sell Stock
**Difficulty:** EASY
[External](https://leetcode.com/problems/best-time-to-buy-and-sell-stock)
Canonical: https://scaleengineer.com/dsa/problems/best-time-to-buy-and-sell-stock
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Accolite](https://scaleengineer.com/companies/accolite), [Agoda](https://scaleengineer.com/companies/agoda), [Akamai](https://scaleengineer.com/companies/akamai), [American Express](https://scaleengineer.com/companies/american-express), [Atlassian](https://scaleengineer.com/companies/atlassian), [BNY Mellon](https://scaleengineer.com/companies/bny-mellon), [Bolt](https://scaleengineer.com/companies/bolt), [ByteDance](https://scaleengineer.com/companies/bytedance), [Capgemini](https://scaleengineer.com/companies/capgemini), [Cisco](https://scaleengineer.com/companies/cisco), [Deloitte](https://scaleengineer.com/companies/deloitte), [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Expedia](https://scaleengineer.com/companies/expedia), [FPT](https://scaleengineer.com/companies/fpt), [Flipkart](https://scaleengineer.com/companies/flipkart), [FreshWorks](https://scaleengineer.com/companies/freshworks), [Garmin](https://scaleengineer.com/companies/garmin), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [Intel](https://scaleengineer.com/companies/intel), [Intuit](https://scaleengineer.com/companies/intuit), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Mastercard](https://scaleengineer.com/companies/mastercard), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Myntra](https://scaleengineer.com/companies/myntra), [Nutanix](https://scaleengineer.com/companies/nutanix), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [Ozon](https://scaleengineer.com/companies/ozon), [PayPal](https://scaleengineer.com/companies/paypal), [Pwc](https://scaleengineer.com/companies/pwc), [Roblox](https://scaleengineer.com/companies/roblox), [SAP](https://scaleengineer.com/companies/sap), [Samsung](https://scaleengineer.com/companies/samsung), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Shopee](https://scaleengineer.com/companies/shopee), [Siemens](https://scaleengineer.com/companies/siemens), [Slice](https://scaleengineer.com/companies/slice), [Snowflake](https://scaleengineer.com/companies/snowflake), [Tech Mahindra](https://scaleengineer.com/companies/tech-mahindra), [Tekion](https://scaleengineer.com/companies/tekion), [TikTok](https://scaleengineer.com/companies/tiktok), [UKG](https://scaleengineer.com/companies/ukg), [Uber](https://scaleengineer.com/companies/uber), [VMware](https://scaleengineer.com/companies/vmware), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [athenahealth](https://scaleengineer.com/companies/athenahealth), [eBay](https://scaleengineer.com/companies/ebay), [tcs](https://scaleengineer.com/companies/tcs), [Capital One](https://scaleengineer.com/companies/capital-one), [Zopsmart](https://scaleengineer.com/companies/zopsmart), [josh technology](https://scaleengineer.com/companies/josh-technology), [Airtel](https://scaleengineer.com/companies/airtel), [Netflix](https://scaleengineer.com/companies/netflix), [Salesforce](https://scaleengineer.com/companies/salesforce), [Tesla](https://scaleengineer.com/companies/tesla), [ThoughtWorks](https://scaleengineer.com/companies/thoughtworks), [Turing](https://scaleengineer.com/companies/turing), [opentext](https://scaleengineer.com/companies/opentext), [Citadel](https://scaleengineer.com/companies/citadel), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Snap](https://scaleengineer.com/companies/snap), [Swiggy](https://scaleengineer.com/companies/swiggy), [BlackRock](https://scaleengineer.com/companies/blackrock), [Media.net](https://scaleengineer.com/companies/media.net), [PhonePe](https://scaleengineer.com/companies/phonepe), [RBC](https://scaleengineer.com/companies/rbc), [Microstrategy](https://scaleengineer.com/companies/microstrategy), [carwale](https://scaleengineer.com/companies/carwale), [HSBC](https://scaleengineer.com/companies/hsbc), [HashedIn](https://scaleengineer.com/companies/hashedin), [QBurst](https://scaleengineer.com/companies/qburst), [Sprinklr](https://scaleengineer.com/companies/sprinklr), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [CME Group](https://scaleengineer.com/companies/cme-group), [Rakuten](https://scaleengineer.com/companies/rakuten), [Zoox](https://scaleengineer.com/companies/zoox), [Bank of America](https://scaleengineer.com/companies/bank-of-america), [Millennium](https://scaleengineer.com/companies/millennium), [Tripadvisor](https://scaleengineer.com/companies/tripadvisor), [UBS](https://scaleengineer.com/companies/ubs), [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies), [Two Sigma](https://scaleengineer.com/companies/two-sigma), [Instacart](https://scaleengineer.com/companies/instacart), [CrowdStrike](https://scaleengineer.com/companies/crowdstrike), [Groww](https://scaleengineer.com/companies/groww), [DevRev](https://scaleengineer.com/companies/devrev), [Robinhood](https://scaleengineer.com/companies/robinhood), [AQR Capital Management](https://scaleengineer.com/companies/aqr-capital-management), [Bentley Systems](https://scaleengineer.com/companies/bentley-systems), [Blizzard](https://scaleengineer.com/companies/blizzard), [Citigroup](https://scaleengineer.com/companies/citigroup), [Cloudera](https://scaleengineer.com/companies/cloudera), [DRW](https://scaleengineer.com/companies/drw), [Ola Cabs](https://scaleengineer.com/companies/ola-cabs), [Optiver](https://scaleengineer.com/companies/optiver), [Remitly](https://scaleengineer.com/companies/remitly), [Snapdeal](https://scaleengineer.com/companies/snapdeal), [Societe Generale](https://scaleengineer.com/companies/societe-generale), [Sony](https://scaleengineer.com/companies/sony), [The Trade Desk](https://scaleengineer.com/companies/the-trade-desk), [Tiger Analytics](https://scaleengineer.com/companies/tiger-analytics), [Toast](https://scaleengineer.com/companies/toast), [zeta suite](https://scaleengineer.com/companies/zeta-suite)
---
## Problem
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.

Return _the maximum profit you can achieve from this transaction_. If you cannot achieve any profit, return `0`.

**Example 1:**

**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.

**Example 2:**

**Input:** prices = [7,6,4,3,1]
**Output:** 0
**Explanation:** In this case, no transactions are done and the max profit = 0.

**Constraints:**

* `1 <= prices.length <= 105`
* `0 <= prices[i] <= 104`

# Approaches
## Brute Force Approach
This approach involves checking every possible pair of buy and sell days to find the one that yields the maximum profit. We use nested loops to iterate through all valid transaction pairs.
**Time:** O(n^2) · **Space:** O(1)
**Pros:** Simple to understand and implement.; Correctly solves the problem for small inputs.
**Cons:** Highly inefficient for large arrays.; Will result in a 'Time Limit Exceeded' error on most online judges due to the O(n^2) complexity.
### Explanation
The brute force method systematically calculates the profit for every possible transaction. We assume we buy on day `i` and sell on a future day `j` (where `j > i`).

We use two nested loops. The outer loop iterates through each day `i` from the first to the second-to-last day, considering it as the potential buy day. The inner loop iterates through each subsequent day `j` from `i+1` to the last day, considering it as the potential sell day.

For each pair of `(buy_price, sell_price)`, we calculate the profit. We maintain a variable `maxProfit` which is updated whenever we find a profit greater than the current `maxProfit`.

If no profitable transaction can be made (i.e., prices are always decreasing), the `maxProfit` will remain at its initial value of 0.

```java
class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxProfit) {
                    maxProfit = profit;
                }
            }
        }
        return maxProfit;
    }
}
```
### Algorithm
- Initialize a variable `maxProfit` to 0.
- Iterate through the `prices` array with an index `i` from 0 to `n-2` (representing the buy day).
- Inside this loop, start another loop with an index `j` from `i+1` to `n-1` (representing the sell day).
- Calculate the current profit: `profit = prices[j] - prices[i]`.
- Compare `profit` with `maxProfit`. If `profit` is greater, update `maxProfit = profit`.
- After the loops complete, return `maxProfit`.

## One Pass Approach
A more efficient approach is to iterate through the price list just once. We maintain two variables: the minimum price encountered so far and the maximum profit seen. This allows us to find the solution in linear time.
**Time:** O(n) · **Space:** O(1)
**Pros:** Extremely efficient with linear time complexity.; Uses constant extra space.; This is the optimal solution for this problem.
**Cons:** May be slightly less intuitive to devise compared to the brute-force method.
### Explanation
This optimized approach avoids the nested loops by iterating through the prices array a single time. The key idea is that the maximum profit at any given day `i` is the difference between the price on that day `prices[i]` and the minimum price encountered on any day before `i`.

We initialize `minPrice` to a very large number (or the first price) and `maxProfit` to 0.

We then traverse the `prices` array. For each price, we first check if it's a new minimum price. If it is, we update `minPrice`. Then, we calculate the potential profit if we were to sell on the current day using the `minPrice` found so far (`prices[i] - minPrice`). We update `maxProfit` if this potential profit is larger than the current `maxProfit`.

By the end of the single pass, we will have found the overall maximum profit.

```java
class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else if (prices[i] - minPrice > maxProfit) {
                maxProfit = prices[i] - minPrice;
            }
        }
        return maxProfit;
    }
}
```
### Algorithm
- Initialize `minPrice` to `Integer.MAX_VALUE`.
- Initialize `maxProfit` to 0.
- Iterate through the `prices` array with an index `i` from 0 to `n-1`.
- For each price `prices[i]`:
  - If `prices[i]` is less than `minPrice`, update `minPrice = prices[i]`.
  - Else, calculate the potential profit `prices[i] - minPrice`. If this is greater than `maxProfit`, update `maxProfit`.
- After the loop, return `maxProfit`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int MaxProfit(int[] prices) {
        int ans = 0, mi = prices[0];
        foreach(int v in prices) {
            ans = Math.Max(ans, v - mi);
            mi = Math.Min(mi, v);
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  int maxProfit(int[] prices) {
    int ans = 0, mi = prices[0];
    for (int v : prices) {
      ans = Math.max(ans, v - mi);
      mi = Math.min(mi, v);
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} prices * @return {number} */ var maxProfit = function (
  prices,
) {
  let ans = 0;
  let mi = prices[0];
  for (const v of prices) {
    ans = Math.max(ans, v - mi);
    mi = Math.min(mi, v);
  }
  return ans;
};

```

### CPP

```cpp
class Solution {
public:
  int maxProfit(vector<int> &prices) {
    int ans = 0, mi = prices[0];
    for (int &v : prices) {
      ans = max(ans, v - mi);
      mi = min(mi, v);
    }
    return ans;
  }
};

```

### Python

```python
''' >>> import math >>> a = math.inf >>> a inf >>> x = float('-inf') >>> y = float('inf') >>> print(x < y) # Output: True True >>> >>> z = -math.inf >>> x==z True ''' class Solution : def maxProfit ( self , prices : List [ int ]) -> int : ans , mi = 0 , inf for v in prices : mi = min ( mi , v ) ans = max ( ans , v - mi ) return ans ############ class Solution ( object ): def maxProfit ( self , prices ): """ :type prices: List[int] :rtype: int """ if not prices : return 0 ans = 0 pre = prices [ 0 ] for i in range ( 1 , len ( prices )): pre = min ( pre , prices [ i ]) ans = max ( prices [ i ] - pre , ans ) return ans
```