leetcode

Best Time to Buy and Sell Stock solution using TypeScript

This post outlines my TypeScript solution to the LeetCode "Best Time to Buy and Sell Stock" question.

Algorithm: The solution iterates over the array to find the lowest value, which represents the cheapest day to buy on. It then compares the lowest value with the values that follow, finding the largest difference, which represents the the most profitable day to sell on.

Time Complexity: Because the array will be iterated at most, one time, the time complexity is O(n) where n represents the number of items in the inputted array.

Space Complexity: Because the solution will use a constant amount of space, the space complexity is O(1).

/**
 * Best Time to Buy and Sell Stock
 * Say you have an array for which the ith element 
 * is the price of a given stock on day i. If you were only 
 * permitted to complete at most one transaction 
 * (i.e., buy one and sell one share of the stock), 
 * design an algorithm to find the maximum profit.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 *
 * maxProfit([7,1,5,3,6,4]) // 5
 * maxProfit([7,6,4,3,1]) // 0
 */
function maxProfit(prices: number[]): number {
    let minPrice = Number.MAX_SAFE_INTEGER;
    let maxProfit = 0;
    let ptr = 0;
    
    while (ptr < prices.length) {
        // see if this is the cheapest price to buy at
        if (prices[ptr] < minPrice) {
            minPrice = prices[ptr];
        }
        // check if this is the most profitable day to sell
        else if (prices[ptr] - minPrice > maxProfit) {
            maxProfit = prices[ptr] - minPrice;
        }
        ptr += 1;
    }
    
    return maxProfit;
}

more LeetCode posts