Stock Buy and Sell

Given an array prices, where prices[i] represents the stock price on the ith day, your task is to find the maximum profit you can achieve by choosing a single day to buy one stock and a different day in the future to sell that stock.

• You must buy the stock before you sell it.
• If there is no way to make a profit, return 0.

Understanding the Problem

We are given an array of stock prices, where each element represents the price of a stock on a particular day. Our goal is to find the best day to buy and the best day to sell the stock to maximize profit. However, we are allowed to make this transaction only once, and we must buy the stock before we sell it.

In simple terms, we want to choose two days: one for buying and one for selling. The profit is the difference between the selling price and the buying price. If no profit is possible (i.e., prices only go down), we return 0.

Step-by-Step Solution with Explanation

1. Track the Minimum Price

As we go through the list, we will keep track of the lowest price we’ve seen so far. This will represent the best day to buy so far.

2. Calculate Profit

At each step, we calculate the profit if we were to sell the stock on that day, using the lowest price we've seen before. If this profit is greater than the best profit we’ve recorded, we update our best profit.

3. Use Example for Better Understanding

Let’s understand this with a beginner-friendly example: [7, 1, 5, 3, 6, 4]

• Day 1: Price = 7 → minPrice = 7
• Day 2: Price = 1 → minPrice = 1 (found a cheaper buy)
• Day 3: Price = 5 → profit = 5 - 1 = 4 → maxProfit = 4
• Day 4: Price = 3 → profit = 3 - 1 = 2 → maxProfit remains 4
• Day 5: Price = 6 → profit = 6 - 1 = 5 → maxProfit = 5
• Day 6: Price = 4 → profit = 4 - 1 = 3 → maxProfit remains 5

Result: Best profit is 5 (Buy at 1, sell at 6)

Handling Edge Cases

Case 1: Prices Only Go Down

Example: [7, 6, 4, 3, 1]
The price keeps dropping. Any buy-sell pair results in a loss. So, the maximum profit is 0.

Case 2: Constant or Steady Increase

Example: [1, 2, 3, 4, 5]
Here, buying at day 1 and selling at day 5 gives the best result: profit = 5 - 1 = 4.

Case 3: Single Price

Example: [10]
We can’t sell if we buy on the only day available. So, the profit is 0.

Case 4: Empty Array

There are no prices at all, so no transaction can be made. The answer is 0.

1. Given an array prices where prices[i] represents the price of a stock on the ith day.
2. Initialize min_price to a very large number and max_profit to 0.
3. Traverse through the array:
4. → If prices[i] is less than min_price, update min_price.
5. → Else, calculate the profit by prices[i] - min_price and update max_profit if it is greater.
6. After the loop, return max_profit.

#include <stdio.h>
#include <limits.h>

int maxProfit(int prices[], int size) {
    int minPrice = INT_MAX;
    int maxProfit = 0;
    for (int i = 0; i < size; i++) {
        if (prices[i] < minPrice)
            minPrice = prices[i];
        else if (prices[i] - minPrice > maxProfit)
            maxProfit = prices[i] - minPrice;
    }
    return maxProfit;
}

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

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

int maxProfit(vector<int>& prices) {
    int minPrice = INT_MAX;
    int maxProfit = 0;
    for (int price : prices) {
        if (price < minPrice)
            minPrice = price;
        else if (price - minPrice > maxProfit)
            maxProfit = price - minPrice;
    }
    return maxProfit;
}

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

def max_profit(prices):
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > max_profit:
            max_profit = price - min_price
    return max_profit

# Sample Input
prices = [7, 1, 5, 3, 6, 4]
print("Max Profit:", max_profit(prices))

public class StockProfit {
    public static int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;
            } else if (price - minPrice > maxProfit) {
                maxProfit = price - minPrice;
            }
        }
        return maxProfit;
    }

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

function maxProfit(prices) {
    let minPrice = Infinity;
    let maxProfit = 0;
    for (let price of prices) {
        if (price < minPrice) {
            minPrice = price;
        } else if (price - minPrice > maxProfit) {
            maxProfit = price - minPrice;
        }
    }
    return maxProfit;
}

// Sample Input
const prices = [7, 1, 5, 3, 6, 4];
console.log('Max Profit:', maxProfit(prices));

package main

import (
    "fmt"
    "math"
)

func maxProfit(prices []int) int {
    minPrice := math.MaxInt
    maxProfit := 0
    for _, price := range prices {
        if price < minPrice {
            minPrice = price
        } else if price - minPrice > maxProfit {
            maxProfit = price - minPrice
        }
    }
    return maxProfit
}

func main() {
    prices := []int{7, 1, 5, 3, 6, 4}
    fmt.Println("Max Profit:", maxProfit(prices))
}

fn max_profit(prices: Vec<i32>) -> i32 {
    let mut min_price = i32::MAX;
    let mut max_profit = 0;
    for price in prices {
        if price < min_price {
            min_price = price;
        } else if price - min_price > max_profit {
            max_profit = price - min_price;
        }
    }
    max_profit
}

fn main() {
    let prices = vec![7, 1, 5, 3, 6, 4];
    println!("Max Profit: {}", max_profit(prices));
}

fun maxProfit(prices: IntArray): Int {
    var minPrice = Int.MAX_VALUE
    var maxProfit = 0
    for (price in prices) {
        if (price < minPrice) {
            minPrice = price
        } else if (price - minPrice > maxProfit) {
            maxProfit = price - minPrice
        }
    }
    return maxProfit
}

fun main() {
    val prices = intArrayOf(7, 1, 5, 3, 6, 4)
    println("Max Profit: ${maxProfit(prices)}")
}

func maxProfit(_ prices: [Int]) -> Int {
    var minPrice = Int.max
    var maxProfit = 0
    for price in prices {
        if price < minPrice {
            minPrice = price
        } else if price - minPrice > maxProfit {
            maxProfit = price - minPrice
        }
    }
    return maxProfit
}

let prices = [7, 1, 5, 3, 6, 4]
print("Max Profit: \(maxProfit(prices))")

function maxProfit(prices: number[]): number {
    let minPrice = Infinity;
    let maxProfit = 0;
    for (const price of prices) {
        if (price < minPrice) {
            minPrice = price;
        } else if (price - minPrice > maxProfit) {
            maxProfit = price - minPrice;
        }
    }
    return maxProfit;
}

const prices: number[] = [7, 1, 5, 3, 6, 4];
console.log('Max Profit:', maxProfit(prices));

Time complexity

Space complexity

O(1)

The solution uses a constant amount of extra space, maintaining only variables like min_price and max_profit.