by Lead by code Jun 28, 2024 iOS

Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock

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

Here is the Swift implementation of the maxProfit function for finding the maximum profit from buying and selling a stock where you can only buy and sell once:

var prices = [7,6,4,3,1]
func maxProfit(_ prices: [Int]) -> Int {
    var profit = 0
    for i in 0..<prices.count {
        for j in i..<prices.count {
            print("\(prices[j])  - \(prices[i]) =  \(profit)")
            if(prices[j] - prices[i]) > profit {
                profit = prices[j] - prices[i]
            }
        }
    }
    return profit
}

for O(n2)

2nd Solution

func maxProfit(_ prices: [Int]) -> Int {
    var minPrice = Int.max
    var maxProfit = 0
    
    for price in prices {
        // Update the minimum price if the current price is lower
        if price < minPrice {
            minPrice = price
        }
        
        // Calculate the potential profit if we sold at the current price
        let potentialProfit = price - minPrice
        
        // Update the maximum profit if the potential profit is higher
        if potentialProfit > maxProfit {
            maxProfit = potentialProfit
        }
    }
    
    return maxProfit
}

// Example usage:
let prices = [7, 1, 5, 3, 6, 4]
let profit = maxProfit(prices)
print(profit) // Output: 5

Table of Contents

Explanation:

  1. Initialization:
    • minPrice is initialized to the maximum integer value (Int.max) to ensure it will be updated to any price in the array.
    • maxProfit is initialized to 0 to keep track of the maximum profit.
  2. Iterate Through Prices:
    • For each price in the array:
      • Update minPrice to the minimum value between the current minPrice and the current price.
      • Calculate potentialProfit as the difference between the current price and minPrice.
      • Update maxProfit to the maximum value between the current maxProfit and potentialProfit.
  3. Return Result:
    • Return the value of maxProfit, which represents the maximum profit possible by buying and selling once.

This implementation ensures that the maximum profit is calculated efficiently with a time complexity of O(n)O(n)O(n), where nnn is the number of days (prices in the array).

func maxProfit(_ prices: [Int]) -> Int {
        guard prices.count > 1 else {
            return 0
        }
        var minPriceSoFar: Int = prices[0]
        var maxProfit: Int = 0
        for index in 1 ..< prices.count {
            let profit = prices[index] - minPriceSoFar
            maxProfit = max(profit, maxProfit)
            minPriceSoFar = min(minPriceSoFar, prices[index])
        }
        return maxProfit
    }

Table of Contents

→ Index