Problem Statement

Given an array arr of n integers, where arr[i] represents price of the stock on the ith day. Determine the maximum profit achievable by buying and selling the stock at most once.

The stock should be purchased before selling it, and both actions cannot occur on the same day.

Examples

Example 1:

Input: arr = [10, 7, 5, 8, 11, 9]
Output: 6

Explanation: Buy on day 3 (price = 5) and sell on day 5 (price = 11), profit = 11 - 5 = 6

Example 2:

Input: arr = [5, 4, 3, 2, 1]
Output: 0

Explanation: In this case, no transactions are made. Therefore, the maximum profit remains 0.

Different Approaches

1️⃣ Brute Force Approach

A naive solution involves considering all possible pairs of buy and sell days and calculating the profit for each pair. The maximum profit is then chosen. Although straightforward, this approach has a time complexity of O(n^2), making it inefficient for large datasets.

Code Implementation

class Solution {
public:
    /*
    Function to calculate the maximum profit that can be made by buying and selling stocks.
    @param prices - A vector containing the prices of the stock on different days.
    @param n - The total number of days (size of the prices array).
    @return Maximum profit that can be achieved.
    */
    int stockBuySell(vector<int> prices, int n) {
        int maximumProfit = 0; // Variable to store the maximum profit

        // Iterate over all possible buy days
        for (int buyDay = 0; buyDay < prices.size(); buyDay++) {
            int buyPrice = prices[buyDay]; // Price on the buy day

            // Iterate over all possible sell days after the buy day
            for (int sellDay = buyDay + 1; sellDay < prices.size(); sellDay++) {
                int sellPrice = prices[sellDay]; // Price on the sell day

                // Calculate profit for the current buy and sell day
                int currentProfit = sellPrice - buyPrice;

                // Update the maximum profit if the current profit is greater
                maximumProfit = max(maximumProfit, currentProfit);
            }
        }

        return maximumProfit; // Return the maximum profit
    }
};

Complexity Analysis:

• Time Complexity: O(n^2), where n is the size of the prices array.
  • The outer loop runs for O(n) iterations.
  • The inner loop runs for O(n) iterations.
  • Therefore, the overall time complexity is O(n^2).
• Space Complexity: O(1)
  • The algorithm uses only a constant amount of extra space for variables.

2️⃣ Optimized Approach (One Pass)

Intuition:

• Keep track of the minimum price so far and calculate the profit for each day as if that day is the selling day.
• Update the maximum profit whenever a higher profit is found.

Approach:

• Traverse the prices array while maintaining the lowest price encountered so far and the maximum profit.

Code Implementation:

int maxProfit(vector<int>& prices) {
    int minPrice = INT_MAX;
    int maxProfit = 0;

    for (int price : prices) {
        minPrice = min(minPrice, price);        // Update minimum price so far
        maxProfit = max(maxProfit, price - minPrice); // Calculate current profit
    }

    return maxProfit;
}

Complexity Analysis

• Time Complexity: O(n) - where n is the size of the prices array.
• Space Complexity: O(1) - as only a constant amount of extra space is required.