Here's the Leetcode 121 solution using TypeScript.
Leetcode 121 - Best Time to Buy and Sell Stock:
You are given an array prices where prices[i]
is the price of a given stock on the i
th 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
.
Approach
The goal is to find the maximum profit that you can obtain by buying and selling a stock given it's prices over time.
You can use a simple one-pass algorithm with two pointers, l
and r
, and track the buying and selling days.
Initialize l
and r
to the first and second days, respectively.
Then iterate through the array using a while
loop.
In each iteration, check if the price on day l
is less than the price on day r
. If true, calculate the profit by subtracting the buying price (prices[l]
) from the selling price (prices[r]
) and update the maximum profit (max
) only if the calculated profit is greater than the current maximum.
On the other hand, if the buying price is not less than the selling price, it means a better buying opportunity is found, so move the l
pointer to the current selling day (r
). This way you can ensure that the algorithm always looks for the lowest buying price before searching for a selling opportunity.
The final result is the maximum profit obtained by buying and selling the stock.
Code Implementation
function maxProfit(prices: number[]): number {
let l = 0
let r = 1
let max = 0
while (r < prices.length) {
if (prices[l] < prices[r]) {
const profit = prices[r] - prices[l]
max = Math.max(profit, max)
} else l = r
r++
}
return max
}
Time Complexity
The time complexity is O(n)
, where n
is the length of the input array prices
. The algorithm iterates through the array once, and each iteration involves constant-time operations.
Space Complexity
The space complexity is O(1)
or constant. The algorithm uses only a constant amount of extra space for variables like l
, r
, max
, and profit
.
It doesn't require additional memory that grows with the size of the input array.
Top comments (0)