Best Time to Buy and Sell Stock In C,CPP,JAVA,PYTHON,C#,JS

Problem Statement: Best Time to Buy and Sell Stock

You are given an array of integers where each element represents the price of a stock on a given day. You need to find the maximum profit you can achieve by buying and selling the stock exactly once.

You can assume that you can only make one buy and one sell. The buying must happen before the selling.

Example:

• Input: [7, 1, 5, 3, 6, 4]
• Output: 5
  • Explanation: Buy on day 2 (price = 1), sell on day 5 (price = 6), profit = 6 – 1 = 5.
• Input: [7, 6, 4, 3, 1]
• Output: 0
  • Explanation: In this case, no transaction is done, so the profit is 0.

Approach

1. Brute Force Approach:
   • A straightforward solution would be to check all possible pairs of buy and sell days and calculate the profit for each pair.
   • Time complexity: O(n²), because for each day, we would check all the days after it for possible sell prices.
2. Optimized Approach (Greedy with One Pass):
   • Instead of checking all pairs, we can use the following insight:
     • Track the minimum price seen so far as you iterate through the array.
     • For each day, calculate the profit if you sold the stock on that day (i.e., the difference between the current price and the minimum price).
     • Keep track of the maximum profit during the iteration.
   • Time complexity: O(n), because we only iterate through the array once.

Steps:

• Initialize two variables:
  • min_price to store the minimum price encountered so far.
  • max_profit to store the maximum profit.
• Iterate through the array:
  • For each price, check if it’s lower than the min_price and update min_price accordingly.
  • Calculate the profit for the current day by subtracting the min_price from the current price.
  • Update max_profit if the current profit is greater than the previous max_profit.
• Return the max_profit.

Code Implementations

---

C:

#include <stdio.h>

int maxProfit(int* prices, int pricesSize) {
    int min_price = prices[0];
    int max_profit = 0;
    
    for (int i = 1; i < pricesSize; i++) {
        if (prices[i] < min_price) {
            min_price = prices[i]; // update min price
        } else {
            int profit = prices[i] - min_price;
            if (profit > max_profit) {
                max_profit = profit; // update max profit
            }
        }
    }
    
    return max_profit;
}

int main() {
    int prices[] = {7, 1, 5, 3, 6, 4};
    int pricesSize = sizeof(prices) / sizeof(prices[0]);
    printf("Max profit: %d\n", maxProfit(prices, pricesSize));  // Output: 5
    return 0;
}

---

C++:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxProfit(vector<int>& prices) {
    int min_price = prices[0];
    int max_profit = 0;
    
    for (int i = 1; i < prices.size(); i++) {
        if (prices[i] < min_price) {
            min_price = prices[i]; // update min price
        } else {
            int profit = prices[i] - min_price;
            max_profit = max(max_profit, profit); // update max profit
        }
    }
    
    return max_profit;
}

int main() {
    vector<int> prices = {7, 1, 5, 3, 6, 4};
    cout << "Max profit: " << maxProfit(prices) << endl;  // Output: 5
    return 0;
}

---

Java:

public class BestTimeToBuyAndSellStock {
    public static int maxProfit(int[] prices) {
        int minPrice = prices[0];
        int maxProfit = 0;

        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i]; // update min price
            } else {
                int profit = prices[i] - minPrice;
                maxProfit = Math.max(maxProfit, profit); // update max profit
            }
        }

        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println("Max profit: " + maxProfit(prices));  // Output: 5
    }
}

---

Python:

def maxProfit(prices):
    min_price = prices[0]
    max_profit = 0

    for price in prices[1:]:
        if price < min_price:
            min_price = price  # update min price
        else:
            profit = price - min_price
            max_profit = max(max_profit, profit)  # update max profit

    return max_profit

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

---

C#:

using System;

public class BestTimeToBuyAndSellStock {
    public static int MaxProfit(int[] prices) {
        int minPrice = prices[0];
        int maxProfit = 0;

        for (int i = 1; i < prices.Length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i]; // update min price
            } else {
                int profit = prices[i] - minPrice;
                maxProfit = Math.Max(maxProfit, profit); // update max profit
            }
        }

        return maxProfit;
    }

    static void Main() {
        int[] prices = {7, 1, 5, 3, 6, 4};
        Console.WriteLine("Max profit: " + MaxProfit(prices));  // Output: 5
    }
}

---

JavaScript:

function maxProfit(prices) {
    let minPrice = prices[0];
    let maxProfit = 0;

    for (let i = 1; i < prices.length; i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i]; // update min price
        } else {
            let profit = prices[i] - minPrice;
            maxProfit = Math.max(maxProfit, profit); // update max profit
        }
    }

    return maxProfit;
}

// Example usage
let prices = [7, 1, 5, 3, 6, 4];
console.log("Max profit:", maxProfit(prices));  // Output: 5

---

Explanation of Approach:

1. Initialization:
   • Set min_price to the first price, as this will be the initial “buy” price.
   • Set max_profit to 0 because initially, there’s no profit.
2. Iteration:
   • Loop through the array starting from the second element.
   • For each price:
     • Update min_price if the current price is lower than the previously encountered minimum price.
     • Calculate the potential profit if we sell at the current price (current price - min_price).
     • Update max_profit if the calculated profit is greater than the previously recorded max_profit.
3. Result:
   • At the end of the loop, max_profit holds the maximum profit that can be achieved by buying and selling once.

Time Complexity:

• O(n) where n is the number of elements in the array (prices). We iterate over the array only once.

Space Complexity:

• O(1) since we are using only a few extra variables (min_price and max_profit), regardless of the input size.

Edge Cases:

• If the prices array contains only one element, no transaction can be made, so the result will be 0.
• If the prices are strictly decreasing (no opportunities to make a profit), the result will also be 0.

---

Summary:

This problem can be efficiently solved using a greedy approach, tracking the minimum price and calculating the potential profit at each step. The solution runs in linear time and constant space, making it highly optimal.