Scale Engineer

Best Time to Buy and Sell Stock

Easy
#0121Time: O(n^2)Space: O(1)112 companies
Patterns
Dynamic Programming
Data structures
Array
Companies
AccentureAccoliteAgodaAkamai

Prompt

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

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

 

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

 

Constraints:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves checking every possible pair of buy and sell days to find the one that yields the maximum profit. We use nested loops to iterate through all valid transaction pairs.

Algorithm

  • Initialize a variable maxProfit to 0.
  • Iterate through the prices array with an index i from 0 to n-2 (representing the buy day).
  • Inside this loop, start another loop with an index j from i+1 to n-1 (representing the sell day).
  • Calculate the current profit: profit = prices[j] - prices[i].
  • Compare profit with maxProfit. If profit is greater, update maxProfit = profit.
  • After the loops complete, return maxProfit.

Walkthrough

The brute force method systematically calculates the profit for every possible transaction. We assume we buy on day i and sell on a future day j (where j > i).

We use two nested loops. The outer loop iterates through each day i from the first to the second-to-last day, considering it as the potential buy day. The inner loop iterates through each subsequent day j from i+1 to the last day, considering it as the potential sell day.

For each pair of (buy_price, sell_price), we calculate the profit. We maintain a variable maxProfit which is updated whenever we find a profit greater than the current maxProfit.

If no profitable transaction can be made (i.e., prices are always decreasing), the maxProfit will remain at its initial value of 0.

class Solution {    public int maxProfit(int[] prices) {        int maxProfit = 0;        for (int i = 0; i < prices.length - 1; i++) {            for (int j = i + 1; j < prices.length; j++) {                int profit = prices[j] - prices[i];                if (profit > maxProfit) {                    maxProfit = profit;                }            }        }        return maxProfit;    }}

Complexity

Time

O(n^2)

Space

O(1)

Trade-offs

Pros

  • Simple to understand and implement.

  • Correctly solves the problem for small inputs.

Cons

  • Highly inefficient for large arrays.

  • Will result in a 'Time Limit Exceeded' error on most online judges due to the O(n^2) complexity.

Solutions

public class Solution {    public int MaxProfit(int[] prices) {        int ans = 0, mi = prices[0];        foreach(int v in prices) {            ans = Math.Max(ans, v - mi);            mi = Math.Min(mi, v);        }        return ans;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem