101 Logo
onenoughtone

Code Implementation

Stock Trader with Cooldown Implementation

Below is the implementation of the stock trader with cooldown:

solution.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
/**
 * Brute Force Recursive Approach
 * Time Complexity: O(2^n) - Exponential due to exploring all possible buy/sell combinations
 * Space Complexity: O(n) - Due to recursion stack
 *
 * This approach explores all possible decisions at each step using recursion.
 *
 * @param {number[]} prices - Array of stock prices
 * @return {number} - Maximum profit
 */
function maxProfitBruteForce(prices) {
  // Helper function to recursively find the maximum profit
  function dfs(i, holding) {
    // Base case: If we've gone through all prices, no more profit can be made
    if (i >= prices.length) {
      return 0;
    }
 
    if (holding) {
      // Option 1: Sell the stock and skip the next day (cooldown)
      const sellProfit = prices[i] + dfs(i + 2, false);
      // Option 2: Continue holding the stock
      const holdProfit = dfs(i + 1, true);
      // Return the maximum profit between selling and holding
      return Math.max(sellProfit, holdProfit);
    } else {
      // Option 1: Buy a stock
      const buyProfit = -prices[i] + dfs(i + 1, true);
      // Option 2: Do nothing
      const waitProfit = dfs(i + 1, false);
      // Return the maximum profit between buying and waiting
      return Math.max(buyProfit, waitProfit);
    }
  }
 
  // Start the recursion from day 0 with no stock
  return dfs(0, false);
}
 
/**
 * Memoized Recursive Approach
 * Time Complexity: O(n) - Each state is computed only once
 * Space Complexity: O(n) - For memoization and recursion stack
 *
 * This approach optimizes the brute force solution by caching results of subproblems.
 *
 * @param {number[]} prices - Array of stock prices
 * @return {number} - Maximum profit
 */
function maxProfitMemoized(prices) {
  // Create a memo object to store results of subproblems
  const memo = {};
 
  // Helper function to recursively find the maximum profit with memoization
  function dfs(i, holding) {
    // Base case: If we've gone through all prices, no more profit can be made
    if (i >= prices.length) {
      return 0;
    }
 
    // Create a unique key for the current state
    const key = `${i},${holding}`;
 
    // If we've already computed this state, return the cached result
    if (key in memo) {
      return memo[key];
    }
 
    let profit;
    if (holding) {
      // Option 1: Sell the stock and skip the next day (cooldown)
      const sellProfit = prices[i] + dfs(i + 2, false);
      // Option 2: Continue holding the stock
      const holdProfit = dfs(i + 1, true);
      profit = Math.max(sellProfit, holdProfit);
    } else {
      // Option 1: Buy a stock
      const buyProfit = -prices[i] + dfs(i + 1, true);
      // Option 2: Do nothing
      const waitProfit = dfs(i + 1, false);
      profit = Math.max(buyProfit, waitProfit);
    }
 
    // Cache the result before returning
    memo[key] = profit;
    return profit;
  }
 
  // Start the recursion from day 0 with no stock
  return dfs(0, false);
}
 
/**
 * State Machine Approach
 * Time Complexity: O(n) - We iterate through the prices array once
 * Space Complexity: O(1) - We use only a constant amount of extra space
 *
 * This approach models the problem as a state machine with three states:
 * 1. hold: We are holding a stock
 * 2. sold: We just sold a stock
 * 3. rest: We are not holding a stock and not in cooldown
 *
 * @param {number[]} prices - Array of stock prices
 * @return {number} - Maximum profit
 */
function maxProfit(prices) {
  // Edge case: If there are no prices or only one price, no profit can be made
  if (prices.length <= 1) {
    return 0;
  }
 
  // Initialize state variables
  let hold = -prices[0];  // Maximum profit with a stock (initially we buy the first stock)
  let sold = 0;           // Maximum profit after selling (initially we haven't sold anything)
  let rest = 0;           // Maximum profit at rest (initially we haven't done anything)
 
  // Iterate through the prices starting from the second day
  for (let i = 1; i < prices.length; i++) {
    // We need to save the current hold value before updating it
    // because we'll need the old value to calculate the new sold value
    const prevHold = hold;
 
    // Update hold: either continue holding or buy a new stock after resting
    hold = Math.max(hold, rest - prices[i]);
 
    // Update sold: sell the stock we were holding
    sold = prevHold + prices[i];
 
    // Update rest: either continue resting or come from sold state (after cooldown)
    rest = Math.max(rest, sold);
  }
 
  // The maximum profit will be the maximum of sold and rest states
  // (we don't want to end up holding a stock)
  return Math.max(sold, rest);
}
 
/**
 * Dynamic Programming Approach
 * Time Complexity: O(n) - We iterate through the prices array once
 * Space Complexity: O(n) - We use three arrays of size n
 *
 * This approach uses dynamic programming to track the maximum profit
 * for each state at each day.
 *
 * @param {number[]} prices - Array of stock prices
 * @return {number} - Maximum profit
 */
