Stock Buy and Sell (Single Transaction)

Problem Statement

You are given an array prices[] where prices[i] represents the price of a stock on day i.

You are allowed to complete only one transaction:

• Buy on one day
• Sell on a later day

Find the maximum profit you can achieve.
If no profit is possible, return 0.

Example 1

Input

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

Output

5

Explanation

Buy on day 1 at price 1
Sell on day 4 at price 6
Profit = 6 - 1 = 5

Example 2

Input

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

Output

0

Explanation

Prices are decreasing, so no profit is possible.

Why This Problem Is Important

• Very common interview question
• Tests understanding of:
  • Minimum tracking
  • Greedy strategy
  • One-pass optimization
• Foundation for advanced stock problems

Approaches Overview

Approach 1: Brute Force Method

Idea

Try every possible buy day and every possible sell day after it, calculate profit, and track the maximum profit.

Algorithm

1. Initialize maxProfit = 0
2. For each day i:
   • For each day j > i:
     • Profit = prices[j] - prices[i]
     • Update maxProfit
3. Return maxProfit

Time and Space Complexity

• Time Complexity: O(n²)
• Space Complexity: O(1)

C Implementation 

#include<stdio.h> 

int main() {
    int prices[] = {7, 1, 5, 3, 6, 4};
    int n = 6;
    int maxProfit = 0;

    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            int profit = prices[j] - prices[i];
            if(profit > maxProfit)
                maxProfit = profit;
        }
    }

    printf("Maximum Profit: %d", maxProfit);
    return 0;
}

JavaScript Implementation 

let prices = [7, 1, 5, 3, 6, 4];
let maxProfit = 0;

for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
        let profit = prices[j] - prices[i];
        if (profit > maxProfit)
            maxProfit = profit;
    }
}

console.log("Maximum Profit:", maxProfit);

Approach 2: Optimized Greedy Approach (One Pass)

Core Idea

• Track the minimum price so far
• At each day, calculate potential profit if sold today
• Update maximum profit accordingly

This ensures:

• Buy happens before sell
• Only one transaction

Algorithm

1. Initialize:
   • minPrice = prices[0]
   • maxProfit = 0
2. Traverse from day 1 to end:
   • Update minPrice = min(minPrice, prices[i])
   • Calculate profit = prices[i] - minPrice
   • Update maxProfit
3. Return maxProfit

Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)

C Implementation 

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

int main() {
    int prices[] = {7, 1, 5, 3, 6, 4};
    int n = 6;

    int minPrice = INT_MAX;
    int maxProfit = 0;

    for(int i = 0; i < n; i++) {
        if(prices[i] < minPrice)
            minPrice = prices[i];

        int profit = prices[i] - minPrice;
        if(profit > maxProfit)
            maxProfit = profit;
    }

    printf("Maximum Profit: %d", maxProfit);
    return 0;
}

C++ Implementation 

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

int main() {
    int prices[] = {7, 1, 5, 3, 6, 4};
    int n = 6;

    int minPrice = INT_MAX;
    int maxProfit = 0;

    for(int i = 0; i < n; i++) {
        minPrice = min(minPrice, prices[i]);
        maxProfit = max(maxProfit, prices[i] - minPrice);
    }

    cout << "Maximum Profit: " << maxProfit;
    return 0;
}

Java Implementation 

public class StockBuySell {
    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};

        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for(int price : prices) {
            if(price < minPrice)
                minPrice = price;

            maxProfit = Math.max(maxProfit, price - minPrice);
        }

        System.out.println("Maximum Profit: " + maxProfit);
    }
}

Python Implementation 

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

min_price = float('inf')
max_profit = 0

for price in prices:
    min_price = min(min_price, price)
    max_profit = max(max_profit, price - min_price)

print("Maximum Profit:", max_profit)

JavaScript Implementation 

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

let minPrice = Number.MAX_VALUE;
let maxProfit = 0;

for (let price of prices) {
    minPrice = Math.min(minPrice, price);
    maxProfit = Math.max(maxProfit, price - minPrice);
}

console.log("Maximum Profit:", maxProfit);

Dry Run (Optimized Approach)

Prices: [7, 1, 5, 3, 6, 4]

Day | Price | MinPrice | Profit | MaxProfit
0   | 7     | 7        | 0      | 0
1   | 1     | 1        | 0      | 0
2   | 5     | 1        | 4      | 4
3   | 3     | 1        | 2      | 4
4   | 6     | 1        | 5      | 5
5   | 4     | 1        | 3      | 5

Key Interview Notes

• Selling must occur after buying
• Greedy approach ensures best result in one pass
• No extra memory needed
• Returns 0 if profit is negative

Summary

• Brute force checks all possibilities but is slow
• Optimized approach tracks minimum price
• Best solution runs in O(n) time
• Very frequently asked interview problem

Next Problems You Can Cover

Stock Buy and Sell (Multiple Transactions)