[LeetCode in Swift] Best Time to Buy and Sell Stock

Hello this is Derek! 👋

I’m starting a new blog series called LeetCode in Swift, where I solve LeetCode challenges in Swift, as I am in the middle of job hunting process and I need to prepare for possible upcoming coding interview.

This question is an easy difficulty in LeetCode and shows history of being asked this question from interviews at Amazon, Apple, Yandex, Facebook, and Adobe for 0–6 months of experience interviewees.

Disclaimer: I am not an experienced developer nor I have a Computer Science education background. My solution may not be the most efficient or effective approach in solving the problem. The reason why I am writing this in blog series is to help these logics, algorithms and approach to stick into my head, and to possibly help absolute beginners who is also facing similar problems.

Today’s challenge: 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

Approach and Thought Process

Our goal is to maximize our profit by picking the best day to buy a stock and a different day in the future to sell that stock. Here’s a key difference from last week’s question — we are only allowed one transaction, meaning we can only buy once and sell once.

To find the maximum profit, we’ll use a simple but effective algorithm:

1. Track the minimum price encountered so far.
2. Calculate the potential profit (current price minus minimum price).
3. Keep track of the maximum profit we’ve seen.

Let’s go through this process in detail:

Step 1: Initialize minPrice and maxProfit

We start by initializing two variables, minPrice to track the minimum price we have encountered and maxProfit to keep track of the maximum profit we can make. We initially set minPrice to Int.max (a placeholder for infinity in our case) and maxProfit to 0.

var minPrice = Int.max
var maxProfit = 0

Step 2: Iterate Over Array

Next, we iterate over the array of prices. For each price, we first check if it is less than our current minPrice. If it is, we update minPrice. Otherwise, we calculate the potential profit (current price — minPrice) and check if this profit is greater than our current maxProfit. If it is, we update maxProfit.

for price in prices {
      if price < minPrice {
          minPrice = price
      } else if price - minPrice > maxProfit {
          maxProfit = price - minPrice
      }
    }

Step 3: Return Maximum Profit

Finally, we return the maximum profit, which is the best we could do with one buy and one sell operation.

return maxProfit

Step 4: Implement Solution

So our complete solution would look like this:

class Solution {
  func maxProfit(_ prices: [Int]) -> Int {

    var minPrice = Int.max
    var maxProfit = 0
    
    for price in prices {
      if price < minPrice {
          minPrice = price
      } else if price - minPrice > maxProfit {
          maxProfit = price - minPrice
      }
    }

    return maxProfit
  }
}

Walkthrough Example

Let’s walk through an example with the following:

input: prices = [7,1,5,3,6,4]

Our minPrice is initialized to Int.max and maxProfit to 0.

During the first iteration, price is 7. Since 7 is less than Int.max, we update minPrice to 7. MaxProfit remains 0 as we have no profit yet.

On the second day, the price drops to 1, which is less than our current minPrice (7), so we update minPrice to 1. MaxProfit remains 0.

On the third day, the price is 5. This is more than our minPrice (1), so we calculate the profit: 5–1 = 4. Since 4 is greater than our current maxProfit (0), we update maxProfit to 4.

We continue this process for the rest of the array. In the end, our maxProfit is 5, which is the maximum profit we can get by buying and selling the stock only once.

Let’s test it to see if it passes in LeetCode!

And just like that, we have successfully solved another problem!

Time and Space Complexity Analysis

The time complexity of our solution is O(n), where n is the number of days. This is because we iterate over the array of prices once.

The space complexity is O(1), as we only use a constant amount of space to store our variables.

I hope this explanation was helpful! As always, please feel free to ask any questions or share your thoughts in the comments section.

Stay tuned for more LeetCode solutions in Swift.

Until then, happy coding! 🔥