LeetCode 121
Best Time to Buy and Sell Stock
Concepts:
Array
Description: 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.
Brute-force Approach
Iterate through the array and for each element, iterate through the rest of the array to find the maximum profit.
Time: O(n^2)
Space: O(1)
Optimal Approach
Iterate through the array, keeping track of min until now and updating maxProfit for each element.
Time: O(n)
Space: O(1)