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

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 a Medium difficulty in LeetCode and shows history of being asked this question from interviews at Yahoo and Citadel 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 II

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Constraints:

• 1 <= prices.length <= 3 * 104
• 0 <= prices[i] <= 104

Approach and Thought Process

We need to find the maximum profit that we can achieve by buying and selling stocks. The key point here is that we can conduct as many transactions as we like, but we must sell the stock before we can buy again.

Our approach to solving this problem efficiently involves using a Greedy algorithm. This type of algorithm makes the locally optimal choice at each step with the hope of finding a global optimum.

In other words, we aim to make the most profitable transaction at each step. If we can make a profit by selling a stock tomorrow (i.e., tomorrow’s price is higher than today’s), we should do it.

Let’s break down the process:

Step 1. Initialize maxProfit

We start by initializing a variable maxProfit to keep track of the total profit we make from all transactions.

var maxProfit = 0

Step 2. Iterate Over Array

Next, we iterate over the array of prices. For each day (except the last one), we compare the price of the stock on that day with the price on the next day.

for i in 0..<prices.count - 1 {

Step 3. Sell if Profitable

If the price of the stock is less today than it is tomorrow, we buy the stock today and sell it tomorrow. The profit from this transaction (tomorrow’s price minus today’s price) is added to our total profit.

if prices[i] < prices[i + 1] {
    maxProfit += prices[i + 1] - prices[i]
}

Step 4. Return Maximum Profit

Finally, we return the total profit made from all transactions.

return maxProfit

Step 5. Implement Solution

So our complete solution would look like this:

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        // Buy low, sell high
        // Greedy Algorithm
        
        // Create a property to keep track of the max Profit
        var maxProfit = 0
        for i in 0..<prices.count - 1 {
            if prices[i] < prices[i + 1] {
                maxProfit += prices[i + 1] - prices[i]
            }
            // We are not worried about where prices[i] > prices[i + 1]
        }
        // return total appended maxProfit
        return maxProfit
    }
}

Walkthrough Example

Let’s walk through an example with the following input:

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

1. On day 1, the price is 7. Since the price drops to 1 on day 2, we don’t buy the stock on day 1.
2. On day 2, the price is 1. Since the price rises to 5 on day 3, we buy the stock on day 2.
3. On day 3, the price is 5. We sell the stock bought on day 2 and make a profit of 5–1 = 4.
4. On day 4, the price is 3. Since the price rises to 6 on day 5, we buy the stock on day 4.
5. On day 5, the price is 6. We sell the stock bought on day 4 and make a profit of 6–3 = 3.
6. On day 6, the price is 4. Since there is no day after day 6, we don’t buy the stock.

Our total profit is 4 + 3 = 7.

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 breakdown of the solution helps you understand how to tackle this problem! If you have any questions or suggestions, feel free to drop a comment. More LeetCode challenges in Swift are on the way.

Stay tuned and happy coding! 🔥