June 1st 2023

Best Time to Buy and Sell Stock — Typescript

Problem 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.

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.

Solution (1)

// Util functions
function expect(description: string, test: boolean) {
    if (test) {
        console.log(`✅ ${description}`)
    } else {
        console.log(`❌ ${description}`)
    }
}

// day is a human day (so the first day is day 1)
function maxProfitFromBuyingAtMoment(prices: number[], day: number): number {
    const pricesAfterPurchase = prices.slice(day)
    const highestValueAfterPurchase = Math.max(...pricesAfterPurchase)
    return Math.max(highestValueAfterPurchase - prices[day - 1], 0)
}

function maxProfit(prices: number[]): number {
    const profitsByDay = prices
        .map((_: number, index: number) => {
            return maxProfitFromBuyingAtMoment(prices, index + 1)
        })

    return Math.max(...profitsByDay, 0)

};

// Test the max profit for each day
expect(
    "The profit from buying on Day 1 in [7, 1, 5, 3, 6, 4] is 0",
    maxProfitFromBuyingAtMoment([7, 1, 5, 3, 6, 4], 1) == 0)
expect(
    "The profit from buying on Day 2 in [7, 1, 5, 3, 6, 4] is 5",
    maxProfitFromBuyingAtMoment([7, 1, 5, 3, 6, 4], 2) == 5)

// Test finding the max profit in the set
expect(
    "The max profit in maxProfit([7, 1, 5, 3, 6, 4] is 5",
    maxProfit([7, 1, 5, 3, 6, 4]) === 5)
expect(
    "The max profit in maxProfit([7,6,4,3,1] is 0",
    maxProfit([7, 6, 4, 3, 1]) === 0)

Discussion (1)

This is a brute force solution that compares every moment when a stock could have been bought or sold. I wasn't happy with this, though, I knew I wanted to find local maxima and minima for a quicker solution.

In this was a project that I was actually shipping I might have shipped this version depending on my dataset because it's probably good enough for most things. If this ran as a batch job overnight and wasn't something humans waited on then this is good enough- it's clear and it works.

Solution (2)

// Util functions
function expect(description: string, test: boolean) {
    if (test) {
        console.log(`✅ ${description}`)
    } else {
        console.log(`❌ ${description}`)
    }
}

function arrayEqual(a: number[], b: number[]): boolean {
    if (a.length !== b.length) {
        return false
    }

    for (var i = 0; i < a.length; i++) {
        if (a[i] !== b[i]) {
            return false
        }
    }

    return true
}


/*
// Need to find local minima and local maxima

[0, 1, 2, 4, 8, 1]


// Store 0
[0, 1] // going up
[1, 2] // going up
[2, 4] // going up
[4, 8] // going up
[8, 1] // going down (store 8 and 1)
*/

enum PriceDirection {
    Up = 1,
    Down = 2
}

// moment is a computer moment (first element is 0)
function maxProfitFromBuyingAtMoment(prices: number[], moment: number): number {
    const pricesAfterPurchase = prices.slice(moment)
    const highestValueAfterPurchase = Math.max(...pricesAfterPurchase)
    return Math.max(highestValueAfterPurchase - prices[moment], 0)
}

function simplifyPriceLine(prices: number[]): number[] {
    var keyPriceMoments: number[] = [prices[0]]
    var movementDirection: PriceDirection | null = null

    for (var i = 1; i < prices.length; i++) {
        const previous = prices[i - 1];
        const now = prices[i];
        const todaysMovement = now > previous ? PriceDirection.Up : PriceDirection.Down

        // console.log([previous, now], todaysMovement == 1 ? "Up" : "Down")
        if (movementDirection !== null && todaysMovement != movementDirection) {
            keyPriceMoments.push(previous)
        }

        movementDirection = todaysMovement;
    }

    // Always append the last one, this is slightly extra work
    keyPriceMoments.push(prices[prices.length - 1])

    return keyPriceMoments
}

function maxProfit(prices: number[]): number {
    const simplifiedPriceLine = simplifyPriceLine(prices)
    const profitsForKeyMoments = simplifiedPriceLine
        .map((_: number, index: number) => {
            return maxProfitFromBuyingAtMoment(simplifiedPriceLine, index)
        })

    return Math.max(...profitsForKeyMoments, 0)
};

// Test simplifying the price line
expect("Simplifying [1, 2, 4, 2, 5, 7, 2, 4, 9, 0, 9]",
    arrayEqual(
        simplifyPriceLine([1, 2, 4, 2, 5, 7, 2, 4, 9, 0, 9]),
        [1, 4, 2, 7, 2, 9, 0, 9]))

// Test the max profit for each moment
expect(
    "The profit from buying on Day 1 in [7, 1, 5, 3, 6, 4] is 0",
    maxProfitFromBuyingAtMoment([7, 1, 5, 3, 6, 4], 0) == 0)
expect(
    "The profit from buying on Day 2 in [7, 1, 5, 3, 6, 4] is 5",
    maxProfitFromBuyingAtMoment([7, 1, 5, 3, 6, 4], 1) == 5)

// // Test finding the max profit in the set
expect(
    "The max profit in maxProfit([7, 1, 5, 3, 6, 4] is 5",
    maxProfit([7, 1, 5, 3, 6, 4]) === 5)
expect(
    "The max profit in maxProfit([7,6,4,3,1] is 0",
    maxProfit([7, 6, 4, 3, 1]) === 0)
expect(
    "The profit in maxProfit([1,2,4,2,5,7,2,4,9,0,9]) is 9",
    maxProfit([1, 2, 4, 2, 5, 7, 2, 4, 9, 0, 9]) == 9
)

Discussion (2)

I like that this verion has more tests. I like that the function for simplifying the price line is broken out. This version isn't guaranteed to be faster, if the data is up and down every-other moment then the performance of this is exactly the same as the other version.