3573. Best Time to Buy and Sell Stock V Solution

Q: Is Best Time to Buy and Sell Stock V easy or hard?

The problem is typically rated medium because the core challenge is modeling the dynamic programming states correctly. Once the buy/sell transitions and transaction limits are defined, implementation becomes straightforward.

Q: Best Time to Buy and Sell Stock V Python/Java solution

Implement the DP transition using arrays that store buy and sell profits for each transaction count. Iterate through the prices and update states using max operations. The same logic works across Python, Java, C++, Go, TypeScript, Rust, and C# with O(n * k) time complexity.

Q: How to solve Best Time to Buy and Sell Stock V in O(n)?

If the number of transactions is small or fixed, you can update buy and sell states in a single pass over the prices. Maintain arrays for buy[t] and sell[t] and update them for each price. This keeps the scan linear over the array while handling transaction constraints efficiently.

Q: What is the best approach for Best Time to Buy and Sell Stock V?

The most efficient approach uses dynamic programming with transaction states. Track whether you are holding a stock and how many transactions have been completed. This reduces the problem to O(n * k) time by updating buy and sell states for each transaction while scanning the price array once.

Q: Is Best Time to Buy and Sell Stock V asked at Google/Amazon/Meta?

Stock trading dynamic programming problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants such as limited transactions, cooldown periods, or transaction fees test your ability to model state transitions and optimize DP solutions.

Q: What data structure is used in Best Time to Buy and Sell Stock V?

The core structure is a dynamic programming table or compressed DP arrays. These structures track the maximum profit for each day, transaction count, and holding state while iterating through the price array.

Q: What is the time complexity of Best Time to Buy and Sell Stock V?

The optimal dynamic programming solution runs in O(n * k) time, where n is the number of days and k is the maximum number of allowed transactions. Each price is processed once while updating buy and sell states for every transaction count.

The problem

You are given an integer array prices where prices[i] is the price of a stock in dollars on the i^th day, and an integer k.

You are allowed to make at most k transactions, where each transaction can be either of the following:

Normal transaction: Buy on day i, then sell on a later day j where i < j. You profit prices[j] - prices[i].
Short selling transaction: Sell on day i, then buy back on a later day j where i < j. You profit prices[i] - prices[j].

Note that you must complete each transaction before starting another. Additionally, you can't buy or sell on the same day you are selling or buying back as part of a previous transaction.

Return the maximum total profit you can earn by making at most k transactions.

Example 1:

Input: prices = [1,7,9,8,2], k = 2

Output: 14

Explanation:

We can make $14 of profit through 2 transactions:

A normal transaction: buy the stock on day 0 for $1 then sell it on day 2 for $9.
A short selling transaction: sell the stock on day 3 for $8 then buy back on day 4 for $2.

Example 2:

Input: prices = [12,16,19,19,8,1,19,13,9], k = 3

Output: 36

Explanation:

We can make $36 of profit through 3 transactions:

A normal transaction: buy the stock on day 0 for $12 then sell it on day 2 for $19.
A short selling transaction: sell the stock on day 3 for $19 then buy back on day 4 for $8.
A normal transaction: buy the stock on day 5 for $1 then sell it on day 6 for $19.

Constraints:

2 <= prices.length <= 10³
1 <= prices[i] <= 10⁹
1 <= k <= prices.length / 2

Approach overview

Problem Overview: You are given an array where prices[i] is the stock price on day i. The goal is to maximize profit by buying and selling the stock multiple times with a limit on the number of transactions. Each transaction consists of one buy followed by one sell, and you cannot hold multiple stocks at the same time.

Approach 1: Brute Force Recursion (Exponential Time, O(2^n) time, O(n) space)

The naive approach explores every possible action on each day: buy, sell, or skip. Recursively simulate decisions while tracking whether you currently hold a stock and how many transactions remain. For every day, branch into multiple possibilities and compute the resulting profit. This approach demonstrates the full decision tree but quickly becomes impractical because the number of states grows exponentially. It mainly helps build intuition for the dynamic programming transition.

Approach 2: Dynamic Programming with Transaction States (O(n * k) time, O(n * k) space)

Dynamic programming removes repeated work by storing results for each state. Define dp[i][t][h] where i is the day, t is the number of completed transactions, and h indicates whether you are holding a stock. Transition by either skipping the day, buying, or selling. Buying moves from h = 0 to h = 1 while keeping the transaction count the same. Selling moves from h = 1 to h = 0 and increments the transaction count. Iterating through days and transactions fills the DP table and guarantees the optimal profit. This approach is the standard pattern used in many dynamic programming stock problems.

Approach 3: Space Optimized Dynamic Programming (O(n * k) time, O(k) space)

The full DP table is unnecessary because each state depends only on the previous day. Instead of storing results for every day, keep two arrays: one for buy states and one for sell states for each transaction count. Iterate through the price array and update the arrays in place using transitions such as buy[t] = max(buy[t], sell[t-1] - price) and sell[t] = max(sell[t], buy[t] + price). This reduces memory usage significantly while preserving the same time complexity. The technique appears frequently in array optimization problems and advanced DP interview questions.