function maxProfitDP(prices) {
  // Edge case: If there are no prices or only one price, no profit can be made
  if (prices.length <= 1) {
    return 0;
  }
 
  const n = prices.length;
 
  // Create arrays to track the maximum profit for each state at each day
  const buy = new Array(n).fill(0);      // Maximum profit if we have a stock at the end of day i
  const sell = new Array(n).fill(0);     // Maximum profit if we sell a stock at day i
  const cooldown = new Array(n).fill(0); // Maximum profit if we are in cooldown at day i
 
  // Initialize the first day: we can only buy on the first day
  buy[0] = -prices[0];
 
  // Fill the DP arrays for each day
  for (let i = 1; i < n; i++) {
    // Buy: either continue from previous buy state or buy after cooldown
    buy[i] = Math.max(buy[i - 1], cooldown[i - 1] - prices[i]);
 
    // Sell: either continue from previous sell state or sell the stock we bought
    sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
 
    // Cooldown: either continue from previous cooldown state or enter cooldown after selling
    cooldown[i] = Math.max(cooldown[i - 1], sell[i - 1]);
  }
 
  // The maximum profit will be the maximum of sell and cooldown states at the last day
  return Math.max(sell[n - 1], cooldown[n - 1]);
}
 
/**
 * Optimized Dynamic Programming Approach
 * Time Complexity: O(n) - We iterate through the prices array once
 * Space Complexity: O(1) - We use only a constant amount of extra space
 *
 * This approach optimizes the space usage of the DP approach by using
 * variables instead of arrays.
 *
 * @param {number[]} prices - Array of stock prices
 * @return {number} - Maximum profit
 */
function maxProfitOptimized(prices) {
  // Edge case: If there are no prices or only one price, no profit can be made
  if (prices.length <= 1) {
    return 0;
  }
 
  // Initialize state variables for the first day
  let buy = -prices[0];
  let sell = 0;
  let cooldown = 0;
 
  // Iterate through the prices starting from the second day
  for (let i = 1; i < prices.length; i++) {
    // We need to save the current values before updating them
    // to avoid using updated values in the same iteration
    const prevBuy = buy;
    const prevSell = sell;
 
    // Update buy: either continue from previous buy state or buy after cooldown
    buy = Math.max(buy, cooldown - prices[i]);
 
    // Update sell: either continue from previous sell state or sell the stock we bought
    sell = Math.max(sell, prevBuy + prices[i]);
 
    // Update cooldown: either continue from previous cooldown state or enter cooldown after selling
    cooldown = Math.max(cooldown, prevSell);
  }
 
  // The maximum profit will be the maximum of sell and cooldown states
  return Math.max(sell, cooldown);
}
 
// Test cases
console.log("State Machine Approach:");
console.log(maxProfit([1, 2, 3, 0, 2]));  // 3
console.log(maxProfit([1]));  // 0
 
console.log("\nDP Approach:");
console.log(maxProfitDP([1, 2, 3, 0, 2]));  // 3
console.log(maxProfitDP([1]));  // 0
 
console.log("\nOptimized DP Approach:");
console.log(maxProfitOptimized([1, 2, 3, 0, 2]));  // 3
console.log(maxProfitOptimized([1]));  // 0
 
// Note: The brute force and memoized approaches are not tested with large inputs
// as they would be too slow or cause stack overflow for large inputs

Step-by-Step Explanation

Let's break down the implementation:

  1. 1. Understand the Problem: First, understand that we need to find the maximum profit from buying and selling stocks with a cooldown period of one day after selling. This means after selling a stock, we must wait one day before buying again.
  2. 2. Identify the Brute Force Approach: Start with a recursive approach that explores all possible decisions at each step: buy, sell, or do nothing. For each day, we need to consider our current state (whether we're holding a stock or not) and make the best decision.
  3. 3. Optimize with Memoization: Notice that the recursive approach has overlapping subproblems. We can use memoization to avoid recalculating the same states multiple times by storing the results in a cache.
  4. 4. Define State Variables: For the iterative approaches, define state variables to track the maximum profit in different states: holding a stock, just sold a stock, and resting (not holding and not in cooldown).
  5. 5. Implement State Transitions: For each day, update the state variables based on the possible actions: buy, sell, or do nothing. The key insight is to understand how these states transition into each other.
  6. 6. Handle Cooldown Period: Ensure that after selling a stock, we cannot buy on the next day (cooldown period). This is handled differently in each approach: in the recursive approach, we skip a day after selling; in the DP approach, we use separate arrays for different states.
  7. 7. Optimize Space Usage: Observe that we only need information from at most two days ahead. We can optimize the space usage by using variables instead of arrays, reducing the space complexity from O(n) to O(1).
  8. 8. Return Maximum Profit: Return the maximum profit, which will be the maximum of the sold and rest states (we don't want to end up holding a stock).
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone