LeetCode 121 & 122.

Intro

LeetCode 121 & LeetCode 122 are similiar so here I put them in a same page.

LeetCode 121. 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.

Intuition

Got the point that we can only buy & sell stock once. As a result, we can divide the problem into several sub-problems:

• calculate the max profit we can earn while buying stock on each day (because there must be a transaction if max profit was existed)
• compare results

The time complexity of comparison should be O(n).

Approach

Now, we need to figure out: Calculate the max profit we can earn while buying stock on each day.

We know if we buy stock on day i (1<=i<=n), we have to sell it on day k (i< k <=n). In addition, stock price on day k should be the highest in the range of days (i to n). Here comes two constraints:

• buy on day i & sell on day k (1 <= i < k <= n)
• prices[k] >= prices[x] (i < x <= n)

First set a variable to keep the max price during day x to day n (represents prices[k]). Then create an array to record max profit while buying stock on day i, the value should be prices[k]-prices[i]. Finally, do the comparison of each day’s max profit.

Complexity

• Time complexity: O(n)

• Space complexity: O(n)

Code

class Solution {
    // LeetCode 121: Best time to Buy and Sell Stock 
    public int maxProfit(int[] prices) {
        int max = prices[prices.length-1];
        int[] maxProfit = new int[prices.length];
        for (int i=prices.length-2; i>=0; i--) {
            maxProfit[i] = Math.max(0, max - prices[i]);
            max = Math.max(max, prices[i]);
        }
        max = 0;
        for (int mp: maxProfit) {
            max = Math.max(max, mp);
        }
        return max;
    }
}

LeetCode 122. 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.

Intuition

Since we can sell and buy stock on the same day, we can buy stock whatever prices go down or high. If prices go down then we sell it immediately. Otherwise, we sell it on the next day.

Approach

Use Greedy Algorithm

Complexity

• Time complexity: O(n)

• Space complexity: O(1)

Code

class Solution {
    // LeetCode 122: Best time to Buy and Sell Stock II
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i=0; i<prices.length; i++) {
            if (i+1 < prices.length && prices[i] < prices[i+1] ) {
                profit += prices[i+1]-prices[i];
            }
        }
        return profit;
    }
}

Check out the description of these two problems at LC 121, LC 122.