Recommended for interviews: Start by explaining the recursive decision process (buy, sell, skip). Then move to the DP formulation with transaction states. Interviewers usually expect the O(n * k) dynamic programming solution and often appreciate the space‑optimized version since it demonstrates deeper understanding of DP state transitions.

Solution

We define f[i][j][k] to represent the maximum profit on the first i days, with at most j transactions, and the current state k. Here, the state k has three possibilities:

If k = 0, it means we do not hold any stock.
If k = 1, it means we are holding a stock.
If k = 2, it means we are holding a short position.

Initially, for any j \in [1, k], we have f[0][j][1] = -prices[0] and f[0][j][2] = prices[0]. This means buying a stock or opening a short position on day 0.

Next, we update f[i][j][k] using state transitions. For each day i and each transaction j, we update according to the current state k:

If k = 0, meaning no stock is held, this state can be reached from three situations:
- No stock was held the previous day.
- A stock was held the previous day and sold today.
- A short position was held the previous day and bought back today.
If k = 1, meaning a stock is held, this state can be reached from two situations:
- A stock was held the previous day.
- No stock was held the previous day and a stock is bought today.
If k = 2, meaning a short position is held, this state can be reached from two situations:
- A short position was held the previous day.
- No stock was held the previous day and a short position is opened (sold) today.

That is, for 1 leq i < n and 1 leq j leq k, we have the following state transition equations:

$\begin{aligned} f[i][j][0] &= max(f[i - 1][j][0], f[i - 1][j][1] + prices[i], f[i - 1][j][2] - prices[i]) \ f[i][j][1] &= max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i]) \ f[i][j][2] &= max(f[i - 1][j][2], f[i - 1][j - 1][0] + prices[i]) \end{aligned}

Finally, we return f[n - 1][k][0], which is the maximum profit after at most k transactions and not holding any stock at the end of n days.

The time complexity is O(n times k), and the space complexity is O(n times k), where n is the length of the array prices and k$ is the maximum number of transactions.

Python

class Solution:
    def maximumProfit(self, prices: List[int], k: int) -> int:
        n = len(prices)
        f = [[[0] * 3 for _ in range(k + 1)] for _ in range(n)]
        for j in range(1, k + 1):
            f[0][j][1] = -prices[0]
            f[0][j][2] = prices[0]
        for i in range(1, n):
            for j in range(1, k + 1):
                f[i][j][0] = max(
                    f[i - 1][j][0],
                    f[i - 1][j][1] + prices[i],
                    f[i - 1][j][2] - prices[i],
                )
                f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i])
                f[i][j][2] = max(f[i - 1][j][2], f[i - 1][j - 1][0] + prices[i])
        return f[n - 1][k][0]

Java

class Solution {
    public long maximumProfit(int[] prices, int k) {
        int n = prices.length;
        long[][][] f = new long[n][k + 1][3];
        for (int j = 1; j <= k; ++j) {
            f[0][j][1] = -prices[0];
            f[0][j][2] = prices[0];
        }
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j <= k; ++j) {
                f[i][j][0] = Math.max(f[i - 1][j][0],
                    Math.max(f[i - 1][j][1] + prices[i], f[i - 1][j][2] - prices[i]));
                f[i][j][1] = Math.max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i]);
                f[i][j][2] = Math.max(f[i - 1][j][2], f[i - 1][j - 1][0] + prices[i]);
            }
        }
        return f[n - 1][k][0];
    }
}

C++

class Solution {
public:
    long long maximumProfit(vector<int>& prices, int k) {
        int n = prices.size();
        long long f[n][k + 1][3];
        memset(f, 0, sizeof(f));
        for (int j = 1; j <= k; ++j) {
            f[0][j][1] = -prices[0];
            f[0][j][2] = prices[0];
        }

        for (int i = 1; i < n; ++i) {
            for (int j = 1; j <= k; ++j) {
                f[i][j][0] = max({f[i - 1][j][0], f[i - 1][j][1] + prices[i], f[i - 1][j][2] - prices[i]});
                f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i]);
                f[i][j][2] = max(f[i - 1][j][2], f[i - 1][j - 1][0] + prices[i]);
            }
        }

        return f[n - 1][k][0];
    }
};

TypeScript

function maximumProfit(prices: number[], k: number): number {
    const n = prices.length;
    const f: number[][][] = Array.from({ length: n }, () =>
        Array.from({ length: k + 1 }, () => Array(3).fill(0)),
    );

    for (let j = 1; j <= k; ++j) {
        f[0][j][1] = -prices[0];
        f[0][j][2] = prices[0];
    }

    for (let i = 1; i < n; ++i) {
        for (let j = 1; j <= k; ++j) {
            f[i][j][0] = Math.max(
                f[i - 1][j][0],
                f[i - 1][j][1] + prices[i],
                f[i - 1][j][2] - prices[i],
            );
            f[i][j][1] = Math.max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i]);
            f[i][j][2] = Math.max(f[i - 1][j][2], f[i - 1][j - 1][0] + prices[i]);
        }
    }

    return f[n - 1][k][0];
}

