Best Time to Buy and Sell Stock  II Leetcode Solution

Difficulty Level Easy
Frequently asked in Amazon DE Shaw Facebook Microsoft Morgan Stanley Uber
algorithms Array coding Greedy Interview interviewprep LeetCode LeetCodeSolutionsViews 6448

Problem statement

In the problem “Best Time to Buy and Sell Stock  II,” we are given an array where each element in the array contains the price of the given stock on that day.

The definition of the transaction is buying one share of stock and selling that one share of stock.

Our task is to find the maximum profit under the following restrictions:

  1. we can’t buy a new stock if we have not sold the previous stock. that is at a time we can have at most one stock.
  2. we can do as many transactions as we want.

Example

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

Explanation: maximum profit that can be obtained is 7. Following is the transaction detail:

First day: rest

Second day: buy

Third day: sell

Fourth day: buy

Fifth day: sell

Sixth day: rest

Approach for Best Time to Buy and Sell Stock  II Leetcode Solution

As we don’t have any restrictions on the number of transactions so we will think of a greedy algorithm here. So every time we will buy a stock at a minimum price and sell it at a maximum price. We can summarize it as, at each minima we will buy a stock and at each maxima, we will sell a stock.  This is explained in the figure given below. It is a plot between the stock price and the days. leetcode solution to Best Time to Buy and Sell Stock  II

We can make it simpler if we observe that a maxima is formed when small values are added to minima. So in spite of tracking every minima and maxima to calculate the maximum profit, we can directly add those values to our profit for which we found a positive slope that is prices[i]>prices[i-1]. The addition of all such values will give us maximum profit.

leetcode solution to Best Time to Buy and Sell Stock  II

Implementation

C++ code for Best Time to Buy and Sell Stock II

#include <bits/stdc++.h> 
using namespace std; 
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int ans = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i - 1])
                ans += prices[i] - prices[i - 1];
        }
        return ans;
    }
int main() 
{ 
 vector<int> arr = { 7,1,5,3,6,4 }; 
 cout<<maxProfit(arr)<<endl; 
 return 0;
}
7

Java code for Best Time to Buy and Sell Stock II

import java.util.Arrays; 
public class Tutorialcup {
     public static int maxProfit(int[] prices) {
        int ans = 0;
        int n=prices.length;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i - 1])
                ans += prices[i] - prices[i - 1];
        }
        return ans;
    }
  public static void main(String[] args) {
    int [] arr = {7,1,5,3,6,4}; 
    int ans=  maxProfit(arr);
    System.out.println(ans);
  }
}
7

Complexity Analysis of Best Time to Buy and Sell Stock  II Leetcode Solution

Time complexity

The time complexity of the above code is O(n) because we are traversing the price array only once. Here n is the length of the price array.

Space complexity

The space complexity of the above code is O(1) because we using memory only to store the answer.

References

Translate »