Best Time to Buy and Sell Stock using Strategy - Video Solutions
Best Time to Buy and Sell Stock using Strategy | Simply Detailed | Dry Run | Leetcode 3652 | MIK
Best Time to Buy and Sell Stock using Strategy - Video Solution
Watch 10 video solutions for Best Time to Buy and Sell Stock using Strategy, a medium level problem involving Array, Sliding Window, Prefix Sum. This walkthrough by codestorywithMIK has 7,852 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given two integer arrays prices and strategy, where:
prices[i]is the price of a given stock on theithday.strategy[i]represents a trading action on theithday, where:-1indicates buying one unit of the stock.0indicates holding the stock.1indicates selling one unit of the stock.
You are also given an even integer k, and may perform at most one modification to strategy. A modification consists of:
- Selecting exactly
kconsecutive elements instrategy. - Set the first
k / 2elements to0(hold). - Set the last
k / 2elements to1(sell).
The profit is defined as the sum of strategy[i] * prices[i] across all days.
Return the maximum possible profit you can achieve.
Note: There are no constraints on budget or stock ownership, so all buy and sell operations are feasible regardless of past actions.
Example 1:
Input: prices = [4,2,8], strategy = [-1,0,1], k = 2
Output: 10
Explanation:
| Modification | Strategy | Profit Calculation | Profit |
|---|---|---|---|
| Original | [-1, 0, 1] | (-1 × 4) + (0 × 2) + (1 × 8) = -4 + 0 + 8 | 4 |
| Modify [0, 1] | [0, 1, 1] | (0 × 4) + (1 × 2) + (1 × 8) = 0 + 2 + 8 | 10 |
| Modify [1, 2] | [-1, 0, 1] | (-1 × 4) + (0 × 2) + (1 × 8) = -4 + 0 + 8 | 4 |
Thus, the maximum possible profit is 10, which is achieved by modifying the subarray [0, 1]āāāāāāā.
Example 2:
Input: prices = [5,4,3], strategy = [1,1,0], k = 2
Output: 9
Explanation:
| Modification | Strategy | Profit Calculation | Profit |
|---|---|---|---|
| Original | [1, 1, 0] | (1 × 5) + (1 × 4) + (0 × 3) = 5 + 4 + 0 | 9 |
| Modify [0, 1] | [0, 1, 0] | (0 × 5) + (1 × 4) + (0 × 3) = 0 + 4 + 0 | 4 |
| Modify [1, 2] | [1, 0, 1] | (1 × 5) + (0 × 4) + (1 × 3) = 5 + 0 + 3 | 8 |
Thus, the maximum possible profit is 9, which is achieved without any modification.
Constraints:
2 <= prices.length == strategy.length <= 1051 <= prices[i] <= 105-1 <= strategy[i] <= 12 <= k <= prices.lengthkis even
Approach Overview
Problem Overview: You are given stock prices and a strategy-derived gain sequence. The task is to determine the best buy and sell window that maximizes total profit. Conceptually, this reduces to finding the maximum profit segment over an array of gains.
Approach 1: Prefix Sum + Enumeration (O(n) time, O(n) space)
Convert the strategy impact into a profit array where each element represents the gain or loss contributed on that day. Build a prefix sum array so the profit of any interval [l, r] can be computed in constant time using prefix[r] - prefix[l-1]. While iterating through the array, track the smallest prefix value seen so far and compute the maximum difference with the current prefix. This effectively finds the maximum subarray profit without enumerating all pairs explicitly. Time complexity is O(n) and space complexity is O(n) for the prefix array.
The key insight: maximizing profit between two days is equivalent to maximizing the difference between two prefix sums where the smaller prefix appears earlier. This pattern appears frequently in Prefix Sum problems and can also be viewed as a sliding profit window over the array.
Instead of recomputing sums for every candidate buy and sell pair, prefix sums allow constant-time range evaluation. Maintaining the minimum prefix seen so far eliminates the need for nested loops. The algorithm performs a single pass through the data, updating the best achievable profit at each step.
This technique is closely related to maximum subarray problems and commonly appears with Array manipulation and window-based optimization. When implemented carefully, the logic resembles a rolling comparison similar to patterns used in Sliding Window problems.
Recommended for interviews: The prefix sum + enumeration optimization is the expected solution. A brute-force approach that checks all buy/sell pairs demonstrates understanding but runs in O(n^2). Interviewers typically look for the optimized linear scan using prefix differences because it shows recognition of the maximum-subarray-style transformation.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Buy/Sell Enumeration | O(n^2) | O(1) | Useful for understanding the problem or verifying small inputs |
| Prefix Sum + Enumeration | O(n) | O(n) | Best general solution for large arrays and interview settings |
| Running Minimum Prefix (Optimized Scan) | O(n) | O(1) | When memory is constrained and prefix array storage is unnecessary |