public class Solution {
    public long MaximumProfit(int[] prices, int k) {
        int n = prices.Length;
        long[,,] f = new long[n, k + 1, 3];

        for (int j = 1; j <= k; ++j) {
            f[0, j, 1] = -prices[0];
            f[0, j, 2] = prices[0];
        }

        for (int i = 1; i < n; ++i) {
            for (int j = 1; j <= k; ++j) {
                f[i, j, 0] = Math.Max(
                    f[i - 1, j, 0],
                    Math.Max(
                        f[i - 1, j, 1] + prices[i],
                        f[i - 1, j, 2] - prices[i]
                    )
                );
                f[i, j, 1] = Math.Max(
                    f[i - 1, j, 1],
                    f[i - 1, j - 1, 0] - prices[i]
                );
                f[i, j, 2] = Math.Max(
                    f[i - 1, j, 2],
                    f[i - 1, j - 1, 0] + prices[i]
                );
            }
        }

        return f[n - 1, k, 0];
    }
}

func maximumProfit(prices []int, k int) int64 {
	n := len(prices)
	f := make([][][3]int, n)
	for i := range f {
		f[i] = make([][3]int, k+1)
	}

	for j := 1; j <= k; j++ {
		f[0][j][1] = -prices[0]
		f[0][j][2] = prices[0]
	}

	for i := 1; i < n; i++ {
		for j := 1; j <= k; j++ {
			f[i][j][0] = max(f[i-1][j][0], f[i-1][j][1]+prices[i], f[i-1][j][2]-prices[i])
			f[i][j][1] = max(f[i-1][j][1], f[i-1][j-1][0]-prices[i])
			f[i][j][2] = max(f[i-1][j][2], f[i-1][j-1][0]+prices[i])
		}
	}

	return int64(f[n-1][k][0])
}

Rust

impl Solution {
    pub fn maximum_profit(prices: Vec<i32>, k: i32) -> i64 {
        let n = prices.len();
        let k = k as usize;
        let mut f = vec![vec![vec![0i64; 3]; k + 1]; n];
        for j in 1..=k {
            f[0][j][1] = -(prices[0] as i64);
            f[0][j][2] = prices[0] as i64;
        }
        for i in 1..n {
            for j in 1..=k {
                f[i][j][0] = f[i - 1][j][0]
                    .max(f[i - 1][j][1] + prices[i] as i64)
                    .max(f[i - 1][j][2] - prices[i] as i64);
                f[i][j][1] = f[i - 1][j][1].max(f[i - 1][j - 1][0] - prices[i] as i64);
                f[i][j][2] = f[i - 1][j][2].max(f[i - 1][j - 1][0] + prices[i] as i64);
            }
        }
        f[n - 1][k][0]
    }
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Recursion	O(2^n)	O(n)	Conceptual understanding of all possible buy/sell decisions
Dynamic Programming with 3D State	O(n * k)	O(n * k)	General solution when transaction count is limited
Space Optimized DP	O(n * k)	O(k)	Large inputs where memory usage matters

Frequently asked questions

Is Best Time to Buy and Sell Stock V easy or hard?

The problem is typically rated medium because the core challenge is modeling the dynamic programming states correctly. Once the buy/sell transitions and transaction limits are defined, implementation becomes straightforward.

Best Time to Buy and Sell Stock V Python/Java solution

Implement the DP transition using arrays that store buy and sell profits for each transaction count. Iterate through the prices and update states using max operations. The same logic works across Python, Java, C++, Go, TypeScript, Rust, and C# with O(n * k) time complexity.

How to solve Best Time to Buy and Sell Stock V in O(n)?

If the number of transactions is small or fixed, you can update buy and sell states in a single pass over the prices. Maintain arrays for buy[t] and sell[t] and update them for each price. This keeps the scan linear over the array while handling transaction constraints efficiently.

What is the best approach for Best Time to Buy and Sell Stock V?

The most efficient approach uses dynamic programming with transaction states. Track whether you are holding a stock and how many transactions have been completed. This reduces the problem to O(n * k) time by updating buy and sell states for each transaction while scanning the price array once.

Is Best Time to Buy and Sell Stock V asked at Google/Amazon/Meta?

Stock trading dynamic programming problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants such as limited transactions, cooldown periods, or transaction fees test your ability to model state transitions and optimize DP solutions.

What data structure is used in Best Time to Buy and Sell Stock V?

The core structure is a dynamic programming table or compressed DP arrays. These structures track the maximum profit for each day, transaction count, and holding state while iterating through the price array.

What is the time complexity of Best Time to Buy and Sell Stock V?

The optimal dynamic programming solution runs in O(n * k) time, where n is the number of days and k is the maximum number of allowed transactions. Each price is processed once while updating buy and sell states for every transaction count.

Best Time to Buy and Sell Stock V solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Best Time to Buy and Sell Stock V solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems