Best Time to Buy and Sell Stock using Strategy solution and explanation
9 more videos on this problem
Best Time to Buy and Sell Stock using Strategy | Simply Detailed | Dry Run | Leetcode 3652 | MIKcodestorywithMIK · 37:42 · 7K views
Best Time to Buy and Sell Stock using Strategy | LeetCode 3652 | Beginner FriendlySanyam IIT Guwahati · 13:36 · 1K views
3652. Best Time to Buy and Sell Stock using Strategy | Leetcode Daily - PythonLeetcode Daily · 8:33 · 974 views
3652. Best Time to Buy and Sell Stock using Strategy (Leetcode Medium)Programming Live with Larry · 15:17 · 820 views
Best Time to Buy and Sell Stock using Strategy | LeetCode 3652 🔥 | Daily Coding Challenge Study Placement · 26:07 · 723 views
3652. Best Time to Buy and Sell Stock using Strategy | Leetcode Weekly Contest 463Break and Build · 28:08 · 472 views
Best Time to Buy and Sell Stock using Strategy | LeetCode 3652 - Pythonimpoldev · 13:50 · 346 views
LeetCode 3652 Explained | Best Time to Buy and Sell Stock Using Strategy | FAANG InterviewExpertFunda · 32:18 · 92 views
LeetCode POTD 3652 | Best Time to Buy and Sell Stock using Strategy | Daily ChallengeCodehurdle · 14:06 · 83 views
Leetcode | 3652 Best Time to Buy and Sell Stock using Strategy | Java | Prefix Sum| Daily ChallengeCakot Coding · 38:38 · 66 views
The problem
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.
Solution
We use an array s to represent the prefix sum, where s[i] is the total profit for the first i days, i.e., s[i] = sum_{j=0}^{i-1} prices[j] times strategy[j]. We also use an array t to represent the prefix sum of stock prices, where t[i] = sum_{j=0}^{i-1} prices[j].
Initially, the maximum profit is s[n]. We enumerate the right endpoint i of the subarray to be modified, with the left endpoint being i-k. After modification, the first k/2 days of the subarray have strategy 0, and the last k/2 days have strategy 1, so the profit change is:
$\Delta = -(s[i] - s[i-k]) + (t[i] - t[i-k/2])
Therefore, we can update the maximum profit by enumerating all possible i.
The time complexity is O(n), and the space complexity is O(n), where n$ is the length of the array.
class Solution:
def maxProfit(self, prices: List[int], strategy: List[int], k: int) -> int:
n = len(prices)
s = [0] * (n + 1)
t = [0] * (n + 1)
for i, (a, b) in enumerate(zip(prices, strategy), 1):
s[i] = s[i - 1] + a * b
t[i] = t[i - 1] + a
ans = s[n]
for i in range(k, n + 1):
ans = max(ans, s[n] - (s[i] - s[i - k]) + t[i] - t[i - k // 2])
return ansclass Solution {
public long maxProfit(int[] prices, int[] strategy, int k) {
int n = prices.length;
long[] s = new long[n + 1];
long[] t = new long[n + 1];
for (int i = 1; i <= n; i++) {
int a = prices[i - 1];
int b = strategy[i - 1];
s[i] = s[i - 1] + a * b;
t[i] = t[i - 1] + a;
}
long ans = s[n];
for (int i = k; i <= n; i++) {
ans = Math.max(ans, s[n] - (s[i] - s[i - k]) + (t[i] - t[i - k / 2]));
}
return ans;
}
}class Solution {
public:
long long maxProfit(vector<int>& prices, vector<int>& strategy, int k) {
int n = prices.size();
vector<long long> s(n + 1), t(n + 1);
for (int i = 1; i <= n; i++) {
int a = prices[i - 1];
int b = strategy[i - 1];
s[i] = s[i - 1] + a * b;
t[i] = t[i - 1] + a;
}
long long ans = s[n];
for (int i = k; i <= n; i++) {
ans = max(ans, s[n] - (s[i] - s[i - k]) + (t[i] - t[i - k / 2]));
}
return ans;
}
};function maxProfit(prices: number[], strategy: number[], k: number): number {
const n = prices.length;
const s: number[] = Array(n + 1).fill(0);
const t: number[] = Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
const a = prices[i - 1];
const b = strategy[i - 1];
s[i] = s[i - 1] + a * b;
t[i] = t[i - 1] + a;
}
let ans = s[n];
for (let i = k; i <= n; i++) {
const val = s[n] - (s[i] - s[i - k]) + (t[i] - t[i - Math.floor(k / 2)]);
ans = Math.max(ans, val);
}
return ans;
}public class Solution {
public long MaxProfit(int[] prices, int[] strategy, int k) {
int n = prices.Length;
long[] s = new long[n + 1];
long[] t = new long[n + 1];
for (int i = 1; i <= n; i++) {
long a = prices[i - 1];
long b = strategy[i - 1];
s[i] = s[i - 1] + a * b;
t[i] = t[i - 1] + a;
}
long ans = s[n];
for (int i = k; i <= n; i++) {
long cur = s[n] - (s[i] - s[i - k]) + (t[i] - t[i - k / 2]);
if (cur > ans) {
ans = cur;
}
}
return ans;
}
}func maxProfit(prices []int, strategy []int, k int) int64 {
n := len(prices)
s := make([]int64, n+1)
t := make([]int64, n+1)
for i := 1; i <= n; i++ {
a := prices[i-1]
b := strategy[i-1]
s[i] = s[i-1] + int64(a*b)
t[i] = t[i-1] + int64(a)
}
ans := s[n]
for i := k; i <= n; i++ {
ans = max(ans, s[n]-(s[i]-s[i-k])+(t[i]-t[i-k/2]))
}
return ans
}impl Solution {
pub fn max_profit(prices: Vec<i32>, strategy: Vec<i32>, k: i32) -> i64 {
let n: usize = prices.len();
let k: usize = k as usize;
let mut s: Vec<i64> = vec![0; n + 1];
let mut t: Vec<i64> = vec![0; n + 1];
for i in 1..=n {
let a: i64 = prices[i - 1] as i64;
let b: i64 = strategy[i - 1] as i64;
s[i] = s[i - 1] + a * b;
t[i] = t[i - 1] + a;
}
let mut ans: i64 = s[n];
for i in k..=n {
let cur = s[n] - (s[i] - s[i - k]) + (t[i] - t[i - k / 2]);
if cur > ans {
ans = cur;
}
}
ans
}
}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 |
Frequently asked questions
Is Best Time to Buy and Sell Stock using Strategy easy or hard?
The problem is typically classified as Medium because the brute-force idea is straightforward but the optimal solution requires recognizing a prefix-sum or maximum-subarray transformation. Identifying this pattern is the key step.
Best Time to Buy and Sell Stock using Strategy Python/Java solution
Most implementations compute a prefix sum or running cumulative gain while tracking the smallest prefix seen so far. This pattern works the same in Python, Java, C++, Go, TypeScript, Rust, and C#, producing an O(n) solution with minimal extra memory.
How to solve Best Time to Buy and Sell Stock using Strategy in O(n)?
First compute cumulative profit using prefix sums. While iterating through the array, track the minimum prefix value encountered so far. The difference between the current prefix and this minimum represents the best profit ending at that index, allowing the algorithm to update the global maximum in linear time.
What is the best approach for Best Time to Buy and Sell Stock using Strategy?
The most efficient approach uses prefix sums with a running minimum prefix value. By transforming the strategy into a gain array, the problem becomes finding the maximum difference between two prefix sums where the smaller one appears earlier. This runs in O(n) time and either O(n) or O(1) space depending on whether the prefix array is stored.
Is Best Time to Buy and Sell Stock using Strategy asked at Google/Amazon/Meta?
Stock profit optimization and maximum subarray style problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that involve prefix sums, dynamic profit tracking, or sliding windows are commonly used to test array optimization skills.
What data structure is used in Best Time to Buy and Sell Stock using Strategy?
The core structure is a simple array combined with prefix sums for cumulative profit computation. The algorithm also maintains a running minimum value to efficiently determine the best buy point before each sell point.
What is the time complexity of Best Time to Buy and Sell Stock using Strategy?
The optimal solution runs in O(n) time because the array is scanned once while maintaining the smallest prefix sum seen so far. Each step computes a candidate profit in constant time. Space complexity is O(n) with an explicit prefix array or O(1) with a running prefix calculation.